A goal should scare you a little, and excite you a lot. - Joe Vitale
N Queens - Branch and Bound
Welcome Reader!
In this article we will discuss about the first problem based on "Recursion and Backtracking" i.e. N Queens - Branch and Bound.
We have already discussed this problem, N Queens, earlier in level-1. But here we will use the Branch and Bound approach.
If you want then you can try and solve that one first, so that you can get a broader perspective to understand this problem using a better approach which is Branch and Bound.
Before you move any further, it is advised that you give this problem a fair try.
In this problem you are given a number n, the size of a chess board.
You are required to place n number of queens in the n * n cells of board such that no queen can kill another, by completing the body of "printNQueens()" function - without changing signature - to calculate and print all safe configurations of n-queens.
Note:
Queens Kill at distance in all 8 directions
The online judge can't force you to write the function recursively but that is what the spirit of the 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.
The input is 4, which implies that (n=4), the size of a chess board is 4. We need to place 4 queens in the 4*4 cells of board such that no queen can kill each other.
There are 2 ways to place the 4 queens in 4*4 cells of board.
First way is represented by green circle (* sign), when queens are placed at 0-1, 1-3, 2-0, 3-2.
Second way is represented by red circle (# sign), when queens are placed at 0-2, 1-0, 2-3, 3-1.
For better understanding of the question, watch part of the video lecture. Use recursion as suggested in the video.
Moving On:
First of all, let's go through the rules of queen movement in chess:
She can move horizontally.
She can move vertically.
She can move diagonally in both directions.
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:
Cols(column) 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. Its size will be equal to N as there are N columns.
Ndaig(normal) array to check 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.
Rdiag(reverse) array to check whether the current reverse 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.
Let the n be 4.
For better understanding of the question, watch part of the video lecture. Use recursion as suggested in the video.
NDIAG
Here every box is filled with the sum of row index and col index.
Thus, we can see that every line represents the 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 the 1st index of the 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, by 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 the 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 the 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, by 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) elements of the matrix.
For better understanding of the question, watch part of the video lecture. Use recursion as suggested in the video.
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.
Let's try to code this!
import java.util.*;
public class Main {
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;
true";
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 - col + 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.
Base Case: When the row will be equal to the length of board, we will print our asf and return.
Watch this of the video lecture for better understanding.
Complexities:O()
Time Complexity: O()
Complete Code:
import java.io.*;
import java.util.*;
public class Main {
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;
}
}
}
public static void main(String[] args) throws Exception {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
boolean[][] board = new boolean[n][n];
boolean[] cols = new boolean[n];
boolean[] ndiag = new boolean[2 * n - 1];
boolean[] rdiag = new boolean[2 * n - 1];
solution(board, 0, cols, ndiag, rdiag, "");
}
}
java;
true";
We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.
We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.
Trust me it will just get easier to understand after you have watched the solution video.
You can contact us via our website. Doubts, suggestions and feedback are always welcomed.
It is also advised that you follow the sequence of modules and questions which is there on our website.
Keep practicing more and more problems daily. Meditate enough on each step of each problem.
All the best for an exciting future!
Happy Coding!
