The n-queens problem involves finding all possible ways to place n non-attacking queens on an nxn board. Non-attacking implies that no two queens can be on the same row, column, or diagonal, and therefore have no way of attacking one another. One possible solution to the n-queens problem, where n=4, can be displayed as follow:
Most readily-available solutions involve using a direct representation of the chess board, such as an nxn array, to dictate the placement of queens on the board. Although this approach works, it is not efficient. Instead, a more practical approach is to represent the state of the rows, columns, and diagonals using dictionaries. Using this method, we directly observe whether a specific row, column, or diagonal is under attack.
GitHub repository for this post
To do so, I make use of a single Python dictionary to store all needed information on the board, initialized as follows:
def initialize(n, board): # initialize the board
for key in ['queen','row','col','nwtose','swtone']:
board[key] = {}
for i in range(n): # set the queen positions, row vals, and col vals to empty
board['queen'][i] = -1
board['row'][i] = 0
board['col'][i] = 0
for i in range(-(n-1), n): # set main diagonal to empty
board['nwtose'][i] = 0
for i in range(2*n-1): # set opposite diagonal to empty
board['swtone'][i] = 0
Then, I create functions to check whether a particular spot on the board is free, as well as functions to add a queen and remove a queen from the board:
def is_free(i, j, board): # function to check whether a spot is available
return(board['row'][i]==0 and board['col'][j]==0 and board['nwtose'][j-i]==0 and board['swtone'][j+i]==0)
def addqueen(i,j,board): # add a queen by filling the spot
board['queen'][i] = j
board['row'][i] = -1
board['col'][j] = -1
board['nwtose'][j-i] = -1
board['swtone'][j+i] = -1
def undoqueen(i,j,board): # undo the filling of a spot
board['queen'][i] = -1
board['row'][i] = 0
board['col'][j] = 0
board['nwtose'][j-i] = 0
board['swtone'][j+i] = 0
A function is created to store all devised solutions:
def add_solution(board): # save a solution
global solutions
saved_board = copy.deepcopy(board)
solutions.append(saved_board)
Finally, the main function is created to find all possible solutions using backtracking:
def placequeen(i, board):
n = len(board['queen'].keys()) # number of columns
for j in range(n): # loop over all columns in the row
if is_free(i, j, board):
addqueen(i, j, board) # add queen is spot is free
if i == n-1: # if on last row, add the solution, remove the queen, and return
add_solution(board)
undoqueen(i,j,board)
return
placequeen(i+1, board) # add a queen to the next row
undoqueen(i,j,board) # undo queen placement to find all solutions
Some additional helper methods are also used to take input from the keyboard at the start of the program as well as print all possible solutions once the backtracking algorithm has run its course:
def printsolutions(solutions, size): # print the solutions
print("{} solutions total".format(len(solutions)))
for sol in solutions:
arr = [[0 for i in range(size)] for i in range(size)]
for row in sorted(sol['queen'].keys()):
arr[row][sol['queen'][row]] = 1
print('\n'.join('{}'.format(k) for k in (arr)))
print("---")
def take_input(): # take user input
while True:
try:
size = int(input("Enter the size of the board: "))
if size == 1:
print("Arbitrary solution, enter a number that is at least 4")
if size <= 3:
print("Enter a number that is at least 4")
except ValueError:
print("Please enter numerical value")
else:
break
return size
The algorithm is then run on a board size of the user’s choice using the following script:
solutions = []
size = take_input()
board = {}
initialize(size, board)
placequeen(0, board)
printsolutions(solutions, size)
This implementation of backtracking runs quite rapidly for board sizes <= 10 on my macbook. Be aware that as the size of the board increases, the total amount of possible solutions increases drastically, which results in a longer runtime. The following curve shows just how rapid this growth is:
I hope this post helped guide your intuition behind the n-queens problem, feel free to post your thoughts in the Disqus comments section below.