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:
board[i][col] = 0
return
solve(board, col+1, size)
#backtrack
board[i][col] = 0

"""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: