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”.

Many textbooks are bloated, poorly structured, and badly written. Most seem to be quite useless without an accompanying college course, but if the course is well-taught, you can often skip the textbook altogether. Programming is no exception to this rule. As Python got more popular, the publishing industry started churning out one tome after another, and from what I’ve seen, they are often dreadful.

For a particularly bad example, look at Mark Lutz’s Learning Python, now in its 5th edition. It’s a staggering 1600 pages thick, and full of downright absurd examples that seem to consist of little more than manipulation of strings like “spam” and “egg”, and if you’re lucky, he will throw in the integer “42” as well. Mark Lutz’ book on Python is quite possibly the worst technical book I have ever encountered, but the other books I’ve sampled were not much better.

One thing they all seem to have in common is their inflated page count. I think this is simply a tactic of publishers to justify selling their books for a higher price. Adding another 500 pages costs very little with a decent print run. Yet, all that dead weight allows them to increase their retail price by 100 %. Apparently consumers have been misled to believe that a higher page count means that you’ll get a better bang for your buck, but the opposite is true.

On the other hand, Think Python: How to Think Like a Computer Scientist, in version 2.0.10, hardly exceeds 200 pages. Yet, Allen Downey manages to cover all basic programming constructs, recursion, data structures, and much more. He even details helpful debugging tips, and added a useful glossary for quick lookup of terms you may be unfamiliar with. File I/O got its own chapter. That’s not all. Towards the end of the book, he invites you to explore a GUI toolkit (Tkinter), object-oriented programming, and explains the basics of the analysis of algorithms. The amount of content in this book is quite staggering, especially when compared to its peers. Downey managed to organize his material very well, which resulted in a book that is slim, yet still feels complete.

What I particularly liked about Think Python is that the material is presented in a clear, logical order. Consequently object-orientation shows up very late. In fact, it is introduced as an optional feature. This is how it should be done, if you want to include OOP. For a beginner, “modern” OOP adds unnecessary complexity and makes it harder to form a clear mental model of the problem you are going to solve. On the other hand, competent experienced programmers tend to be highly critical of OOP. You’re probably better off if you never encounter it. That’s not (yet?) a mainstream opinion, though, so you may have to learn OOP eventually.

In a book like Liang’s Introduction to Programming Using Python, you get dozens of exercises at the end of each chapter. Most are a drudgery, focussing on minute details of the language. Often, they are just mere variations of one another, not unlike the mechanical “drills” that are popular in high school mathematics education. But this isn’t even the worst part of it. Nowadays, you can’t just pick up an old edition of a textbook and get basically the same product plus a few typos here and there. No, instead there are changes all over the place, not all of them particularly well-thought out, and the exercises get modified as well. Of course, compulsive updating and rushing a book to release makes it easy for new errors to find their way into the book, as evinced by long lists of errata of every new edition. On a side note, Liang’s books are particularly aggravating since you don’t even get the full book anymore. Instead, a good chunk of the content consists as “bonus chapters” that have to be downloaded by using a code that was printed in the book, presumably as an attempt to make buying used books less attractive.

Compared to that despicable strategy, you can get Downey’s book not only free of charge, but complete too. His exercise are often surprisingly engaging for a beginner’s text. Writing a simple recursive function that checks whether a word is an anagram is not very exciting. On the other hand, processing a text file that contains over 100,000 words, and finding the five longest anagrams in the English language is more involved, and to successfully solve that exercise, you have to draw from previous chapters. This makes Think Python particularly interesting for autodidacts since you can effectively use the exercises to check whether you have gained a firm grasp of the material. There is a reasonable number of exercises in the book, and they are well-chosen. It’s common that they systematically build upon each other. This should be normal for textbooks, but it’s an exception.

Think Python: How to Think Like a Computer Scientist can be freely downloaded at the homepage of the author. The book has been released under a free license. As a consequence, there are editions for different programming languages. Think Python itself is based on an earlier book that covered Java. Being freely available also led to a large audience for this book. Downey acknowledges dozens of people who have made suggestions or pointed out errors in the text. After about a decade, this now leads to Think Python being a very polished book. Of all the introductory Python textbooks I’ve had a look at, it is the only one I feel comfortable recommending. It’s great for complete beginners and also for people who have experience in another language and quickly want to familiarize themselves with Python.