The 7th Guest: Placing eight queens on a chess board

On the return leg of my Narita to Sydney flight, I was passing time playing the classic DOS game, The 7th Guest. This game was one of the reasons I spent hundreds of dollars buying a CD-ROM drive! Today, it's available in the iTunes Store and the Google Play Store for a fraction of the cost. Today, the only way you'd spend a hundred dollars on this game would be from excess charges on a bad cellular plan.

The 7th Guest broke new ground in 1993: it was one of the first games to ship on a CD-ROM, and it used every megabyte available! You were treated to full motion video as you walked between the rooms of the beautiful haunted house, which was revolutionary at the time. Bill Gates once described it as "the new standard in interactive entertainment". Gamers around the world (including myself) scared themselves half to death as they wandered around the haunted house, solving puzzles and trying to unlock the mystery of the house.

Rated 15 and above. FOR A VERY GOOD REASON.

Enter the Queen's Puzzle: place 8 Queens on a standard 8x8 chess board such that they can't attack each other.

KHALEESI!!!

If you've read this blog, you'll notice I like chess. One of my old hobbies was writing a chess simulator in C.

Chess in C (Part 1)
Chess in C (Part 2) - Insert Pawn Pun Here
Chess in C (Part 3) - Rook, Rooks, Rookies, Wookies, same thing
Chess in C (Part 4) - I'm asking for input
Chess in C (Part 5) - Potential moves of a bishop: up-left, cardinal, pope

When I saw the Queen's Puzzle, my immediate thinking was to write an app that brute forced the solution. The solution space was fairly limited:

          1. Create a 8x8 board
          2. Place a Queen in position (x,y)
          3. Mark each square reachable by the Queen as attackable
          4. Iterate through the remainder of the board until you reach a square that cannot be attacked
          5. Place a Queen in this square
          6. Go to step 4 and repeat until there are 8 Queens on the board.

For step 2, position (x,y) would start as (1,1).
For step 4, the next square that could not be attacked would be position (x+2, y+1). So, if the first Queen is in (1,1), the next Queen would be placed in (3,2).

Unfortunately, I was on a plane and didn't have access to an IDE so I simulated with pen and paper.

Solving problems the old fashion way: pen, paper and swearing.
Queens placed at (1,1), (2,3), (3,5), (4,7), (5,2), (6,4), (7,6) and DARN IT!

Close, but no cigar! Only seven Queens fit. The algorithm fails at step 4: there are no squares that cannot be attacked. I refined the algorithm with two more steps:

          7. Clear the board
          8. Go to step 2, and place a Queen in the next available square.

This meant that instead of placing the Queen in position (1,1), placing it in position (1,2).

Great success!

I solved it and the returned to the next 7th Guest puzzle: swapping the position of 8 bishops on a 4x5 board. That puzzle was AWFUL.

You want to know what's worse than flying 10 hours on a budget carrier that hates you?

More on that in a later blog post.

But, being stuck on 10 hour NRT-SYD flight I thought...what would happen if the chess board was 3D and had a Z-dimension? If you can place 8 Queens on a chessboard of size 8x8, how many Queens can you place on a chessboard of size x-y-z? There is such thing as 3D chess: one of the more common configurations is the Raumschach board which is a 5x5x5 board. The inventor believed that chess should be like warfare: you can be attacked from the plane you are on, but also from above (aerial) and below (underwater).

Board size reduced from 8x8, otherwise you'd spend
months figuring out whether your move was legal.

I started by drawing a 8x8x3 board to get a ballpark idea of the complexity of the problem. Then I placed the 8 Queens on the top layer, and drew the possible attack spaces throughout the other layers.

After diagramming, it becomes clear that there are lots of places for a Queen to hide on an 8x8x3 board. While the Queen can move diagonally over a Z dimension, it has a weakness: the further you are away on the Z dimension, the more clear spots appear. And it's at that point I fell asleep and enjoyed the rest of my flight. The moral of the story: if you need to burn time on a flight, The 7th Guest as a great time waster. But if you want to have hair when you depart the plane, download the strategy guide as well.