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.

Image by author

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.

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?

Let’s see how this can be applied for a 4x4 grid.

  1. Take a 4x4 chessboard
Image by author

2. Place the queen in the left-most column.

Image by author

3. Place the second queen in the second column such that it cannot attack the queen in the first column.

Image by author

4. Locating the third queen in the third column prevents it from attacking the queens in the first two columns.

Image by author

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.

Image by author

6. Place the third queen in a safe cell in the third column.

Image by author

7. Locating the fourth queen in the neighboring column prevents it from attacking the queens in the first three columns.

Image by author

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.

Image by author

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.

Image by author

10. Position the first queen in the first column’s next protected cell.

Image by author

11. Position the second queen in the second column’s protected cell.

Image by author

12. Put the third queen in the third column’s protected cell.

Image by author

13. Put the fourth queen in the fourth column’s protected cell.

Image by author

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!

Reading Bachelor of Science Honours in Computer Science at University of Jaffna, HND in Construction and Built Environment (Civil Engineering)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store