(Solve) N Queens with Python

The N Queens puzzle is the challenge of placing N non-attacking queens on an N×N chessboard in such a way that no two queens threaten each other, i.e. no two queens can be placed in the same row, column, or diagonal.

This is a tutorial on how I approached and solved the task.

Documentation

• Usage: nqueens N
  • If the user calls the program with the wrong number of arguments, an error message Usage: nqueens N is printed with an exit status of 1.
• where N must be an integer greater or equal to 4
  • If N is not an integer, an error message N must be a number is printed with an exit status of 1.
  • If N is smaller than 4, an error message N must be at least 4 is printed with an exit status of 1.
• The program prints every possible solution to the problem
  • One solution per line

Approach

One of the most effective and simple ways to solve N Queens is backtracking.

Here is how backtracking works:

1. We start by placing a queen in the first column of the first row.
2. Then, we try to place a queen in the first column of the second row.
3. If it is not possible to place a queen in the first column (because it would be attacking another queen), move on to the next column and try again.
4. This process is repeated until we have placed a queen in every row, or until it is not possible to place a queen in any of the remaining rows.
5. If a solution is found, the algorithm determines that it is possible to place n queens on the chessboard without any conflicts.
6. If it is not possible to place a queen in any of the remaining rows, the algorithm backtracks to the last queen that was placed and moves it to the next column. starting from the row where we left off.
7. This process is repeated until a solution is found or it is determined that no solution exists.

Pseudocode

• import sys module.
• check for number of arguments passed to the command-line (length of arguments should be 2).
• check if the argument passed is an integer.
• check if integer is greater than 4 (our documentation requires that N must be greater than or equal to 4).
• define global variable board to position our queens.
• define col set that keeps track of each queens position on every column.

• define posDiag set that keeps track of each queens positive diagonals.

• define negDiag set that keeps track of each queens negative diagonals.

• call our backtrack function which takes the following parameters:

  • r: represents row 0 which is our starting point
  • n: is our N chessboard
  • col: our column set
  • posDiag: positive diagonals
  • negDiag: negative diagonals
  • because backtrack is a recursive function, we set a base condition for the recursion to end when there are no more rows.
  • at that point we want to print all posiible solutions so we call the result function.
  • inside backtrack, we traverse through n columns and check if the queen's position is in col, posDiag or negDiag, if a position is found in any of them this would mean that the queen faces an attack from one of the other queens so the queen is moved to the next column.
  • board is updated to 1 to indicate that a queen is present in that position.
  • backtrack is called again but row increases by 1.
  • if the columns are exhausted and there is no where to place the queen, the previous queen is called and her position is changed, the board is also updated to 0 to reflect that change.

Links

• You can find the complete code for N Queens on Github.

In order to use the code, follow these steps:

• Download the source code here.
• Make the file executable by using the command chmod +x 101-nqueens.py on Linux/Mac or by changing the file properties on Windows.
• Run the code by executing the file with an argument that represents the value of n, which is the number of queens to be placed on the chessboard. See example below.

n_queens$ ./101-nqueens.py 4
[[0, 1], [1, 3], [2, 0], [3, 2]]
[[0, 2], [1, 0], [2, 3], [3, 1]]

n_queens$ ./101-nqueens.py 6
[[0, 1], [1, 3], [2, 5], [3, 0], [4, 2], [5, 4]]
[[0, 2], [1, 5], [2, 1], [3, 4], [4, 0], [5, 3]]
[[0, 3], [1, 0], [2, 4], [3, 1], [4, 5], [5, 2]]
[[0, 4], [1, 2], [2, 0], [3, 5], [4, 3], [5, 1]]

If this article was helpful in your understanding of N Queens, please leave a comment in the section below. Your feedback is appreciated. Also, do follow me for more informative articles like this one.