JAVA

n queens problem leetcode

/*
	This implementation produces a non-attacking placement
	of chess queens. A non-attacking placement is one where
	no queen can attack another queen in a single turn.
	This is one of the best examples of backtracking. 

	Let N be the number of queens to be placed on 
	a N*N board. 
	Time complexity: O(N!)
	Space complexity: O(N^2)
*/
public class NQueensProblem {
	int[][] board;
	int N; // Number of queens
	public NQueensProblem(int N) {
		this.N = N;
		board = new int[N][N];
	}
	public void printBoard() {
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) {
				System.out.print(board[i][j] + " ");
			}
			System.out.println();
		}
	}
	/*
	 * A utility function to check if a queen can be
	 * placed on board[row][col].
	 * Note that this function is called when "col" queens
	 * are already placed in columns from 0 to col -1.
	 * So we need to check only left side for attacking
	 * queens.
	 */
	public boolean isSafe(int row, int col) {
		int i, j;
		// Check the row on left side
		for (i = 0; i < col; i++) {
			if (board[row][i] == 1) {
				return false;
			}
		}
		// Check upper diagonal on left side
		for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {
			if (board[i][j] == 1) {
				return false;
			}
		}
		// Check lower diagonal on left side
		for (i = row, j = col; i < N && j >= 0; i++, j--) {
			if (board[i][j] == 1) {
				return false;
			}
		}
		return true;
	}
	public boolean solveUtil(int col) {
		/*
		 * base case: If all queens are placed then return true
		 */
		if (col >= N) {
			return true;
		}
		/*
		 * Consider this column and try placing this queen
		 * in all rows one by one
		 */
		for (int row = 0; row < N; row++) {
			/*
			 * Check if the queen can be placed on board[row][col]
			 */
			if (isSafe(row, col)) {
				board[row][col] = 1;

				// Recur to place the rest of the queens
				if (solveUtil(col + 1) == true) {
					return true;
				}

				/*
				 * If placing queen in board[row][col] doesn't lead to a * solution then remove
				 * queen from board[i=row][col]
				 */
				board[row][col] = 0; // backtrack
			}
		}
		/*
		 * If the queen can not be placed in any row in this column col, * then return
		 * false
		 */
		return false;
	}
	/*
	 * This function solves the N Queen problem using Backtracking.
	 * It mainly uses solveNQUtil () to solve the problem.
	 * It returns false if queens cannot be
	 * placed, otherwise, return true and prints placement
	 * of queens in the form of
	 * 1s.
	 * Please note that there may be more than one solutions, this
	 * function prints one of the feasible solutions.
	 */
	public void solve() {
		if (solveUtil(0) == false) {
			System.out.println("No solution found.");
			return;
		}
		System.out.println("The following solution was found: ");
		printBoard();
	}
	public static void main(String[] args) {
		NQueensProblem problem = new NQueensProblem(4);
		problem.solve();
	}
}