In this problem or puzzle, N queens will be given and the challenge is to place all of them in N x N chessboard so that no two queens are in attacking position. What that means is we need to find the configuration of N queens where any of the two queens do not share a row, column and diagonal paths.
One of the better and elegant solutions to this puzzle is ‘backtracking algorithm’. While we are going through the solution to the problem let us also explore the technique of backtracking.
Problem
Find all valid configuration of N Queens puzzle. To understand this better, let us look into an example – 4 queen’s problem. I am taking the 4 queens problem as there are no solutions for 2 and 3 queen’s problem and 1 queen problem is trivial one. For this, we are given 4 x 4 chessboard and we need to place 4 queens in non-attacking places on this board. Following are the only two configurations which exist for this 4 queen’s problem.
Backtracking Algorithm
Before we get on to the actual solution, let us look into the backtracking algorithm. Backtracking is similar to the brute force approach where it tries all of the solutions but the only difference is that it eliminates/avoids the partial candidate solutions as soon as it finds that that path cannot lead to a solution.
To understand this further, let us look into the following tree. By the way, this is called Trie or prefix tree and let us not worry about these in this post.
In the above mentioned tree, what path leads to the word “BACK” (first 4 letters of backtrackingJ)?
One of the simple way, I can think is as follows.
- Start at the root node ‘B’. Does this match with the 1st letter of the word BACK? YES
- Then check the 1st child node A – does this match 2nd letter of the word BACK? YES
- Then check the 1st child C – does this match 3rd letter of the word BACK? YES
- Check the 1st child L – does this match 4th letter of the word BACK? NO
- Check the 2nd child M – does this match 4th letter of the word BACK? NO
- Then check the 1st child C – does this match 3rd letter of the word BACK? YES
- Check the 2nd child D – does this match 3rd letter of the word BACK? NO
- Then check the 1st child node A – does this match 2nd letter of the word BACK? YES
- Check the 2nd child node C – does this match 2nd letter of the word BACK? NO
- Check the 3rd child node A – does this match 2nd letter of the word BACK? YES
- Check the 1st child V – does this match 3rd letter of word BACK? NO
- Check the 2nd child C – does this match 3rd letter of the work BACK? YES
- Check the 1st child K – does this match 4th letter of the work BACK? YES
Following are the observations based on the above steps,
- Every time when we hit NO, we went back to parent of that node and checked other child nodes/paths – this is back tracking
- Avoided all of the sub paths for the node whenever we hit non match (NO). This enabled us to avoid unnecessary paths exploration(2nd node C – at level 2 and others)
Following is the generalized algorithm in pseudo code,
Take a sub problem. For each of the possible candidates for this sub problem If this can lead to the solution, then recursively call this for next sub problem If not, then skip this possibility and investigate next candidate. If all of the sub problems are solved, Then we found a solution otherwise, no solution
Solution
As we now have the understanding of the backtracking algorithm let us see how that applies to our N Queens problem.
- We can divide this problem into a sub problem of placing single queen on the chess board
- To identify if this leads to a solution, we can check and see does any of the already placed queens attack this position. If yes, then go to next column. If no, then place this queen and move on to next queen
To illustrate this further,
- Did we place all of the queens?
- YES, we found the successful configuration. Print it.
- NO, Take the queen
- For each column from 1 to N
- Does this column is safe – YES, then iterate this process for next queens – call this method recursively
- NO – continue with next column
In Java
We can always represent the queen’s placement in an N x N array but let us use an array with N elements which stores the column positions of each array. For example, if A[2] = 5, it means the 2nd queen is placed on column 5. This way we can save the memory and also it is easy to find if a cell in the board is safe to place or not.
To find if the cell is safe of not, we need to look into two aspects.
Does any of the previously placed queen is in the same column?
This can easily be checked using the above noted array representation. Iterate through above noted array and see does any of the value matches the column we are trying to place current queen. By the way we need not check for the row as we construct the solution row by row and there will not be any queens placed in those.
Does any of the previously placed queen is in diagonal?
This is a bit tricky. The way can find is, iterate through each of the previously placed queen positions and check the absolute differences between the column and row value. If they are same, then they are in attacking position. Let us take an example here. Assume that we already placed first queen in (2, 2) – 2nd queen is placed in 2nd column. If we look at the diagonal cells (1,1), (1,3), (3,1), (3.3), we can observe that,
|r1-r2| == |c1-c2| is hold good.
- |1-2| = |1 -2| = 1 (for cell 1,1)
- |1-2| = |3-2| = 1 (for cell 1,3)
- |3-2| = |1-2| = 1 (for cell 3,1)
- |3-2| = |3-2| = 1 (for cell 3,3)
Following is the java method for the above logic,
//check if the column is safe place to put Qi (ith Queen) private static boolean isSafePlace(int column, int Qi, int[] board) { //check for all previously placed queens for (int i = 0; i < Qi; i++) { if (board[i] == column) { // the ith Queen(previous) is in same column return false; } //the ith Queen is in diagonal //(r1, c1) - (r2, c1). if |r1-r2| == |c1-c2| then they are in diagonal if (Math.abs(board[i] - column) == Math.abs(i - Qi)) { return false; } } return true; }
Following is the java method implementation of N Queens solution using backtracking technique,
private static void placeQueenOnBoard(int Qi, int[] board) { int n = board.length; //base case if (Qi == n) {// a valid configuration found. System.out.println(Arrays.toString(board)); } else { //try to put the ith Queen (Qi) in all of the columns for (int column = 0; column < n; column++) { if (isSafePlace(column, Qi, board)) { board[Qi] = column; //then place remaining queens. placeQueenOnBoard(Qi + 1, board); /** * backtracking. It is not required in this as we only look previously * placed queens in isSafePlace method and it doesnot care what values * are available in next positions.* */ board[Qi] = -1; } } } }
Following is the full java implementation of the above approach.
package com.sada.algorithms.backtracking; import java.util.Arrays; import java.util.Scanner; /** * * @author Sada Kurapati <sadakurapati@gmail.com> */ public class NQueens { public static void main(String args[]) { System.out.println("How many queens? "); Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] board = new int[n]; //hold the column position of n queens placeQueenOnBoard(0, board); } private static void placeQueenOnBoard(int Qi, int[] board) { int n = board.length; //base case if (Qi == n) {// a valid configuration found. System.out.println(Arrays.toString(board)); } else { //try to put the ith Queen (Qi) in all of the columns for (int column = 0; column < n; column++) { if (isSafePlace(column, Qi, board)) { board[Qi] = column; //then place remaining queens. placeQueenOnBoard(Qi + 1, board); /** * backtracking. It is not required in this as we only look previously * placed queens in isSafePlace method and it doesnot care what values * are available in next positions.* */ board[Qi] = -1; } } } } //check if the column is safe place to put Qi (ith Queen) private static boolean isSafePlace(int column, int Qi, int[] board) { //check for all previously placed queens for (int i = 0; i < Qi; i++) { if (board[i] == column) { // the ith Queen(previous) is in same column return false; } //the ith Queen is in diagonal //(r1, c1) - (r2, c1). if |r1-r2| == |c1-c2| then they are in diagonal if (Math.abs(board[i] - column) == Math.abs(i - Qi)) { return false; } } return true; } }