N Queens - Branch And Bound

1. You are given a number n, the size of a chess board.
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 n-queens

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.

Input Format

A number n

Output Format

Safe configurations of queens as suggested in sample output

Question Video Constraints

1 <= n <= 10

Sample Input

4

Sample Output

0-1, 1-3, 2-0, 3-2, .
0-2, 1-0, 2-3, 3-1, .

• 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

  0-1, 1-3, 2-0, 3-2, .

  0-2, 1-0, 2-3, 3-1, .

  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*N-1].

  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