Previous Next -->
16 Jun 2018

n-queens with O(n) space complexity

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.


Tags:
0 comments