Created
November 26, 2019 18:58
-
-
Save dhable/38cd789e0e0deaba03bd6ba5680239ff to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package appito; | |
import java.util.ArrayList; | |
import java.util.List; | |
class Queen | |
{ | |
private int xPos = 0; | |
private int yPos = 0; | |
public Queen( int initialX, int initialY ) { | |
setXPos( initialX ); | |
setYPos( initialY ); | |
} | |
public int getXPos() { return xPos; } | |
public int getYPos() { return yPos; } | |
public void setXPos( int x ) { | |
if( 0 < x || x < 8 ) { | |
xPos = x; | |
} else { | |
throw new RuntimeException( "New value of xPos outside allowed range." ); | |
} | |
} | |
public void setYPos( int y ) { | |
if( 0 < y || y < 8 ) { | |
yPos = y; | |
} else { | |
throw new RuntimeException( "New value of yPos outside allowed range." ); | |
} | |
} | |
private static boolean closeEnough( double value1, double value2 ) { | |
return (value2 - 0.000001) < value1 && value1 < (value2 + 0.000001); | |
} | |
public boolean canTake( Queen otherQueen ) { | |
if( otherQueen == this ) // one cannot take themselves | |
return false; | |
final double rise = otherQueen.getYPos() - getYPos(); | |
final double run = otherQueen.getXPos() - getXPos(); | |
if( closeEnough(run, 0) ) // infinite slope, need to detect here since we can't divide by zero | |
return true; | |
final double slope = rise / run; | |
return ( closeEnough(slope, 0) || closeEnough(slope, -1) || closeEnough(slope, 1) ); | |
} | |
public String toString() { return "(" + xPos + "," + yPos + ")"; } | |
} | |
public final class Queens { | |
static final void findSolution( Queen[] queens, int currentCol ) { | |
if( currentCol < 8 ) { | |
for( int yPos = 0; yPos < 8; yPos++ ) { | |
queens[currentCol].setYPos( yPos ); | |
boolean beTaken = false; | |
for( int i = 0; i < currentCol; i++ ) | |
beTaken = queens[i].canTake(queens[currentCol]) || beTaken; | |
if( !beTaken ) { | |
int nextCol = currentCol + 1; | |
if( nextCol < 8 ) | |
findSolution( queens, nextCol ); | |
else { | |
System.out.print("Possible solution - "); | |
for(Queen q: queens ) | |
System.out.print( q.toString() ); | |
System.out.println(" "); | |
} | |
} | |
} | |
} | |
} | |
public static void main( String[] args ) { | |
Queen[] placedQueens = new Queen[8]; | |
for( int i = 0; i < 8; i++ ) | |
placedQueens[i] = ( new Queen( i, 0 ) ); | |
findSolution( placedQueens, 0 ); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment