I’ve written a lot lately about the physical versus the virtual. I’ve also written about algorithms and the role they play. In this post, I revisit both by exploring what is, for me, an old friend: The Eight Queens Puzzle. The goal is to place eight chess queens on a chessboard such that none can take another in a single move.
The puzzle is simple enough, yet just challenging enough, that it’s a good problem for first-year student programmers to solve. That’s where I met it, and it’s been a kind of “Hello, World!” algorithm for me ever since.
I thought it might be a fun way to explore a simple virtual reality.
To start, for those who don’t play chess (or at least know how the pieces move), there are really only two things to know:
- Chess is played on an 8×8 grid of squares. (A checkerboard!)
- The queen can move any number of (unoccupied) squares in a straight line: horizontally, vertically, or diagonally. (Chess is vaguely feminist in that the queen, by far, is the most powerful piece.)
The puzzle goal of placing eight queens successfully amounts to no queen sharing any row, column, or diagonal.
This leads to some useful logic in approaching the puzzle (at least from a computer’s point of view). I’ll get to that. For now, I’ll stick with the basics.
One thing that makes this a good exercise is that it asks the student to model a physical situation.
So the first step is considering how to solve the puzzle physically. The second step is to figure out how to express that as an algorithm — a precise set of steps to take to produce a solution. As we’ll see, sometimes an algorithm can solve a problem in novel ways not readily accessible to physical solutions.
- Randomly arrange all the elements.
- Are they sorted now?
- If so, we’re done, stop.
- If not, goto step 1…
It’s intended as an example of worst-case sort performance.
Adopting that, we could try a BogoQueens solution:
- Randomly arrange eight queens on the board.
- Are they placed in a solution?
- If so, we’re done, stop.
- If not, goto step 1…
Run long enough (perhaps very long) Bogo solutions will provide an answer.
It also illustrates some important first points about the algorithm we seek:
- If we’re going to “place queens” on a “board” this suggests we need to somehow model a chessboard and chess queens.
- We need to be able to identify what is and isn’t a solution.
- There are hints we need a trial and error approach of some kind.
So even a Bogo solution shows us some of the requirements. (A big one in the context of algorithms is the step-by-step nature of each of those three aspects.)
A less obvious requirement is that, once our algorithm does find a solution, it needs some way to report, print, or display, that solution.
Another thing that makes this a good exercise is that the problem itself is abstract, so it lends itself to an algorithmic approach.
It’s already a logic puzzle, so finding a logical solution really amounts to seeing the problem clearly (also a good exercise for students).
When solving the problem physically, if we take the Bogo approach of randomly placing queens until we hit upon a solution, we’re still using an step-by-step approach (as listed above).
It’s not much of an algorithm, but it is an algorithm. And, as just noticed, it does point to (some involved) sub-steps implied by the major steps. (Also characteristic of algorithms.)
When we develop a more thoughtful and systematic approach, we’re designing a more sophisticated algorithm. It needs all we’ve noted so far, plus a logical approach to the puzzle.
Finding the algorithm means finding that systematic approach. That’s what software designers do.
I explored the actual algorithms on my programming blog. Here I’ll only sketch the basics.
Thinking about the puzzle turns up that, if no queens can share a row or column, then with eight queens on an 8×8 board, it has to be the case that each row and each column has one (and only one) queen.
Therefore, one basic approach is to place a queen in the first row, then one in the second, and so one, one per row, until all eight rows are filled. Assuming the queens are also placed on separate columns and don’t share any diagonals, then placing all eight queens means we have a solution.
So our algorithm might be something like:
- Start in row 1.
- Place a queen in the row.
- Check for collisions with other queens.
- If found, remove queen, and try again.
- Otherwise, if this is row 8, DONE!
- Otherwise, move to next row, goto step 2.
But there’s a bit of a gotcha there. What happens if, for example, we’ve gotten to row 4, and it turns out there is no legal spot on that row to place the queen? Now what?
We have to back-track to row 3 and try a different position with that queen, because it turns out the current spot doesn’t work out.
The same thing — no room at the inn — could happen on row 3, so, potentially, we might back-track all the way to row 1 and try a different starting position.
Fortunately, computers in general, and computer languages in particular, have features that lend themselves nicely to our needs.
Most students implement the chessboard as a two-dimensional array or matrix — something nearly all computer languages provide natively. Those that don’t have reasonable alternatives.
The need to backtrack also turns out to be natural for computers. (I won’t get into it here, but I’m talking about recursion and stacks.)
Once students work through a few gotchas, it’s actually a fairly easy algorithm to create. You just have to think about how you would solve the problem “for real.”
One big piece of this is how a queen is modeled. More importantly, how a queen placed on the board is modeled.
A good analogy here for the board is a spreadsheet (with only 8×8 rows and columns). Placing a queen on the board amounts to putting something a particular spreadsheet cell.
Testing for a legal placement involves looking at the column and diagonals to see if there is a queen already on them. (We’re only placing one queen per row, so no need to check rows.)
As a rule, students create algorithms that reflect the physical reality.
The board is represented by 64 variables in some kind of 8×8 structure. Often a zero means an empty square, and a number (say a one) means a queen is in that square.
Checking placement involves figuring out and checking the columns and diagonals in a systematic way. We’d be checking to see if the squares in question all have zeros (no queens).
Solutions like this very closely resemble (model) the physical reality.
But since, in this case, that physical reality is a logic puzzle — an abstraction — we can consider more abstract approaches.
One characteristic of abstractions is that they have multiple ways of being physically realized. As an extremely trivial example, the number 10 (an abstraction) can be realized as (to name only a few): 10, 2×5, 100÷(3+7), or 11-1.
We’ve already leveraged the idea that placing a queen in every row guarantees no row collisions. What else can we leverage?
Suppose, rather than modeling the board, we make the observation that a solution is a list of eight (rows) where each row has a queen on a different column.
If we number the columns, this amounts to an eight-member list containing the numbers 1–8 in some order. No duplicate numbers means no duplicate columns, so this solves both rows and columns.
We just need to deal with the diagonals, but we have the start of a rather different algorithm:
- Put numbers 1–8 in BAG.
- Start with an empty LIST.
- Take a number from BAG, add it to LIST.
- Check diagonals.
- If LIST has all eight numbers, SUCCESS!
- If FAIL, put number back in BAG.
- Goto #3.
I’m skipping over some nuances (like avoiding reusing the number we just tried), but that’s the gist of it.
As for the diagonals, we can observe that diagonal column numbers differ from the current column by distance. For example, if we’re on column 4, then the diagonals in then next column are 3 and 5 (plus and minus one).
The diagonals two columns away are 2 and 6 (four plus and minus two).
Since no queens are placed “ahead” of us, we just need to check behind us to see if there are “hits” on those column numbers.
(See The Eight Queens on my programming blog for code examples.)
For me, this is part of the joy of programming — finding novel ways to solve a problem using an algorithm.
Back in the late 1980s, in his book Modern Structured Analysis, Edward Yourdon talks a lot about creating computerized solutions for existing physical (typically corporate) processes — “computer automation” as it was once called (and feared).
A point he makes is that the analyst’s job isn’t merely to use the computer to directly replicated the existing process. Computers allow novel, much improved, approaches “outside the box” of the existing physical method.
So a good analyst doesn’t blindly replicate but analyzes and designs.
More to the point here, when it comes to algorithms, there are, indeed, many ways to skin the proverbial cat.
By the way, if you’ve never heard the term before, a “Hello, World!” program is a super simple program — one that just says, “Hello, World!”
Programmers use them as quick tests of a new system or programming language. By extension, the phrase can mean any relatively simple program used mainly as an exercise of some kind.
I often use The Eight Queens when getting to know a new programming language as a way of checking out how expressive the language is. I’ve coded these algorithms in every language I’ve learned!
Stay puzzled, my friends!