Today I am going to explain n queen problem which is based on backtracking. N-queen problem is to set n queens on a board of chess of size n*n such that no queen can attack each other.
For those who don’t know how queen works in chess-
The queen can attack anyone which is diagonally,horizontally or vertically placed to the queen.
One such combination on 4*4 board, where no queen can attack each other is (queen is represented by x)
To solve this problem we will use backtracking. We will start from the first row, place the queen in the very first box available to us.
Then we move to next row start from the 0th index and check if the current queen is compatible with the previously placed queens. If the queen is compatible to all the previous queens we head to next row otherwise, we increase the column of the current queen. If we can not increase the current queen’s column(the current column is the last one on the board). Then we move one row backward and increase the column of that queen and continue with the same algorithm.
If the queen is compatible to all the previous queens we head to next row otherwise, we increase the column of the current queen. If we can not increase the current queen’s column(the current column is the last one on the board). Then we move one row backward and increase the column of that queen and continue with the same algorithm.
If we reach to last row and queen is compatible then we return the current board. If we reach to last column of row 0 after backtracking then there is no such combination which satisfies the problem.
To check the compatibility of the queen with another queen the following rule can be used
- If rows of both queens are same
- If column of both queens are same
- Differences of row and column of both the queens are same
- Differences of column and row of both the queens are same
If any of the above conditions is satisfied then queens are not compatible.
def is_compatible(pos_to_compare,pos_to_be_compared_with): if pos_to_be_compared_with==pos_to_compare: return False if pos_to_be_compared_with==pos_to_compare: return False if pos_to_compare+pos_to_compare==pos_to_be_compared_with+pos_to_be_compared_with: return False if pos_to_compare-pos_to_compare==pos_to_be_compared_with-pos_to_be_compared_with: return False return True
Let’s understand the above problem with an example-
We chose the first row and the first column for the starting row queen. Then we chose the first column in the next row
Now these queens are not compatible so we choose the next column in the same row.
Above board satisfies the conditions hence we head to next row and choose the first column.
Now this board doesn’t satisfy the condition so we choose the next column in this row.
Again this doesn’t satisfy so move to next column until we either satisfy the condition or reach the end of row.
We have reached the row of the current row and still the conditions are not satisfied so we move back one row and choose the next column for that.
Then again we choose the next row starting with first column again.
The process continue until we reach the combination which satisfy the conditions otherwise we don’t have any move left.
For the above board we get the final board as
Data Structure For the Problem
Data structure which should be used in this problem is stack. Using stack we can pop the last item if we can’t move forward in the row.
The time complexity for this problem is exponential.
Source code for this problem can be found here.