N-Queens Problem in Java
--D. Thiebaut (talk) 22:50, 22 October 2014 (EDT)
/**
* NQueens.java
* @author thiebaut
* Positions N queens on an NxN board.
*/
public class NQueens {
static int[][] board = null;
private static void displayBoard( int N ) {
char escCode = 0x1B;
System.out.println(String.format("%c[%d;%df", escCode, 0, 0 ));
for ( int c=0; c < N; c++ )
System.out.print( "--" );
System.out.println();
for ( int r=0; r < N; r++ ) {
for ( int c=0; c < N; c++ ) {
if ( board[r][c] == -1 )
System.out.print( "Q " );
else if ( board[r][c] == 0 )
System.out.print( ". " );
else
System.out.print( "* " );
}
System.out.println();
}
try {
Thread.sleep( 2000 );//000 );
} catch (InterruptedException e) {
//e.printStackTrace();
}
}
private static void displayBoardNumbers( int N ) {
System.out.println(String.format("%c[%d;%df", 0x1B, 0, 0 ));
for ( int c=0; c < N; c++ )
System.out.print( "--" );
System.out.println();
for ( int r=0; r < N; r++ ) {
for ( int c=0; c < N; c++ )
System.out.print( String.format( "%2d", board[r][c]) );
System.out.println();
}
}
/**
* recursively place N queens on the NxN board.
* Our job is to place a queen on Row row, anywhere we can, and then
* call ourself on Row row+1... until all N queens have been placed
* @param row: the row we're working on.
* @param N: the dimension of the board
* @return true if successfully placed all N queens. False if we got stuck.
*/
private static boolean recursePlaceQueen( int row, int N ) {
// We've landed on Row row. Let's try all the columns that
// are open...
for ( int col = 0; col < N; col++ ) {
// is there a non-taken spot?
if ( board[row][col] == 0 ) {
// yes; let's put a queen here, temporarily
board[row][col] = -1; // put a queen there
//if we're on last row and found an empty spot, then we're done! ---
if ( row == N-1 )
return true;
// otherwise, we have some more recursing to do. Mark all the
// cells down from this row that are taken by the queen we've just
// added.
updateColumnDown( row, col, N, +1 );
updateDiagonals( row, col, N, +1 );
// show the current board
displayBoard( N );
// recurse, asking ourselves to put a new queen on the row
// below where we are. Keep track of whether recursion was
// successful or not.
boolean success = recursePlaceQueen( row+1, N );
// were we successful putting all N queens?
if ( success )
// yes: then we're done, return true!
return true;
// No, we were not successful... could not place all N queens with
// our queen currently where it is. Remove it
board[row][col] = 0;
// undo the invalidation that was done earlier...
updateColumnDown( row, col, N, -1 );
updateDiagonals( row, col, N, -1 );
// display current state of the board
displayBoard( N );
// continue looping, looking for a new position where to put a queen
// on Row row.
}
}
// if we're here, we've tried all the possible columns on Row row, and we weren't
// successful. So return false to whoever called us... No success with current
// position of queens on rows above us...
return false;
}
/**
* given the position of a queen at Row row and Column col, mark all the
* cells on rows below and on diagonal positions relative to (row, col) as
* "taken", if offset is 1, or as "not taken" if offset is -1.
* @param row
* @param col
* @param N
* @param offset
*/
private static void updateDiagonals(int row, int col, int N, int offset) {
int leftC = col-1, rightC = col+1;
for ( int r=row+1; r<N; r++ ) {
if ( leftC >= 0 ) board[r][leftC] += offset;
leftC--;
if ( rightC < N ) board[r][rightC] += offset;
rightC++;
}
}
/**
* given the position of a queen at Row row and Column col, mark all the
* cells on rows just below this cell as "taken", if offset is 1, or as
* "not taken" if offset is -1.
* @param row
* @param col
* @param N
* @param offset
*/
private static void updateColumnDown(int row, int col, int N, int offset ) {
for ( int r = row+1; r < N; r++ )
board[ r ][ col ] += offset;
}
/**
* create an NxN board with empty cells (containing 0)
* @param N
* @return
*/
private static int[][] createBoard( int N ) {
board = new int[N][];
for ( int i=0; i<N; i++ )
board[i] = new int[N];
for ( int i=0; i<N; i++ )
for ( int j=0; j<N; j++ )
board[i][j] = 0;
return board;
}
/**
* main entry point.
* @param args
*/
public static void main(String[] args) {
if ( args.length == 0 ) {
args = new String[] { "8" };
}
int N = Integer.parseInt( args[0] );
board = createBoard( N );
recursePlaceQueen( /* row = */ 0, N );
displayBoard( N );
}
}