Recursive Maze Visit

--D. Thiebaut (talk) 20:55, 22 October 2014 (EDT)

---

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( 2 );//000 );
		} catch (InterruptedException e) {
			//e.printStackTrace();
		}
	}

	private static boolean recursePlaceQueen( int row, int N ) {
		for ( int col = 0; col < N; col++ ) {
			if ( board[row][col] == 0 ) {
				board[row][col] = -1; // put a queen there
				displayBoard( N );

				//--- if on last row and found an empty spot, we're done! ---
				if ( row == N-1 )
					return true;

				updateColumnDown( row, col, N, +1 );
				updateDiagonals( row, col, N, +1 );
				
				boolean success = recursePlaceQueen( row+1, N );
				
				if ( success ) 
					return true;
				
				updateColumnDown( row, col, N, -1 );
				updateDiagonals( row, col, N, -1 );
				
				board[row][col] = 0;
				displayBoard( N );
			}
		}
		return false;
	}

	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++;
		}
	}

	private static void updateColumnDown(int row, int col, int N, int offset ) {
		for ( int r = row+1; r < N; r++ )
			board[ r ][ col ] += offset;
	}

	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;
	}

	public static void main(String[] args) {
		args = new String[] { "8" };
		if ( args.length == 0 ) {
			System.out.println( "Syntax: java NQueens N" );
			System.out.println( "        where N = dimension of board" );
			return;
		}
		
		int N = Integer.parseInt( args[0] );
		board = createBoard( N );
		
		recursePlaceQueen( /* row = */ 0, N );
		displayBoard( N );
	}
}