The 8 Queens Problem Revisited

When I was younger I remember seeing this and hearing how difficult it was. And it certainly is. The basic problem is this: place 8 queens on the chess board so that none attacks the other.

Now you can just place one in each row/column and start shifting them around, or you can make educated guesses. Of course, you can brute-force it with a computer, and you can remember a pattern, or even that there is a symmetrical solution etc--but is there a way to *understand* it?

I think so. In fact, I felt like I cheated when I figured it out. Because I said, what the heck, let's see if this works.

The idea is this: queens in the 2x2 center invalidate the most squares. Then queens in the 4x4 center. So can we get away with placing nothing in the 4x4?

........
........
..XXXX..
..XXXX..
..XXXX..
..XXXX..
........
........

Now if you, like me, did too many logic problems with red, blue and green houses, cats/dogs/hamsters as pets, and so forth, you'll recognize--none of the corner 2x2 squares can work! If so, columns 3-6 would need 1 queen in each. But there would only be 3 rows for the 4 queens. Contradiction.

abcdefgh
XX....XX8
XX....XX7
..XXXX..6
..XXXX..5
..XXXX..4
..XXXX..3
XX....XX2
XX....XX1

Wow! There's not much left to try, especially when we invoke symmetry e.g. we consider c8 to be the same as f8 as we can just flip the board horizontally.

Now, let's note the following squares are equivalent: b/g4/5 or d/e2/7. You can rotate the board 90 degrees or flip it until one becomes any of the other. So let's say none of them are possible.

Then either c7 or f7 must contain a queen. But they're mirror images--so, c7. Now g6 or g3 must contain a queen, but c7 takes out g3. Similarly c7 takes out b6, meaning a queen is at b3. That leaves a queen at f2. This is a big problem. We can't have a queen on row 1. c6 negates c1, f2 negates e1/f1, b3 negates d1.

abcdefgh
XX....XX8
XXq...XX7
..XXXXq.6
..XXXX..5
..XXXX..4
.qXXXX..3
XX....XX2
XX....XX1

Therefore, we must have something on a square like d7.

abcdefgh
XX....XX8
XX.q..XX7
..XXXX..6
..XXXX..5
..XXXX..4
..XXXX..3
XX....XX2
XX....XX1

This means the queen on row 8 is at f8. But now if a queen is on b6, that eliminates a6 and a5. d7 eliminates a4, and f8 eliminates a3. Row a cannot have a queen. since the queen cannot be on b5 (d7) or b4 (f8) it is on b3.

abcdefgh
XX...qXX8
XX.q..XX7
..XXXX..6
..XXXX..5
..XXXX..4
.qXXXX..3
XX....XX2
XX....XX1

Note row 2 now has the queen on e2--d7 and f7 take out e2/f2, and b3 takes out c2. That leaves c1 for the queen on row 1.


abcdefgh
XX...qXX8
XX.q..XX7
..XXXX..6
..XXXX..5
..XXXX..4
.qXXXX..3
XX..q.XX2
XXq...XX1


d7 takes out h3, f8 takes out h6, and e2 takes out h5, leaving h4 for the queen. That puts another queen at g6. The remaining queen is at a5.

abcdefgh
XX...qXX8
XX.q..XX7
..XXXXq.6
q.XXXX..5
..XXXX.q4
.qXXXX..3
XX..q.XX2
XXq...XX1

There you go.

An alternative method was to notice that we get close with...

12345678
.......q
.....q..
...q....
.q......
......q.
....q...
..q.....
q.......

Here we try and see if flipping a couple queens will do the trick. There aren't too many possibilities, and I found 8-3(horizontal) and 8-7 worked fine. There are not very many possibilities, as after the first flip, you will see that one of two queens obviously has to be moved. And due to symmetry we can always start by moving one of the upper queens.

So this was an interesting way that trying for a simple cheap way to get through paid off. And if someone ever asks you about this trick, then I hope you can remember either of the ones above. I like the gut-the-center best, as it leaves (at VERY most) 6x12 = 200 possibilities. Why? Column a has 2--5 and 6 being equivalent to 3 and 4, and a5 forces b3 while a6 allows b3/b4 (3 possibilities) with 2 possibilities for g/h. Mirror this for rows 7/8, though c8 is not equivalent to f8 here, and you have at most 72. Well, minus the ones the a/b/g/h diagonals got rid of.

And even then you can remember that the solution mirrors itself over the x axis, which cuts things down totally. Again, symmetry and simplicity.