There’s a fairly simple puzzle, called The Eight Queens, that I’ve long favored as a project for first semester CS students. The problem is simple enough for a beginner to tackle, yet also interesting enough to be engaging. (And just tricky enough to be a nice beginner challenge.)

Due to a discussion on my other blog, I dug out an old Python implementation I had, and, after looking at it, I thought it might be worth writing a post about. If nothing else, as I said, the problem is interesting enough to be engaging.

The Eight Queens puzzle involves placing eight queens on a chessboard such that no queen can capture another queen in one move.

That amounts to saying each queen must be alone on their row, their column, and both diagonals. An insight helpful to modeling the problem is the realization this means each row and each column must contain exactly one queen.¹

§

What makes this a good exercise for students is that it’s an engaging example of modeling a simple dynamic physical system. And, as a puzzle, it has a definite solution (a set of 92, actually), so a program can be easily validated for correctness.

It’s also complex enough to offer multiple ways of modeling and implementing the puzzle. One intent of this post is to illustrate different approaches.

§ § §

Most approaches model the physical board as some sort of 8×8 data array.

Beginners didn’t always start with object-oriented design, but these days it’s more common, and it’s (I think) especially useful when modeling physical objects.²

So I’ll start with a class that models the chessboard:

Two nice things about this over just using an array: One, we can use tuples to index the board, which seems more natural. Two, indexing off the board is safe; it just returns a zero (or does nothing if trying to assign a value).

Using a class also lets us add row() and col() methods that return an entire row or column of the board. (As you see from the methods, Python makes that easy for rows, but a little more involved for a column.)

§ §

The first implementation looks like this:

Note, firstly, that it’s a recursive function. It places a queen in a given column and then recurses to place a queen in the next column. If it recurses all the way to the last column, all eight queens have been successfully placed, and the board is in a solution state.

The algorithm leverages the fact that each column must have exactly one queen. Therefore, all it needs to do is attempt to place a queen in each column. If it can, it’s found a solution.

Of course, this could be done as an iterative implementation. We could loop over the eight columns rather than recursing. (Most beginners do use an iterative implementation, because it’s easier to understand.)

The advantage of the recursive implementation is that the problem is naturally recursive. We place queens until it’s obvious an earlier placement prevents a solution, so we backtrack to an earlier state, make a change, and try again.

By using recursion, backtracking naturally cleans things up as the stack unwinds.

One gotcha that makes this assignment challenging is the last line. Many students, at least on the first try, forget they need to remove the current queen from the board when trying a new position in a given column.

For students who used an iterative implementation, the need to clean up queens when backtracking can also be an additional gotcha, depending on how they implemented it.

§

The meat, obviously, is in the function, check_board_layout(). Here it is:

It’s a little complicated, and most students would use a more brute force approach, which I admit would be a little clearer, but which I couldn’t bring myself to use.

Basically, the code scans all rows, columns, and diagonals to see if there are too many queens (i.e. more than one).

Rather than actually counting the queens, we just sum the values of a row, column, or diagonal. The sum can only be zero or (one) QUEEN.

Normally I would implement this function as a method of the chessboard class, but I’m using that class in two other examples, and each model has its own approach.

§ §

Speaking of a different approach, one thing that bothers me about the first example is that it checks the entire board every time a queen is placed. That seems like a lot of extra work.

The next example just checks to see if a queen can be legally placed given the current state of the board. Here’s the solver:

It looks a lot like the first one, but it has some obvious changes. For instance, we place a new queen after checking the board, rather than before.

That means we don’t have to remove it unless we successfully placed it. In the first algorithm we placed a queen even if it wasn’t legal and always had to pick it up.

§

This time the meat is in the check_queen_position() function. Here it is:

This obviously works a lot differently than the first one. It explicitly looks for queens in the row, column, or diagonal.

It does it by starting at the position where we want to place the queen and iterating outwards from that coordinate.

This is where having a board we can safely index beyond its borders comes in handy. We don’t need to do any bounds checking here (it’s built into the board).

Bounds checking wasn’t really an issue when we did a board layout check, since we explicitly checked the valid rows, columns, and diagonals.

§ §

Some more clever students take the approach of marking the board rather than checking it. The idea is to mark the rows, columns, and diagonals, of the placed queens. Any square that’s marked can’t have a queen placed on it.

There’s a huge gotcha to this one, though: The requirement to clean up the marks as well as the queens when you try another position or backtrack.

It’s a bit more complicated than it seems at first blush, because more than one queen’s mark can be on a square. For instance, a square might be in one queen’s row, another queen’s column, and yet another queen’s diagonal.

So, it’s important to clean up the marks for a specific queen while leaving potential marks of the others alone.

Here’s the solver for the third version:

