Oct. 8, 2018

The `N-queens problem`

is a classic problem that asks the following question.

How can N queens be place on a NxN chessboard so that no two queens attack each other?

The following figure shows a possible solution to the N-queens problem for $N=8$.

The N-queens problem can be solve via recursively searching a rooted tree using the depth-first scheme. This is a type of `combinatorial optimization`

problem, where the optimal solution is found by searching through a very large set of possible solutions. Whenever the search yields a solution, or finding that a solution is not possible under current node, the search `backtracks`

to the previous stage and changes state of a variable that hasn't been tried before. In this post, we will implement a simple recursive solution to finding the number of solution to the N-queens problem.

First, we define a function that builds a NxN chessboard. This can be easily achieved as a numpy array.

In [1]:

```
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
import seaborn as sns; sns.set()
%matplotlib inline
```

In [2]:

```
def build_chessboard(N):
return np.zeros((N, N))
```

Next, we define a printing function that displays a heatmap of the chessboard.

In [3]:

```
def print_board(chessboard):
df = pd.DataFrame(chessboard)
plt.figure()
sns.heatmap(df, linewidth=0.5, cbar=False, cmap="viridis",
square=True, xticklabels=False, yticklabels=False)
```

The following `fill_queen`

function is used to label all cells that are under attack by a queen.

In [4]:

```
def fill_queen(chessboard, row, col):
N = len(chessboard)
chessboard[:, col] = 2
chessboard[row, :] = 2
for i in range(N):
try:
chessboard[row+i, col+i] = 2
except IndexError:
pass
if (row-i>=0):
try:
chessboard[row-i, col+i] = 2
except IndexError:
pass
if (row-i>=0) and (col-i)>=0:
try:
chessboard[row-i, col-i] = 2
except IndexError:
pass
if (col-i>=0):
try:
chessboard[row+i, col-i] = 2
except IndexError:
pass
chessboard[row,col] = 1
return chessboard
```

Let's test our functions by building a 9x9 chessboard and placing a queen at the center.

In [5]:

```
chessboard = build_chessboard(9)
fill_queen(chessboard, 4, 4)
print_board(chessboard)
```

Now we are ready to build the recursive function to find the number of solutions.

In [6]:

```
def N_queens(chessboard, col=0, count=0, solutions=[]):
"""
Inputs:
------------
chessboard: NxN chessboard as numpy array
col: column number from 0 to N (start at 0)
count: total number of solutions (start at 0)
Output:
------------
The number of solutions.
Also plots the first five solutions.
"""
# Building a NxN chessboard
N = len(chessboard)
if col == N:
# Appending a new solution to the list
solutions.append(chessboard)
# Printing the first five solutions
if count < 5:
print_board(chessboard)
return count+1, solutions
# The traversal set of a tree as rows
for row in range(N):
# Check whether a cell is under attack. If not, place a queen.
if chessboard[row][col] == 0:
# Creating a copy of the chessboard so that the original remains in the tree
'''
This is a crucial step. Without copying, the original root
of the tree will be changed, so we lose the tree structure!
'''
chessboard_copy = chessboard.copy()
solutions_copy = solutions.copy()
# Placing a new queen
chessboard_copy = fill_queen(chessboard_copy, row, col)
# Branching to a lower level in the tree
count, solutions = N_queens(chessboard_copy, col+1, count, solutions_copy)
return count, solutions
```

In [7]:

```
chessboard = build_chessboard(8)
count, solutions = N_queens(chessboard)
print ("Number of solutions:", count)
```

To build an animated version of all the solutions, all you need is to install the `ImageMagick`

package. On Ubuntu, you can simply type in the terminal,

```
sudo apt-get install imagemagick
```

On Mac OSX, we can use `homebrew`

by typing in the terminal,

```
brew install imagemagick
```

Then run the following code, and the output will be a `.gif`

of all the solutions. (Note that this only works on UNIX systems.)

In [11]:

```
i = 0
for chessboard in solutions:
print_board(chessboard)
plt.savefig(str(i)+'myfig')
i += 1
plt.close()
from subprocess import Popen
Popen('convert -delay 20 -loop 0 *.png myimage.gif', shell=True).wait()
Popen('rm *myfig.png', shell=True).wait()
pass
```

The output is the following.