(Solve) N Queens with Python
Tags: tutorial, python, nqueens
Published: 2023-02-09 02:00:54

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.


![Drake Hotline Bling Meme](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gct41y8jo6g078comj3n.png)

### 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**.

![Backtracking Meme](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/coep27mktspjn8aso7gx.jpg)

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.

![N Queens Column](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9iptcqi15nd0uye9d7cp.png)

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

![N Queens PosDiag](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3n8gubq4khekivfmqp5u.png)

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

![N Queens NegDiag](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/014szyy5f7w56ot1tvz9.png)

- 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](https://github.com/ajipelumi/alx-higher_level_programming/blob/dd89a00435fdf4172c36431afc9237fd372315c9/0x08-python-more_classes/101-nqueens.py).

In order to use the code, follow these steps:

- Download the source code [here](https://github.com/ajipelumi/alx-higher_level_programming/blob/dd89a00435fdf4172c36431afc9237fd372315c9/0x08-python-more_classes/101-nqueens.py).
- 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.

```python
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.