It’s basically similar to the first two, but a bit cleaner in not manipulating the board directly here at all. Everything is done by the helper functions.

In particular, add_queen_to_board() and remove_queen_from_board(). Here they are:

We solve the problem of marking and unmarking by using bit masks. The bit used depends on the column of the queen doing the marking.³

Notice how simple the test for whether a queen can be placed is. It only requires that the square be non-zero (i.e.  not marked).

Again we benefit from not having to do bounds checking in this code. (To be clear, since bounds checking is done, the benefit is code clarity and simplicity.)

§ §

The only function missing is the record_board_position() function. Here it is:

It’s pretty basic (and really ought to be part of the chessboard class).

It generates outputs that look like this:

  +---+---+---+---+---+---+---+---+ 
  | Q |   |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+ 
  |   |   |   |   |   |   | Q |   |
  +---+---+---+---+---+---+---+---+ 
  |   |   |   |   | Q |   |   |   |
  +---+---+---+---+---+---+---+---+ 
  |   |   |   |   |   |   |   | Q |
  +---+---+---+---+---+---+---+---+ 
  |   | Q |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+ 
  |   |   |   | Q |   |   |   |   |
  +---+---+---+---+---+---+---+---+ 
  |   |   |   |   |   | Q |   |   |
  +---+---+---+---+---+---+---+---+ 
  |   |   | Q |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+

Which is the first solution (as found by all three versions).

§ § §

And now for something completely different.

The first three implementations model the chessboard and determine if a queen can be placed by checking the simulated rows, columns, and diagonals. These models emulate the physical system.

But this is a logic puzzle that can be abstracted and approached mathematically.

We’re already leveraging the idea that each column must have a queen. We can also leverage the idea that each row must have a queen, too.

An implication of that is we can describe a configuration of queens as a one-dimensional vector (an array or list), where the position in the vector maps to the board column, and the value in that position is the row of the placed queen.

For example, the solution shown above is: [1,5,8,6,3,7,2,4]

Such a list turns out to be easy to check as a valid solution. It must be eight numbers long. It must contain all the digits 1–8 (with no repeats, obviously).

Those two requirements validate rows and columns. What remains is the diagonals, and that takes a bit of explaining. Let’s take a look at the code, first:

The solver function in this case looks a lot different!

We no longer need to pass a col parameter to keep track of the depth of recursion. The length of the accumulator (accum) tells us that. When it contains eight entries, that’s a solution.

As the other solvers do, this one iterates over the possible rows it could place the queen in the current column. Then it recurses to do the same in the next column.

Using a list allows us to append and pop queens from it as they are “placed” and “removed” from the “board.” Recursion provides the necessary backtracking.

§

The check_row() function looks a lot different from the previous examples, too:

The function receives two parameters: the growing solution vector and the row (number) being considered for the next queen.

If that row already exists in the vector, this row is no good. There’s no need to check the column, the process insures one queen per column. That leaves the diagonals.

Note that we only need to check the diagonals in prior columns. No queens are placed to the right (yet), so no need to check the diagonals in the upcoming columns.

The trick to detecting a queen on a diagonal here is realizing the mathematics implied.

Imagine we want to place a queen in row 5 of column 3. That means, on the diagonals, we need the squares in row 4 and row 6 of column 2 to be free. We also need the squares in row 3 and row 7 of column 1 to be free.

The progression of rows depends on how far back we go: 5 – (4,6) – (3,7). The math is simple. Subtract and add the distance in columns to get the diagonal rows.

Those row numbers cannot be in those columns. If they are, that means a queen is on the square.

§

As you might imagine, the solution reporter is a little bit different, too:

Although it’s probably the closest to the earlier versions in that it produces nearly identical output. (The only difference is we also print the vector along with the board.)

§ § §

So there are four implementations of solving The Eight Queens problem.

The first three are what we might call “first approximations,” although the third is a little tricky. The fourth shows how careful consideration of the problem can result in a different approach.

Really all four do the same thing. They all make the same number of checks (7,860), although how they check, and what they check, varies. Because of all those checks, a more efficient way to handle collisions speeds up the algorithm a lot.

As an exercise for the reader, the fourth algorithm doesn’t do column checks and only checks the diagonals behind it. The second and third could equally benefit. I left them naive for simplicity.

As the Wiki article makes clear, considering the problem even more abstractly leads to even more efficient solutions.

Ø

^[1] Because there are eight rows, eight columns, and eight queens. Since no row or column can have more than one, the eight queens have to be distributed one to a row and column.

^[2] Not that I find object hierarchies all that useful all that often (but sometimes). My affection for OOD is due mainly to the data encapsulation. And the metaphor.

^[3] The first queen (column 0) uses 0x1, the second queen uses 0x10, the third queen uses 0x100, and so on.