N Queens  Branch And Bound
1. You are given a number n, the size of a chess board.Input Format
2. You are required to place n number of queens in the n * n cells of board such that no queen can
kill another.
Note  Queens kill at distance in all 8 directions
3. Complete the body of printNQueens function  without changing signature  to calculate and
print all safe configurations of nqueens
Use sample input and output to get more idea.
Note > The online judge can't force you to write the function recursively but that is what the spirit
of question is.
Write recursive and not iterative logic. The purpose of the question is to aid learning recursion, branch and bound technique and not test you.
A number nOutput Format
Safe configurations of queens as suggested in sample outputQuestion Video
1 <= n <= 10Sample Input
4Sample Output
01, 13, 20, 32, .
02, 10, 23, 31, .

Editorial
Before proceeding we will go through the rules of queen movement in chess.
1. She can move horizontally.
2. She can move vertically.
3. She can move diagonally in both the directions.
We will be solving the previously solved N  Queens problem but with a new way.
In a 4 X 4 board, we can place queens in the following way.
As we can see on the board, two sets of queens * and # can be placed on the 4 X 4 chess board.
Ans for N = 4 is
01, 13, 20, 32, .
02, 10, 23, 31, .
Like previously, we will be solving this with recursion but with a new and better way.
At each level of recursion, we will increase the current row. We do not need to check the row as at each row only one queen can be placed. To check for columns and diagonals, we will create three new boolean array.
1. Cols array to check whether the current column is occupied by any other queen or not. If it is, we cannot place our queen on that column. It is size will be equal to N as there are N columns.
2. Ndaig(normal) array to checker whether the current normal diagonal is occupied or not. If it is, we cannot place our queen on that box. Its size will be equal to 2*N  1 as there are 2 * N  1 diagonals in N X N board.
3. Rdiag(reverse) array to check whether the current reverse diagonal is occupied or not. If it is, we cannot place out queen on that box. Its size will be equal to 2*N  1 as there are 2 * N  1 diagonals in N X N board.
Let the N be 4.
NDIAG
Here every box is filled with the sum of row index and col index.
Thus, we can see that every line represents same number and they represent the normal diagonal. Therefore, the size of ndiag is 2*N  1.
Therefore, the element with index (0,1) will be represented as 1st index of ndiag array. If there is a queen on (0,1) then no queen can be placed on (1,0) too, therefore my marking 1st index of ndiag we are restricting any other queen on (1,0) too.
Similarly, my marking any index of ndiag as true, we are restricting any other queen on the same diagonal.
RDIAG
Here every element is filled with the difference of row and col index.
Thus, we can see that every line represents same item and they represent the reverse diagonal. As the number of lines is 2*N  1. Therefore, the size of reverse diagonal is 2*N  1.
As we cannot represent negative numbers as index of an array therefore we will add N  1 to every element of 2D array to bring it in range of [0,2*N1].
New 2D array
Therefore, the element with index (0,1) will be represented as 2nd index of ndiag. If there is a queen on (0,1) then no queen can be placed on (1,2) and (2,3) too, therefore my marking 2nd index of rdiag we are restricting any queen on (1,2) and (2,3) too.
Similarly, my marking any index of rdiag as true, we are restricting any other queen on the same diagonal.
This array shows that index 2 of ndiag is storing the value for (2,0), (1,1) and (0,2) element of matrix.
Signature of the function 
public static void solution(boolean[][] board, int row, boolean[] cols, boolean[] ndiag, boolean[] rdiag, String asf)
board  N X N board. It is marked as true wherever the queen is placed.
row  current row.
cols  array of size N. It is used to keep a tab of columns that are already occupied by the queen placed before the current queen.
ndiag  array of size 2 * N  1. It is used to keep a tab of normal diagonals that are already occupied by the queen placed before the current queen.
rdiag  array of size 2 * N  1. It is used to keep a tab of reverse diagonals that are already occupied by the queen placed before the current queen.
asf  string to store the positions where queens are placed.
Code 
public static void solution(boolean[][] board, int row, boolean[] cols, boolean[] ndiag, boolean[] rdiag, String asf) { if (row == board.length) { System.out.println(asf + "."); return; } for (int col = 0; col < board.length; col++) { if (!cols[col] && !ndiag[row + col] && !rdiag[row  col + board.length  1]) { board[row][col] = true; cols[col] = true; ndiag[row + col] = true; rdiag[row  col + board.length  1] = true; solution(board, row + 1, cols, ndiag, rdiag, asf + row + "" + col + ", "); board[row][col] = false; cols[col] = false; ndiag[row + col] = false; rdiag[row  col + board.length  1] = false; } } }
java false
Code Explained 
At each level of recursion, we will use a for loop to go through every column. If the cols[col] == false and rdiag[row  col+ N  1] == false && ndiag[col + row] == false , it means that there is no other queen that can kill the current queen .Therefore, we will place our queen on that box and mark the cols[col] , rdiag[ row cols+ N  1] and ndiag[col+ row] as true in preorder(VISIT).
We will then make a call for the next row.
We will unvisit the visited cols, rdiag and ndiag in post order and mark cols[col], ndiag[row+col] and rdiag[row  col + N  1] as false.(UNVISIT)
Base Case 
When the row will be equal to the length of board, we will print our asf and return.

Asked in Companies

Related Topics