Solving a classic problem in Artificial Intelligence called N-Queens Problem using Backtracking Algorithm
N-Queen problem is a classical problem in the field of Artificial Intelligence and the goal is to arrange N queens on an NxN grid in such a way that no queen can “take” another queen. Queens can move horizontally, vertically, or diagonally.
Look at the following diagram which explains the problem definition that has mentioned above for 4 — queens.
Considering the history, the goal of the n-queens problem is to find Q(n), the number of different ways to arrange n-queens on an n-by-n chessboard so that no two queens are on the same row, column, or diagonal. The problem has been around for a long time. In 1848, an anonymous problem posed the 8-by-8 case. Max Bezzel was later credited with this. In the years since, the problem has piqued the interest of a number of well-known mathematicians, including Gauss, Lucas, and Polya. It is currently of particular interest as a benchmark problem for backtracking algorithms; it is representative of a large literature. Nonetheless, there appears to be no algorithm whose complexity is known to be superior to the brute-force strategy.
Caution : No valid solution exists for a 2 x 2 or a 3 x 3 chessboard.
How to use Backtracking Algorithm to solve the N-Queens problem?
The idea is to position queens in different columns one by one, beginning with the leftmost column. When we position a queen in a column, we look for conflicts with other queens that have already been placed. If we locate a row in the current column with no clash, we label this row and column as part of the solution. If we cannot find such a row due to conflicts, we retrace our steps and return false.
How does it work?
1. Start in the leftmost column
2. Return true if all queens are placed.
3. Experiment with all of the rows in the current column. Do the following for each tried row.
a. If the queen can still be safely placed in this row, then label this [row, column] as part of the solution and check recursively if locating the queen here leads to a solution.
b. Return true if locating the queen in [row, column] results in a solution.
c. If locating the queen does not result in a solution, unmark this [row, column] (Backtrack) and return to step (a) to try other rows.
4. If all rows have been tried and nothing has worked, return false to start the backtracking process.
Let’s see how this can be applied for a 4x4 grid.
- Take a 4x4 chessboard
2. Place the queen in the left-most column.
3. Place the second queen in the second column such that it cannot attack the queen in the first column.
4. Locating the third queen in the third column prevents it from attacking the queens in the first two columns.
Because such a placement is not possible, backtrack to the second column.
5. Place the second queen in another safe cell in the second column.
6. Place the third queen in a safe cell in the third column.
7. Locating the fourth queen in the neighboring column prevents it from attacking the queens in the first three columns.
Because such a positioning is not possible, backtrack to the third column.
8. Locate the third queen in the third column’s other protected cell.
There are no other safe cells in column 3 for the queen, so backtrack once again.
9. There are no other protected cells in column 2 for the queen, so backtrack to the first column.
10. Position the first queen in the first column’s next protected cell.
11. Position the second queen in the second column’s protected cell.
12. Put the third queen in the third column’s protected cell.
13. Put the fourth queen in the fourth column’s protected cell.
And this is our solution!
We have one more solution. Can you deduce that?
Try to implement this in any programming language.
What about the time complexity?
Well, in NxN grid, the first Queen in the first column has the freedom to be in any row in its first column, that is, N positions. The 2nd will have N-1 positions, the 3rd will have N-2 positions, and so on. So the Time Complexity is O(N(N-1)(N-2)….1) = O(N!). This is the worse case of this problem.
As a result, the time complexity for discovering all solutions to the N Queens problem is polynomial.
Hope this helps you!
Let me know your thoughts!