N-Queens In Java, Counting the Number of Probes

--D. Thiebaut (talk) 09:52, 24 October 2014 (EDT)

---

A Java version of the N-Queens problem, that attempts to put N queens on an NxN board. It stops after the first solution is found, and reports the real time execution time. See this page for a comparison of execution times on various machines.

/**
 * NQueens.java
 * @author thiebaut
 * Positions N queens on an NxN board.
 * To compile and run:
 *      javac NQueens.java
 *      java NQueens N         
 *      (where N is the size of the board)
 */
public class NQueens {
	static int[][] board = null;
	static int counter = 0;
	
	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( 0 );//
		} 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?
			counter++;
			if ( board[row][col] == 0 ) {
				
				// yes; let's put a queen here, temporarily
				board[row][col] = -1; // put a queen there
				counter++;
				
				//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;
				counter++;
				
				// 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 ) {
				counter++;
				board[r][leftC]  += offset;
			}
			leftC--;
			if ( rightC < N ) { 
				board[r][rightC] += offset;
				counter++;
			}
			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;
			counter++;
		}
	}

	/**
	 * 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++ ) {
			counter++;		
			board[i] = new int[N];
		}
		
		for ( int i=0; i<N; i++ )
			for ( int j=0; j<N; j++ ) {
				counter++;
				board[i][j] = 0;
			}
		
		return board;
	}


	/**
	 * clears the screen (works only in Terminal/Console)
	 */
	private static void clearScreen() {
        System.out.print("\033[2J\033[;H");
    }
	
	/**
	 * main entry point.
	 * @param args
	 */
	public static void main(String[] args) {
		
		if ( args.length == 0 ) {
			args = new String[] { "30" };
		}
		
		//clearScreen();
		
		int N = Integer.parseInt( args[0] );
		board = createBoard( N );
		
		counter=0;
		long start = System.currentTimeMillis();
		recursePlaceQueen( /* row = */ 0, N );
		long end = System.currentTimeMillis();
		
		//displayBoard( N );
		System.out.println( String.format(
				"%dx%d board: %d probes. real time = %d ms.",
				N, N, counter, (end-start) ) );
	}
}