The Eight Queens

One solution to the puzzle.

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:

  1. Chess is played on an 8×8 grid of squares. (A checkerboard!)
  2. 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.

In the world of sorting (and believe me, there is a large world of sorting), there is something called the BogoSort. It goes like this:

  1. Randomly arrange all the elements.
  2. Are they sorted now?
  3. If so, we’re done, stop.
  4. If not, goto step 1…

It’s intended as an example of worst-case sort performance.

Adopting that, we could try a BogoQueens solution:

  1. Randomly arrange eight queens on the board.
  2. Are they placed in a solution?
  3. If so, we’re done, stop.
  4. 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 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:

  1. Start in row 1.
  2. Place a queen in the row.
  3. Check for collisions with other queens.
  4. If found, remove queen, and try again.
  5. Otherwise, if this is row 8, DONE!
  6. 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.

§

Yet another

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:

  1. Put numbers 1–8 in BAG.
  2. Start with an empty LIST.
  3. Take a number from BAG, add it to LIST.
  4. Check diagonals.
  5. If LIST has all eight numbers, SUCCESS!
  6. If FAIL, put number back in BAG.
  7. 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!

About Wyrd Smythe

The canonical fool on the hill watching the sunset and the rotation of the planet and thinking what he imagines are large thoughts. View all posts by Wyrd Smythe

