November 30, 2016

N queens solver in Python 3

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:
            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")
            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:
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
    jx, jy = row,col
    while jx < size and jy >= 0:
        if board[jx][jy] == 1:
            return False
    return True

def solve(board, col, size):
    """Use backtracking to find all solutions"""
    #base case
    if col >= size:
    for i in range(size):
        if is_safe(board, i, col, size):
            board[i][col] = 1
            if col == size-1:
                board[i][col] = 0
            solve(board, col+1, size)
            board[i][col] = 0

def add_solution(board):
    """Saves the board state to the global variable 'solutions'"""
    global solutions
    saved_board = copy.deepcopy(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 = 
[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.



© Plogging Dev - Powered by Hugo Theme by Kiss