The final project of Coursera’s Introduction to Systematic Program Design – Part 1 was to write a solver for the four queens problem. The goal is to place four queens on a 4 x 4 chess board so that the queens do not obstruct each other. This problem is a simplification of the eight queens problem, and it’s a good exercise for backtracking search. Please note that the Coursera course was using a Lisp dialect as its teaching language. Due to the Coursera honor code I cannot share that solution. However, since some students attempted to rewrite their solution in Python and discussed their approaches on the forum, I decided to port my solution to Python as well and present it here.

Given the limited problem space, there are other approaches to the four queens problem that may be more effective. Those may not teach you about constraint programming or backtracking search, though, and they probably don’t scale that well either. Just have a look at a 4 x 4 chess board: If you have the insight to put the first queen on the second square, then the problem basically solves itself!

To make it a bit easier to transition between the problem description and the eventual Python code, I’ll describe the positions on the board as integers, and not as a letter-integer pair as you’d see it on the chess board. The board therefore turns into:

 0  1  2  3
 4  5  6  7
 8  9  10 11
 12 13 14 15 

Let’s assume you want to implement a proper backtracking algorithm. Say, you start with an empty board. What would you then do? The key idea is to check every square and if this turns out to be unfeasible further down the line, discard that branch of the emerging solution tree and continue from a point that has not yet been explored. Concretely, this means that after the very first iteration of the program, when given an empty board, you’ve created a list of 16 boards, each containing a queen on a different square. The first board in the list has the queen on position 0, the second on position 1, and so on.

Let’s stick with the very first board for the time being. In the second iteration you’d create another list of boards that all contain one queen on square 0, and the second queen on one of the squares 6, 7, 9, 11, 12, 14. Pick any of those boards, put a third queen on them, and you’ll find that it is impossible to place a fourth queen. Seeing that it’s not possible to solve the 4-queens problem if you start with a queen on square 0, you then move on to the next square and try to solve the problem. This is indeed one of the solutions, so the algorithm should present a valid board at the end.

Having illustrated the problem, let’s now talk about one way to code up the solution in Python. I tend to avoid overly terse expressions, apart from a list comprehension here or there, so it should be readable with just a bit of commentary.

To make life a bit easier and the resulting code more readable, I made the following definitions:

B = False
Q = True
all_positions = range(16)

The variable “all_positions” is nothing but a veneer to make the code more legible. It represents the idea that the board is a list with 16 entries.

You might think that it’s silly to define B (for blank) as False and Q (for Queen) as True. However, you can then define a board more succinctly in list form. Here’s what the empty board looks like:

BD0 = [B, B, B, B,
       B, B, B, B,
       B, B, B, B,
       B, B, B, B,]

This list gets evaluated to a list with sixteen “False” entries, but the shorthand introduced above saves some typing and allows for easier illustration of the problem.

A queen attacks in three directions over the whole extent of the board, i.e. horizontally, vertically, and diagonally. Since the board is represented as a list of boolean values, and Python allows for index-based list access, the following definitions can be used to traverse the board easily and check whether there are any collisions:

rows = [ [  0,  1,  2,  3 ],
         [  4,  5,  6,  7 ],
         [  8,  9, 10, 11 ],
         [ 12, 13, 14, 15 ] ]

columns = [ [ 0,  4,  8, 12 ],
            [ 1,  5,  9, 13 ],
            [ 2,  6, 10, 14 ],
            [ 3,  7, 11, 15 ] ]

diagonals = [ [  1,  4 ],
              [  2,  5,  8 ],
              [  3,  6,  9, 12 ],
              [  7, 10, 13 ],
              [ 11, 14 ],
              [  2,  7 ],
              [  1,  6, 11 ],
              [  0,  5, 10, 15 ],
              [  4,  9, 14 ],
              [  8, 13] ]

Please note that this solution does not scale well. It works fine on a 4 x 4 board, but to extend it to an 8 x 8 board, you’d either have to expand the lists with fitting numerical values, or find a way to represent rows, columns, and diagonals as sequence definitions that can be generated automatically, but that’s a problem to look into later. Currently, I’m primarily concerned with an illustration of that particular search problem.

With the preliminaries behind us, I’ll now focus on a general strategy for solving the problem, before filling in the blanks and showing you the source code. The following also serves as a blueprint if you want to go ahead and write the program yourself. I prefer to decompose functions so that they, ideally, achieve one task only. This leads to a greater number of functions, but it makes it easier to reason over code, to debug, and to extend the program later on.

Following the description above, the main steps are something like this:

• 1. enter a starting position (board)
• 2. if that board is solved, return the board
• 3. else: generate a list of boards with all valid subsequent positions, and continue with 1)

This gives rise to the question when a board is valid. To make the code a bit cleaner, I’ll assume that the set of inputs only consists of well-formatted lists, according to the previous specification. A board is valid if there is at most one queen in every column, row, and diagonal, which can be expressed like this:

def board_valid(board):

    def check_entries(entries):
        for entry in entries:
            if number_of_queens(board, entry) > 1:
                return False
        return True
    
    return all([ check_entries(x) for x in [ rows, columns, diagonals ] ])

The function number_of_queens() is defined separately:

def number_of_queens(board, positions):
    return sum([ 1 for pos in positions if board[pos] ])

A board is solved if it is a valid board and if there are exactly four queens on the board:

def board_solved(board):
    return isinstance(board, list) and board_valid(board) \
            and number_of_queens(board, all_positions) == 4 

With those functions in place, everything is set up to solve the problem. I tend to prefer a bottom-up approach when programming, and I visually represent this by putting the most general function last.

# find all empty squares
def get_positions(board):
    return [ x for x in range(len(board)) if not board[x] ]

def get_next_boards(board, positions):
    result = []
    for pos in positions:
        temp = copy.deepcopy(board)
        temp[pos] = True
        result.append(temp)
    return [ board for board in result if board_valid(board) ]

def solve_board(board):
    if board_solved(board):
        return board
    else:
        return solve_board_list(get_next_boards(board, get_positions(board)))
        
def solve_board_list(board_list):
    if board_list == []:
        return False
    else:
        check = solve_board(board_list[0])
        if board_solved(check) != False:
            return check
        else:
            return solve_board_list(board_list[1:])

I think this is quite readable. If the flow of execution is not quite clear, please refer to the description of the problem at the start of the article. Congratulations! You’ve now solved the four queens problem using backtracking search.

The entire code, with test cases and some further helper functions, like a visualizer, a generator for all valid starting positions, and a function that outputs all possible solutions, is available on my github page. Look for the file “4_queens.py”.