What is the N queens problem?

The N queens problem is the problem of placing N non-attacking queens on an NxN chessboard, for which solutions exist for all natural numbers N with the exception of N=2 and N=3.

When N=1, the solution is trivial so the program will ask for a value of N such that `N >= 4`

.

I will solve this problem using backtracking. There are more efficient ways to solve this problem, but I will use backtracking since it’s the most intuitive way to arrive at the solution without getting into the mathematics of arriving at efficient solutions. Through solving these problems, I aim to better understand Python.

What is backtracking?

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons each partial candidate *c* (“backtracks”) as soon as it determines that *c* cannot possibly be completed to a valid solution.

A high level overview of how to use backtracking to solve the N queens problem:

- place a queen in the first column and first row
- place a queen in the second column such that it does not attack the queen in the first column
- continue placing non-attacking queens in the remaining columns
- if all N queens have been placed, a solution has been found. Remove the queen in the Nth column, and try incrementing the row of the queen in the (N-1)th column
- if it’s a dead end, remove the queen, increment the row of the queen in the previous column
- continue doing this until the queen in the 1st column exhausts all options and is in the row N

The above explanation starts counting at 1, not 0 based counting.

To see a visualization of backtracking, refer here.

The solution:

```
import copy
def take_input():
"""Accepts the size of the chess board"""
while True:
try:
size = int(input('What is the size of the chessboard? n = \n'))
if size == 1:
print("Trivial solution, choose a board size of atleast 4")
if size <= 3:
print("Enter a value such that size>=4")
continue
return size
except ValueError:
print("Invalid value entered. Enter again")
def get_board(size):
"""Returns an n by n board"""
board = [0]*size
for ix in range(size):
board[ix] = [0]*size
return board
def print_solutions(solutions, size):
"""Prints all the solutions in user friendly way"""
for sol in solutions:
for row in sol:
print(row)
print()
def is_safe(board, row, col, size):
"""Check if it's safe to place a queen at board[x][y]"""
#check row on left side
for iy in range(col):
if board[row][iy] == 1:
return False
ix, iy = row, col
while ix >= 0 and iy >= 0:
if board[ix][iy] == 1:
return False
ix-=1
iy-=1
jx, jy = row,col
while jx < size and jy >= 0:
if board[jx][jy] == 1:
return False
jx+=1
jy-=1
return True
def solve(board, col, size):
"""Use backtracking to find all solutions"""
#base case
if col >= size:
return
for i in range(size):
if is_safe(board, i, col, size):
board[i][col] = 1
if col == size-1:
add_solution(board)
board[i][col] = 0
return
solve(board, col+1, size)
#backtrack
board[i][col] = 0
def add_solution(board):
"""Saves the board state to the global variable 'solutions'"""
global solutions
saved_board = copy.deepcopy(board)
solutions.append(saved_board)
size = take_input()
board = get_board(size)
solutions = []
solve(board, 0, size)
print_solutions(solutions, size)
print("Total solutions = {}".format(len(solutions)))
```

Output of the program when N=4:

```
What is the size of the chessboard? n =
4
[0, 0, 1, 0]
[1, 0, 0, 0]
[0, 0, 0, 1]
[0, 1, 0, 0]
[0, 1, 0, 0]
[0, 0, 0, 1]
[1, 0, 0, 0]
[0, 0, 1, 0]
Total solutions = 2
```

Some important takeaways from coding the solution:

- To make an NxM list use:

```
A = [0] * N
for i in range(N):
A[i] = [0] * M
```

I tried, `A = [[0] * M] * N`

initially, which is wrong. More info here.

When saving the contents of a multidimensional list, use

`copy.deepcopy(to_save)`

.Testing is hard! More so when dealing with complicated outputs from a function. I will update this blog with tests soon.

Source code available here.

References: