## The Seventh Guest Queens Puzzle As Solved By A Nerd

Posted by – March 20, 2012

I played the heck out of The 7th Guest when I was a kid. I was using a Power Mac 6100/60. Ah, those were the days. I do not miss them.

For those that don’t know, The 7th Guest is an entirely pre-rendered game. In other words, you click in a direction to move, and then a pre-rendered movie plays to move you in that direction. Every single frame of the game is a movie. I don’t know if I was limited by my CPU or my 4x CD drive, but the movies did not play smoothly. Sometimes the audio would stutter. The game would pause between receiving a command and playing the movie.

Now I can play the game on my iPhone, and the experience is ridiculously better. I had no idea how horrible the game really played until the first time I moved somewhere and the phone literally flew through the movie, quickly and smoothly. I’d estimate that just moving around takes half the time as it did on my old Power Mac. I suppose this shouldn’t astound me, but it does. Modern cell phones have an astounding amount of processing power and storage space.

I still remember the solutions to the three word puzzles I have encountered so far, which I find amusing. Some puzzles, though…some have solutions I could never have recalled.

Take the queens puzzle. The point is to place 8 queens on a chess board such that no queen could take another. Thus every row, every column, and every diagonal contains exactly one queen. How would you go about solving this problem?

Most people would do a greedy search with a local home-in to the answer. In other words, they’d just start putting queens on the board any which way that works, until they get down to 3, 2, or even 1 queen left and discover that no legal moves remain. Then they start shuffling queens around until they arrive at a solution.

This is what I did the first time(s) I played the game, but this time around I got bored with it pretty quickly. It seemed to me that a computer would do a better job of solving this puzzle than I would. What’s more, it should be able to do so quickly because the problem lends itself to aggressive search space pruning. Every queen placed eliminates a row, column, and two diagonals from the search space, and as soon as we reach an unwinnable board configuration, we can back up and try something else.

Now, I know what you’re thinking. Yes, programming a computer to solve the problem takes a lot longer than the futz-with-it-by-hand method. And yes, I could just look up the solution in the guide book. Shaddup. My way is more fun.

## The Code

Before I show you the code, I’d ask you to keep in mind that this is a quick and dirty PHP script. I may be having fun with this, but that doesn’t mean I’m going to spend a lot of time elegantly designing a great solution. It only needs to work once, and never will it be modified again.

The script recursively searches for a solution by trying to place a queen on the board, checking to see if the result is valid, and if not, moving on to the next untried spot. If an unwinnable state is reached, the recursion lets us back up and try a different configuration. This approach is, in this case, quite fast—it produces a correct solution as close to instantaneously as makes no difference on my 4-year-old MacBook Pro.

## No, look, seriously, the code

<?php
function newBoard()  {
\$board = array();
for (\$i = 0; \$i < 8; ++\$i)  {
\$board[] = array();

for (\$j = 0; \$j < 8; ++\$j)  {
\$board[\$i][\$j] = 0;
}
}

return \$board;
}

function isValidMove(\$board, \$row, \$col)  {
\$board[\$row][\$col] = 1;

return boardIsValid(\$board);
}

function boardIsValid(\$board)  {
// Check rows, columns, and diagonals
for (\$i = 0; \$i < 8; ++\$i)  {
\$rowOneCnt = 0;
\$colOneCnt = 0;
\$diagOneCnt = 0;
for (\$j = 0; \$j < 8; ++\$j)  {

if (\$board[\$i][\$j] == 1)  \$rowOneCnt++;
if (\$board[\$j][\$i] == 1)  \$colOneCnt++;

// Up left diagonal
// This is the only loop that checks the current square (\$board[\$i][\$j])
for (\$di = \$i, \$dj = \$j;
\$di >= 0 && \$dj >= 0;
--\$di, --\$dj)
{
if (\$board[\$di][\$dj] == 1)  \$diagOneCnt++;
}
// Up right diagonal
for (\$di = \$i-1, \$dj = \$j+1;
\$di >= 0 && \$dj < 8;
--\$di, ++\$dj)
{
if (\$board[\$di][\$dj] == 1)  \$diagOneCnt++;
}
// Down left diagonal
for (\$di = \$i+1, \$dj = \$j-1;
\$di < 8 && \$dj >= 0;
++\$di, --\$dj)
{
if (\$board[\$di][\$dj] == 1)  \$diagOneCnt++;
}
// Down right diagonal
for (\$di = \$i+1, \$dj = \$j+1;
\$di < 8 && \$dj < 8;
++\$di, ++\$dj)
{
if (\$board[\$di][\$dj] == 1)  \$diagOneCnt++;
}

if (\$diagOneCnt > 1 && \$board[\$i][\$j] == 1)  {
return false;
}
\$diagOneCnt = 0;
}
if (\$rowOneCnt > 1 || \$colOneCnt > 1)  return false;
}

return true;
}

function findWin(\$board, \$row = 0)  {
if (\$row > 7)  {
if (boardIsValid(\$board))
return \$board;
else
return false;
}

// Starting position on current row
for (\$startPos = 0; \$startPos < 8; ++\$startPos)  {
if (isValidMove(\$board, \$row, \$startPos))  {
\$board[\$row][\$startPos] = 1;

\$result = findWin(\$board, \$row+1);

if (\$result !== false)  return \$result;
else  \$board[\$row][\$startPos] = 0;
}
}

return false;
}

function printBoard(\$board)  {
for (\$i = 0; \$i < 8; ++\$i)  {
for (\$j = 0; \$j < 8; ++\$j)  {
echo \$board[\$i][\$j] . ' ';
}
echo "\n";
}
}

\$board = findWin(newBoard());
printBoard(\$board);

?>

### 8 Comments on The Seventh Guest Queens Puzzle As Solved By A Nerd

1. Alex says:

Meh. Could’ve done it in one line with PERL… :p

2. Ryan says:

Heh. I would very much like to see that.

3. Marisol says:

I see you share interesting things here, you can earn some additional cash, your website has big potential, for the monetizing method, just type in google – K2 advices how to monetize a website

4. Etta says:

I read a lot of interesting content here. Probably you spend a lot of time writing, i know how to save you a lot of time, there is an online tool that creates readable, google friendly articles in minutes, just type in google – laranitas free content source

5. Elizbeth says:

I read a lot of interesting posts here. Probably you spend a lot of time writing, i know how to save you a lot of time, there is an online tool that creates readable, google friendly articles in minutes, just type in google – laranitas free content source

6. weight loss says:

Awesome articles you post on your blog, i have shared this post on my twitter

7. slots online says:

Hi admin of this site, do you allow guest posting ? Please let me know, i am interested .

8. You have got one of the better online sites.