12 responses to “The Eight Queens

  • Wyrd Smythe

    There are many nuances I skipped over, such as how a naive solution will find all solutions, including reflections and rotations. A more sophisticated algorithm finds only the unique solutions.

    For example, an easy way to eliminate a whole group of reflections is to only place a queen in columns 1-4 in the first row. (Just stop after finding all solutions with a row 1 queen in columns 1-4.) It turns out a solution with a queen in, say, column 8 is a reflection of the same solution with the queen in column 1. (Likewise, 7 reflects 2, 6 reflects 3, and 5 reflects 4.)

    I’ll leave finding rotations as an exercise for the reader. 😀

  • SelfAwarePatterns

    On “Hello World” programs, every time it comes up, I think about my first look at the “Hello World” for the Windows API (about two printed pages). It got a little simpler with Win32, but not much. A far cry from the 1-5 lines of console programs.

    • Wyrd Smythe

      Yeah, graphical windowing environments are a lot more complicated. With Windows, you need the message pump and all the cruft necessary to create a window.

      But if you think that’s bad, try doing “Hello, World!” in raw Unix X-Windows. That’s more like four or five pages. A real nightmare. (Fortunately, most use the various toolkits, but it’s still always more complicated in a graphical environment.)

      Even Visual BASIC, if you look at the code behind a “form” isn’t a lot better. It just isolates most users from the cruft.

      • SelfAwarePatterns

        I should note those two pages didn’t include the resource files you had to create, which actually specified the window layouts.

        I never did X-Windows, although someone told me they didn’t find it that bad, but they might have been using one of the toolkits. In truth, by the late 90s, hardly anyone did raw Win32. Most C++ programmers used MFC, which as long as you didn’t try to actually understand it, was much easier to work with.

        But modern business apps, while less technical, are arguably just as involved. These days you have to be familiar with HTML, Javascript and its various frameworks and libraries, a back end technology like Java, C# or PHP, and their various frameworks and libraries, usually some kind of database, and probably web service protocols. Sometimes I’m glad I don’t code anymore.

      • Wyrd Smythe

        (One could get away without the RC file if there was only one window and no custom app icon, but that was pretty limiting.)

        I’ve done assembly-level coding as long as I’ve been coding, and I’ve done a lot of low-level network and graphics coding, so I’m more used to getting my hands dirty than many programmers. Plus, I sometimes have a bad case of “not invented by me” when it comes to code and tend to use libraries grudgingly. Which is all to say I never liked the MFC classes (or even the standard C++ library classes — too butt-ugly some of them) and tended to avoid them as much as possible. (But most of my C++ Windows stuff was utility-level, no major apps. I used VB for the major stuff — much faster development cycle. They like that in corporations.)

        It really surprised me how JavaScript (ECMA-262 in most cases) became THE embedded language for custom app programming. I knew it as a simple automation language for websites, and then, bang, it’s all over the place, embedded in the damnedest places. That said, it’s a great language. I used to recommend it as a first language for people who wanted to learn programming. (For one thing, Notepad and IE were all you needed. For another, 100% object-oriented. Not even Java is.) Now I recommend Python — it’s freedom.

        Speaking of which, Java was surprising, too. I’d met that as a silly language for silly web “applets” — and kind of a weird language in some ways (what do you mean main() has to be in a class? what??). Next thing I know, it’s THE corporate programming platform. (We did a lot of J2EE, so I guess it made sense. I did come to love it.) True what you say about DBs. I did a lot of SQL. (Still do some. I like DBs. When I found out Python comes with SQLite, I was in heaven.)

        I’ve managed to avoid C#, and I’ve not used PHP, although I did join the Perl cult for a while. I got over it — Perl source code really does look a bit like line noise. I used to be attracted to the idea of symbols in a programming language (ever heard of APL? 😀 ), but Perl cured me of that.

        For me, programming was like science fiction. Something I took to immediately, and embraced as part of my very identity. There’s good reason the tag line on my programming blog is, “I just can’t stop writing code!” (My love of programming is why I started that blog. Otherwise I’d write about it too much here. The math and baseball posts are bad enough.)

      • Wyrd Smythe

        p.s. The hidden punchline on the xkcd cartoon? That was exactly my reaction. Perl and Python occupy the same “script language” niche, and Perl didn’t stand a chance. (Like an ice cube in a blast furnace doesn’t stand a chance.)

      • SelfAwarePatterns

        Java’s rise as the new COBOL surprised me too. Although it’s always felt a bit top down, and reflexively anti-Microsoft. And its paternalistic nature toward coding has always irked me.

        Python’s rise on the other hand, feels completely bottom up. It’s starting to permeate corporate culture, but only have several years of permeating scientific and geek culture. It won’t surprise me too much if most coding is done in it 10 years from now, although by then there will probably be some new language starting to work its way up.

        Can’t say I was ever a Perl fan. Perl code to me looks like something exploded and splatted all over the source file. Pathologically Eclectic Rubbish Lister has always struck me as the right backonym for it. Someone recently show me a very maintainable looking Perl program, but it was the first I could ever recall seeing. I was very happy to see other languages eclipse it.

        I had the coding bug for a long time, but it faded as I got older and my job responsibilities shifted. (As did the gaming bug.) Although I do sometimes miss the feeling of coming up with a good programming solution.

      • Wyrd Smythe

        “Although [Java has] always felt a bit top down, and reflexively anti-Microsoft.”

        😀 Hence C# — Java for Microsofteans! 😛

        Now that you say that, Java did seem like it became a serious language after it was mandated as an Enterprise language. The language itself grew and evolved, and the various Java libraries got really powerful. (I did like the whole JAR file thing. Sort of like DLLs you didn’t have to bother the O/S with.)

        (DataBridge, and another, DataCollector, were the crown jewels in my Java cap. I was (and am) unreasonably proud of those apps. They were serious work horses. (And corporate ass-savers, as it turned out.))

        “…although by then there will probably be some new language starting to work its way up.”

        There already are contenders. (I’ve been seeing a lot of headlines about RUST being the hot new thing, but haven’t explored it yet.)

        “Someone recently show me a very maintainable looking Perl program, but it was the first I could ever recall seeing.”

        Ha, yeah, I can imagine. What made it maintainable? Lots of comments? Long descriptive variable names?

        I think maybe one mark of both a good programmer and a good language is that you can return to code you wrote a year ago and easily make sense of it. (I’ve learned the hard way to make that sort of thing as easy as possible on myself. Defensive coding!)

        “Although I do sometimes miss the feeling of coming up with a good programming solution.”

        For me, it satisfies my creative urges. The film career I originally intended flamed out early (or, perhaps, rather I bailed out after deciding various odds were too high against success — same as with a musical career). I’ve recently realized why I never found fiction writing compelling despite my fascination with storytelling (and with reading): I’m too much of a misanthrope to actually want to write about the lives of people.

        But coding is perfect for an alienated misanthropic loner! The irony is that what was a favorite hobby became my career. That whole arc started out as hardware for me (I was a service tech) but evolved when I realized what else I could bring to the table. (It’s the one thing in life that worked out super well.)

        I will say that, with Java (and with C++ many years earlier), I got to the point where it wasn’t fun with those languages. Too many times writing the same damned for{…} loop to do something trivial. With Python, that changed. Functions like reversed(), sorted(), sum(), max(), etc. are built in!

        I’d have to have a very good reason to use Java or C++ again.

      • SelfAwarePatterns

        “What made it maintainable? Lots of comments? Long descriptive variable names?”

        That and tons of whitespace. The one vulnerability I could see is that the comments were long, in many cases spanning a whole page before the code they pertained to, something that’s very easy to fall out of sync.

        “I think maybe one mark of both a good programmer and a good language is that you can return to code you wrote a year ago and easily make sense of it.”

        Definitely. The problem is everyone thinks their own code is self documenting, but maintenance programmers virtually never agree, including as you note, the programmer themselves a couple of years later.

        I never seriously got into Python. But if I ever seriously get the urge to code something, it’ll probably be what I reach for. (Unless something else has replaced it by then!)

      • Wyrd Smythe

        “That and tons of whitespace.”

        Ah, yes; whitespace is another good one.

        A trick I borrowed from “literary programming” is that the order of functions in a file, or the order of methods in a class, participates in documenting that file. It’s a matter of how things are grouped (similar things together) and a logic in those groups.

        “…but maintenance programmers virtually never agree,…”

        I’ve been that guy. (A few times it was easier to start fresh and copy-paste the few bits that had any value.)

        Being in that position enough times, either with other code or your own, tends to give you better habits. It’s especially embarrassing when you can’t figure out what the hell you were thinking five years ago.

        I’m especially embarrassed about a C macros phase I went through at one point:

        #define OKAY    (0)
        #define IS      ==
        #define ISNT    !=
        #define NOT     !
        #define AND     &&
        #define OR      ||
        
        #define isNOT(x)    if((x)==0)
        #define isNULL(x)   ((x)==(NULL))
        #define notNULL(x)  ((x)!=(NULL))
        

        Shudder!

      • SelfAwarePatterns

        Yikes! Yeah, I don’t think I would have liked those.

        The worst use of C macros I ever saw was to use them to obscure pointer arithmetic, which he used when he could have easily gotten by with array notation. I was an experienced C programmer when I came across it, but the resulting code, which was several thousand lines, was undecipherable, and I was in a hurry at the time. Which meant I “fixed” it by bypassing the code in the specific conditions where the bug, wherever it was, was manifesting. Not my proudest maintenance moment. (I did document it in an epic comment, which included my opinions about that use of macros.)

      • Wyrd Smythe

        You took that all-important first step: Make it work. (According to what I was told was an AT&T thing, steps two and three are: Make it work right. Make it work fast. To which I always want to add: “If you have time.” So often, you only have time for step one.)

        In both cases, those macros are rewriting the language, which is Bad Practice. At least I didn’t go this far:

        #define BEGIN   {
        #define END     }
        

        Which I have seen (an attempt to make C look Pascal-ish).

And what do you think?

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: