Month: March 2012

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);

?>