Generate a minesweeper board which doesn't need guessing

Question

I am designing a Minesweeper-like game (with modified rules), and I want to prevent player from guessing. My goal is: The generated board is with few revealed squares, and player can solve the entire puzzle without any guessing.

Wikipedia mentioned:

Some implementations of Minesweeper will set up the board by never placing a mine on the first square revealed, or by arranging the board so that the solution does not require guessing.

However, I cannot figure out the algorithm.

Besides, in another StackOverflow question: Minesweeper solving algorithm

Improvement: Run the solver alongside the generator, making sure that the puzzle has a unique solution. This takes some cleverness, and isn't done in most variants.

I doubt if this really works. It's well-known solving minesweeper is NP-complete.

In summary, my questions are:

• How to generate a Minesweeper board which doesn't need any guessing?
• If we can, what's the concrete algorithm?
• Could we solve this problem in polynomial time deterministically? Is this problem NP-complete? How to prove it?

Answer 1

The implementation of Minesweeper in Simon Tatham's Portable Puzzle Collection is guessing-free. (It's also MIT licensed, so you're free to copy his implementation if you so desire.)

Answer 2

It's well-known solving minesweeper is NP-complete.

This is true but perhaps not as relevant as you think. The proposed algorithm is something like "repeatedly generate random boards until the computer can solve one". NP-hardness is a property of the worst case, but here we're really interested in the average-case hardness. If an unusually hard board is generated, we can time out the solver and restart with a new board.

Also, even if there were an oracle to distinguish good boards from bad, would you really want the user to have to solve a hard problem in order to avoid guessing? A less talented computer solver might bias the choice toward fairer boards.

Answer 3

Disclaimer: This may or may not be entirely correlated, but it's something neat I noticed, and might be useful to others trying to find the answer.

In minesweeper, there's a neat little thing I found when looking at different minesweeper boards: In the game, when generating a board, all non-mine squares have their value set to the number of neighboring mines. However, you can apply the same thing, but in reverse: All mines add 1 to the value of each neighboring space. This makes it possible to think of mines less like mines, and more like layered 3x3 squares. To demonstrate, here's a board, stripped of any neighboring mine counts:

....x
.x...
x..x.
..x..
x...x

If we use the normal generation method, setting the value of each non-mine tile to the number of neighboring mine tiles, we get:

1111x
2x222
x33x1
23x32
x212x

So what's the issue with using this method? Well, it has to do with just how many times we're checking for a mine. Let's see:

1111x  -  took 23 checks
2x222  -  took 31 checks
x33x1  -  took 26 checks
23x32  -  took 31 checks
x212x  -  took 20 checks

Ouch. That comes in at a total of 131 checks. Now, let's try the square method:

1111x  -  took 8 checks
2x222  -  took 13 checks
x33x1  -  took 18 checks
23x32  -  took 13 checks
x212x  -  took 11 checks

This method is much faster, with a total of only 63 checks, less than half of the naïve method.

These "squares" can also be utilized when solving boards. For example:

0000
?110
??10
???0

In this example, we can clearly see a corner, and therefore a square, with a mine in the center (+ and - are queued opens and flags):

0000
?110
?-10
???0

We can also expand the corner, since there isn't another square on top of it:

0000
+110
+-10
?++0

However, we cannot expand the last ? in the same way until we uncover all the queued tiles. Just as an example, I'm going to use some twos:

0000
1110
2x10
?210

Now we can see another corner, and it turns out that it intersects a mine. This can be hard to spot, but this is a corner.

One thing to watch out for, though, is something like this:

00000
01110
12x10
x?210
2x100

In this scenario, there are 3 squares. The 4x4 region in the top right matches the previous scenario, but don't get fooled: the twos from earlier are part of two separate squares in this one, and the unknown tile happens to be a three. If we had placed a mine there, the twos would be complete, and we would have lost to misjudgment, trying to uncover a tile that seems safe.

TL;DR: Mines can be thought of as layered 3x3 squares, which can save time when generating and/or solving.

Answer 4

I realize this question is rather old but figured I'd add an answer that is a bit different from the other answers and can result in fairly performant minesweeper board generation. Also, I'm including fully functional source code, albeit lacking comments and my usual professional polish and isn't quite complete.

We'll use the following numbers to indicate certain conditions:

• -1 to indicate open spaces that are guaranteed to be empty and free (permanent).
• 0 to indicate a space that could be open or contain a mine (non-permanent).
• 1 to indicate a possible mine position (non-permanent).
• 2 to indicate a permanent mine position (permanent).

The first step is to reserve the starting position and the surrounding 8 spaces with -1 and then randomly generate a board filled with possible mines. This is the easy part. The key is to then solve the board internally before presenting it to the user.

Before entering the solver phase, find all the points with no mines in the region from the starting position and flag them as points of interest to resolve.

For the solver phase, solve as much as possible using logic rules until hitting a wall. The solver can be as simple or as complex as desired but players prefer reasonably simple rules of deduction over having to do a deep analysis to figure out mine positions. There are two types of deduction rules: Known mine positions and known empty spaces.

The first rule is obvious: All mines for the surrounding spaces have been found. Open the remaining spaces and mark them as points of interest. Mark the current point as done.

The next rule is also obvious: All surrounding spaces have been filled and the only remaining spaces are mines. Fill spaces with permanent mines. Mark the current point as done.

After that, things get a bit trickier. The next most common pattern is "1 2 1" with 3 adjacent unknown spaces (after counting up the mines left for the adjacent points). When that pattern is encountered either vertically or horizontally, then there can't be a mine in the middle space and the other two spaces have to be the mines.

From here, there are a couple of other logic rules that can be applied that are rather complex to explain but don't require recursion or testing a bunch of different points. I'll try to do my best:

The first complex rule is to open logically impossible positions where only one mine can be placed in two different adjacent spots, but there are three open adjacent spaces in a row/column (i.e. open the third spot). For example, for a logical "1 1 ?" there has to be a mine in one of the two 1 positions and the ? has to be an open space.

The other complex rule is to open logically impossible positions where only one mine can be placed in two different spots, but the adjacent space has only one mine and more than the same two possible spots (i.e. the rest are clear). For example:

???
?11
?1

When working with the point in the middle, the left three ? can't be mines and therefore have to be open spaces because there has to be a mine in the other two spaces.

I think those more complex rules become more apparent after generating a bunch of boards and encountering them for the first time.

All of those rules are doable with just working with the current point of interest and not going crazy with recursion or anything more complex.

Okay, now let's say the solver hits a wall in the logic and doesn't open any new spaces and doesn't know for certain about any more mines. The solution is to randomly move one or more non-permanent mines to a non-permanent location somewhere else on the board. This has the unfortunate tendency to push some mines to the edges and corners but it otherwise works fairly well. Doing this may also rarely cause earlier solved locations to become unsolvable.

The next step is to fill in spaces that were unreachable with mines (i.e. change 0's to 1's).

If the solver moves any mines, reset -1's to 0's and 2's to 1's, reopen the starting position, and start the solver over again until no more mines are moved. Also, if the output ever results in more than a 20% overfill of the target number of mines, then it's almost certain that the majority of the board got cut off with mines. For those situations, just start over with a brand new board. It takes less than 1 second to generate and solve a decent sized board internally using this algorithm in most programming/scripting languages. So the player can afford to wait for an extra half second.

I haven't looked at Simon Tatham's algorithm but I've played his mobile Mines minigame in his puzzle collection enough to know that it has a tendency to have a bunch of mines on the outer edges and corners. So it's likely that his algorithm does something similar to the above.

Here's a quick and dirty implementation in PHP of most of the algorithm shown above (mainly it doesn't do the last step and repeat the solver loop, which results in slightly less than perfect results - an exercise for you to implement on your own):

<?php
    // Quick and dirty PHP code example for minesweeper board generation.
    $boardx = 9;
    $boardy = 9;
    $boardmines = 23;

    $board = array();
    for ($y = 0; $y < $boardy; $y++)
    {
        $row = array();

        for ($x = 0; $x < $boardx; $x++)  $row[] = 0;

        $board[] = $row;
    }

    $used = $board;

    $sboard = $board;
    $sused = $board;

    $startx = mt_rand(0, $boardx - 1);
    $starty = mt_rand(0, $boardy - 1);

//$startx = 8;
//$starty = 8;

    $board[$starty][$startx] = -1;

    function GetTotalMines(&$board)
    {
        global $boardx, $boardy;

        $num = 0;

        for ($y = 0; $y < $boardy; $y++)
        {
            for ($x = 0; $x < $boardx; $x++)
            {
                if ($board[$y][$x] > 0)  $num++;
            }
        }

        return $num;
    }

    function GetMaxMinesAllowed(&$board)
    {
        global $boardx, $boardy;

        $num = 0;

        for ($y = 0; $y < $boardy; $y++)
        {
            for ($x = 0; $x < $boardx; $x++)
            {
                if ($board[$y][$x] == 0)  $num++;
            }
        }

        return $num;
    }

    function PlaceRandomMines(&$board, $numleft)
    {
        global $boardx, $boardy;

        $num = GetMaxMinesAllowed($board);

        if ($numleft > $num)  $numleft = $num;

        while ($numleft)
        {
            do
            {
                $posx = mt_rand(0, $boardx - 1);
                $posy = mt_rand(0, $boardy - 1);
            } while ($board[$posy][$posx] != 0);

            $board[$posy][$posx] = 1;

            $numleft--;
        }
    }

    function ClearPoint(&$board, $posx, $posy)
    {
        global $boardx, $boardy;

        $num = 0;

        for ($y = $posy - 1; $y < $posy + 2; $y++)
        {
            if ($y > -1 && $y < $boardy)
            {
                for ($x = $posx - 1; $x < $posx + 2; $x++)
                {
                    if ($x > -1 && $x < $boardx)
                    {
                        if ($board[$y][$x] > 0)  $num++;

                        if ($board[$y][$x] < 2)  $board[$y][$x] = -1;
                    }
                }
            }
        }

        PlaceRandomMines($board, $num);
    }

    function GetNumMinesPoint(&$board, $x, $y)
    {
        global $boardx, $boardy;

        $num = 0;

        if ($x > 0 && $y > 0 && $board[$y - 1][$x - 1] > 0)  $num++;
        if ($y > 0 && $board[$y - 1][$x] > 0)  $num++;
        if ($x < $boardx - 1 && $y > 0 && $board[$y - 1][$x + 1] > 0)  $num++;

        if ($x > 0 && $board[$y][$x - 1] > 0)  $num++;
        if ($x < $boardx - 1 && $board[$y][$x + 1] > 0)  $num++;

        if ($x > 0 && $y < $boardy - 1 && $board[$y + 1][$x - 1] > 0)  $num++;
        if ($y < $boardy - 1 && $board[$y + 1][$x] > 0)  $num++;
        if ($x < $boardx - 1 && $y < $boardy - 1 && $board[$y + 1][$x + 1] > 0)  $num++;

        return $num;
    }

    function OpenBoardPosition(&$points, &$board, &$dispboard, $x, $y)
    {
        global $boardx, $boardy;

        $dispboard[$y][$x] = ($board[$y][$x] > 0 ? $board[$y][$x] : -1);

        $points[] = array($x, $y);

        if (!GetNumMinesPoint($board, $x, $y))
        {
            if ($x > 0 && $y > 0 && $dispboard[$y - 1][$x - 1] == 0)  OpenBoardPosition($points, $board, $dispboard, $x - 1, $y - 1);
            if ($y > 0 && $dispboard[$y - 1][$x] == 0)  OpenBoardPosition($points, $board, $dispboard, $x, $y - 1);
            if ($x < $boardx - 1 && $y > 0 && $dispboard[$y - 1][$x + 1] == 0)  OpenBoardPosition($points, $board, $dispboard, $x + 1, $y - 1);

            if ($x > 0 && $dispboard[$y][$x - 1] == 0)  OpenBoardPosition($points, $board, $dispboard, $x - 1, $y);
            if ($x < $boardx - 1 && $dispboard[$y][$x + 1] == 0)  OpenBoardPosition($points, $board, $dispboard, $x + 1, $y);

            if ($x > 0 && $y < $boardy - 1 && $dispboard[$y + 1][$x - 1] == 0)  OpenBoardPosition($points, $board, $dispboard, $x - 1, $y + 1);
            if ($y < $boardy - 1 && $dispboard[$y + 1][$x] == 0)  OpenBoardPosition($points, $board, $dispboard, $x, $y + 1);
            if ($x < $boardx - 1 && $y < $boardy - 1 && $dispboard[$y + 1][$x + 1] == 0)  OpenBoardPosition($points, $board, $dispboard, $x + 1, $y + 1);
        }
    }

    function GetMinesAtPoint(&$board, $x, $y)
    {
        global $boardx, $boardy;

        $points = array();

        if ($x > 0 && $y > 0 && $board[$y - 1][$x - 1] > 0)  $points[] = array($x - 1, $y - 1);
        if ($y > 0 && $board[$y - 1][$x] > 0)  $points[] = array($x, $y - 1);
        if ($x < $boardx - 1 && $y > 0 && $board[$y - 1][$x + 1] > 0)  $points[] = array($x + 1, $y - 1);

        if ($x > 0 && $board[$y][$x - 1] > 0)  $points[] = array($x - 1, $y );
        if ($x < $boardx - 1 && $board[$y][$x + 1] > 0)  $points[] = array($x + 1, $y);

        if ($x > 0 && $y < $boardy - 1 && $board[$y + 1][$x - 1] > 0)  $points[] = array($x - 1, $y + 1);
        if ($y < $boardy - 1 && $board[$y + 1][$x] > 0)  $points[] = array($x, $y + 1);
        if ($x < $boardx - 1 && $y < $boardy - 1 && $board[$y + 1][$x + 1] > 0)  $points[] = array($x + 1, $y + 1);

        return $points;
    }

    function GetAvailablePoints(&$board, $x, $y)
    {
        global $boardx, $boardy;

        $points = array();

        if ($x > 0 && $y > 0 && $board[$y - 1][$x - 1] == 0)  $points[] = array($x - 1, $y - 1);
        if ($y > 0 && $board[$y - 1][$x] == 0)  $points[] = array($x, $y - 1);
        if ($x < $boardx - 1 && $y > 0 && $board[$y - 1][$x + 1] == 0)  $points[] = array($x + 1, $y - 1);

        if ($x > 0 && $board[$y][$x - 1] == 0)  $points[] = array($x - 1, $y);
        if ($x < $boardx - 1 && $board[$y][$x + 1] == 0)  $points[] = array($x + 1, $y);

        if ($x > 0 && $y < $boardy - 1 && $board[$y + 1][$x - 1] == 0)  $points[] = array($x - 1, $y + 1);
        if ($y < $boardy - 1 && $board[$y + 1][$x] == 0)  $points[] = array($x, $y + 1);
        if ($x < $boardx - 1 && $y < $boardy - 1 && $board[$y + 1][$x + 1] == 0)  $points[] = array($x + 1, $y + 1);

        return $points;
    }

    function DumpBoard($board)
    {
        global $boardx, $boardy;

        for ($y = 0; $y < $boardy; $y++)
        {
            for ($x = 0; $x < $boardx; $x++)
            {
                if ($board[$y][$x] > 0)  echo "* ";
                else
                {
                    $num = GetNumMinesPoint($board, $x, $y);

                    if ($num)  echo $num . " ";
                    else  echo ". ";
                }
            }

            echo "    ";

            for ($x = 0; $x < $boardx; $x++)
            {
                if ($board[$y][$x] == -1)  echo "x ";
                else if ($board[$y][$x] == 0)  echo ". ";
                else if ($board[$y][$x] == 1)  echo "* ";
                else if ($board[$y][$x] == 2)  echo "! ";
                else  echo "? ";
            }

            echo "\n";
        }

        echo "\n";
    }

    // Initial setup.
echo "Hi: 1\n";
    ClearPoint($board, $startx, $starty);
echo "Hi: 2\n";
    PlaceRandomMines($board, $boardmines);
echo "Hi: 3\n";

/*
// Start at 2, 2.
$board = array(
    array(1, 0, 0, 1, 1, 1, 1, 0, 1),
    array(1, -1, -1, -1, 0, 1, 0, 1, 1),
    array(0, -1, -1, -1, 0, 1, 0, 0, 1),
    array(0, -1, -1, -1, 0, 0, 0, 0, 0),
    array(0, 0, 0, 0, 1, 0, 0, 0, 0),
    array(0, 0, 0, 0, 0, 1, 1, 0, 0),
    array(1, 0, 1, 1, 1, 1, 0, 0, 0),
    array(1, 0, 0, 0, 0, 0, 0, 0, 0),
    array(0, 0, 0, 0, 0, 1, 0, 1, 1),
);

// Start at 2, 2.
$board = array(
    array(1,  0,  0,  0, 1, 1, 0, 0, 0),
    array(0, -1, -1, -1, 0, 0, 0, 1, 0),
    array(1, -1, -1, -1, 0, 1, 0, 0, 0),
    array(0, -1, -1, -1, 0, 0, 0, 1, 1),
    array(0,  0,  1,  0, 0, 0, 1, 0, 0),
    array(0,  1,  0,  1, 0, 0, 0, 0, 0),
    array(1,  0,  1,  1, 0, 0, 1, 1, 1),
    array(0,  0,  0,  0, 0, 1, 0, 0, 0),
    array(0,  1,  0,  0, 1, 0, 0, 1, 1),
);

// Start at 8, 8.
$board = array(
    array(0, 0, 0, 0, 0, 1, 0, 1, 0),
    array(0, 0, 1, 0, 0, 0, 1, 1, 0),
    array(0, 0, 0, 1, 0, 1, 0, 0, 0),
    array(0, 0, 0, 0, 0, 1, 0, 0, 1),
    array(0, 0, 0, 1, 0, 1, 0, 0, 0),
    array(0, 0, 1, 0, 1, 1, 1, 0, 1),
    array(0, 0, 0, 0, 1, 0, 0, 0, 1),
    array(0, 0, 1, 0, 0, 0, 1, -1, -1),
    array(0, 0, 1, 0, 1, 0, 1, -1, -1),
);
*/

    // Attempt to solve.
    $solver = array();
    $minesleft = GetTotalMines($board);
echo "Hi: 4\n";
    $spacesleft = $boardx * $boardy;
    OpenBoardPosition($solver, $board, $sboard, $startx, $starty);
echo "Hi: 5\n";

    foreach ($solver as $num => $point)
    {
        $sboard[$point[1]][$point[0]] = -1;
        $board[$point[1]][$point[0]] = -1;
    }

    while (count($solver))
    {
        $spacesleft2 = $spacesleft;
        $numpoints = count($solver);

        // Find exact matches.
        foreach ($solver as $num => $point)
        {
//echo $point[0] . ", " . $point[1] . ":  ";
            $mines = GetMinesAtPoint($board, $point[0], $point[1]);
            $smines = GetMinesAtPoint($sboard, $point[0], $point[1]);
            $savail = GetAvailablePoints($sboard, $point[0], $point[1]);

            if (count($mines) == count($smines))
            {
//echo "Path 1\n";
                // Clear the remaining spaces.
                foreach ($savail as $point2)
                {
                    $sboard[$point2[1]][$point2[0]] = -1;
                    $board[$point2[1]][$point2[0]] = -1;

                    $spacesleft--;

                    $solver[] = $point2;
                }

                unset($solver[$num]);

                $sboard[$point[1]][$point[0]] = -1;
                $board[$point[1]][$point[0]] = -1;

                $spacesleft--;
            }
            else if (count($mines) == count($smines) + count($savail))
            {
//echo "Path 2\n";
                // Fill in the remaining spaces with mines.
                foreach ($savail as $point2)
                {
                    $sboard[$point2[1]][$point2[0]] = 1;
                    $board[$point2[1]][$point2[0]] = 2;

                    $spacesleft--;
                }

                unset($solver[$num]);

                $sboard[$point[1]][$point[0]] = -1;
                $board[$point[1]][$point[0]] = -1;

                $spacesleft--;
            }
            else if (count($mines) - count($smines) == 2 && count($savail) == 3)
            {
//echo "Path 3\n";
                // Try vertical 1 2 1.
                $found = false;
                if ($point[1] > 0 && $point[1] < $boardy - 1 && $board[$point[1] - 1][$point[0]] <= 0 && $board[$point[1] + 1][$point[0]] <= 0)
                {
//echo "Path 3a\n";
                    $mines2 = GetMinesAtPoint($board, $point[0], $point[1] - 1);
                    $smines2 = GetMinesAtPoint($sboard, $point[0], $point[1] - 1);
                    $mines3 = GetMinesAtPoint($board, $point[0], $point[1] + 1);
                    $smines3 = GetMinesAtPoint($sboard, $point[0], $point[1] + 1);

                    if (count($mines2) - count($smines2) == 1 && count($mines3) - count($smines3) == 1)
                    {
                        foreach ($savail as $point2)
                        {
                            if ($point2[1] == $point[1])
                            {
                                $sboard[$point2[1]][$point2[0]] = -1;
                                $board[$point2[1]][$point2[0]] = -1;

                                $solver[] = $point2;
                            }
                            else
                            {
                                $sboard[$point2[1]][$point2[0]] = 1;
                                $board[$point2[1]][$point2[0]] = 2;
                            }

                            $spacesleft--;
                        }

                        unset($solver[$num]);

                        $sboard[$point[1]][$point[0]] = -1;
                        $board[$point[1]][$point[0]] = -1;

                        $spacesleft--;

                        $found = true;
                    }
                }

                // Try horizontal 1 2 1.
                if (!$found && $point[0] > 0 && $point[0] < $boardx - 1 && $board[$point[1]][$point[0] - 1] <= 0 && $board[$point[1]][$point[0] + 1] <= 0)
                {
//echo "Path 3b\n";
                    $mines2 = GetMinesAtPoint($board, $point[0] - 1, $point[1]);
                    $smines2 = GetMinesAtPoint($sboard, $point[0] - 1, $point[1]);
                    $mines3 = GetMinesAtPoint($board, $point[0] + 1, $point[1]);
                    $smines3 = GetMinesAtPoint($sboard, $point[0] + 1, $point[1]);

                    if (count($mines2) - count($smines2) == 1 && count($mines3) - count($smines3) == 1)
                    {
                        foreach ($savail as $point2)
                        {
                            if ($point2[0] == $point[0])
                            {
                                $sboard[$point2[1]][$point2[0]] = -1;
                                $board[$point2[1]][$point2[0]] = -1;

                                $solver[] = $point2;
                            }
                            else
                            {
                                $sboard[$point2[1]][$point2[0]] = 1;
                                $board[$point2[1]][$point2[0]] = 2;
                            }

                            $spacesleft--;
                        }

                        unset($solver[$num]);

                        $sboard[$point[1]][$point[0]] = -1;
                        $board[$point[1]][$point[0]] = -1;

                        $spacesleft--;
                    }
                }
            }
            else if (count($mines) - count($smines) == 1 && count($savail) == 3)
            {
//echo "Path 4\n";
                // Determine directionality.
                if ($savail[0][0] == $savail[1][0] && $savail[0][0] == $savail[2][0])
                {
//echo "Path 4a\n";
                    // Vertical up.
                    if ($point[1] > 0 && $board[$point[1] - 1][$point[0]] <= 0)
                    {
                        $mines2 = GetMinesAtPoint($board, $point[0], $point[1] - 1);
                        $smines2 = GetMinesAtPoint($sboard, $point[0], $point[1] - 1);
                        $savail2 = GetAvailablePoints($sboard, $point[0], $point[1] - 1);

                        if (count($mines2) - count($smines2) == 1 && count($savail2) == 2)
                        {
                            $x = $savail[0][0];
                            $y = max($savail[0][1], $savail[1][1], $savail[2][1]);

                            $sboard[$y][$x] = -1;
                            $board[$y][$x] = -1;

                            $solver[] = array($x, $y);
                        }
                    }

                    if ($point[1] < $boardy - 1 && $board[$point[1] + 1][$point[0]] <= 0)
                    {
                        $mines2 = GetMinesAtPoint($board, $point[0], $point[1] + 1);
                        $smines2 = GetMinesAtPoint($sboard, $point[0], $point[1] + 1);
                        $savail2 = GetAvailablePoints($sboard, $point[0], $point[1] + 1);

                        if (count($mines2) - count($smines2) == 1 && count($savail2) == 2)
                        {
                            $x = $savail[0][0];
                            $y = min($savail[0][1], $savail[1][1], $savail[2][1]);

                            $sboard[$y][$x] = -1;
                            $board[$y][$x] = -1;

                            $solver[] = array($x, $y);
                        }
                    }
                }
                else if ($savail[0][1] == $savail[1][1] && $savail[0][1] == $savail[2][1])
                {
//echo "Path 4b\n";
                    // Horizontal left.
                    if ($point[0] > 0 && $board[$point[1]][$point[0] - 1] <= 0)
                    {
                        $mines2 = GetMinesAtPoint($board, $point[0] - 1, $point[1]);
                        $smines2 = GetMinesAtPoint($sboard, $point[0] - 1, $point[1]);
                        $savail2 = GetAvailablePoints($sboard, $point[0] - 1, $point[1]);

                        if (count($mines2) - count($smines2) == 1 && count($savail2) == 2)
                        {
                            $x = max($savail[0][0], $savail[1][0], $savail[2][0]);
                            $y = $savail[0][1];

                            $sboard[$y][$x] = -1;
                            $board[$y][$x] = -1;

                            $solver[] = array($x, $y);
                        }
                    }

                    // Horizontal right.
                    if ($point[0] < $boardx - 1 && $board[$point[1]][$point[0] + 1] <= 0)
                    {
                        $mines2 = GetMinesAtPoint($board, $point[0] + 1, $point[1]);
                        $smines2 = GetMinesAtPoint($sboard, $point[0] + 1, $point[1]);
                        $savail2 = GetAvailablePoints($sboard, $point[0] + 1, $point[1]);

                        if (count($mines2) - count($smines2) == 1 && count($savail2) == 2)
                        {
                            $x = min($savail[0][0], $savail[1][0], $savail[2][0]);
                            $y = $savail[0][1];

                            $sboard[$y][$x] = -1;
                            $board[$y][$x] = -1;

                            $solver[] = array($x, $y);
                        }
                    }
                }
            }
            else if (count($mines) - count($smines) == 1 && count($savail) == 2)
            {
//echo "Path 5\n";
                // Determine directionality.
                $point2 = false;
                if ($savail[0][1] == $savail[1][1] && ($point[0] == $savail[0][0] || $point[0] == $savail[1][0]))
                {
                    // Horizontal left.
                    if ($point[0] - 1 == $savail[0][0] || $point[0] - 1 == $savail[1][0])  $point2 = array($point[0] - 1, $point[1]);

                    // Horizontal right.
                    if ($point[0] + 1 == $savail[0][0] || $point[0] + 1 == $savail[1][0])  $point2 = array($point[0] + 1, $point[1]);
                }
                else if ($savail[0][0] == $savail[1][0] && ($point[1] == $savail[0][1] || $point[1] == $savail[1][1]))
                {
                    // Vertical up.
                    if ($point[1] - 1 == $savail[0][1] || $point[1] - 1 == $savail[1][1])  $point2 = array($point[0], $point[1] - 1);

                    // Vertical down.
                    if ($point[1] + 1 == $savail[0][1] || $point[1] + 1 == $savail[1][1])  $point2 = array($point[0], $point[1] + 1);
                }

                if ($point2 !== false)
                {
//echo "Path 5a\n";
                    $mines2 = GetMinesAtPoint($board, $point2[0], $point2[1]);
                    $smines2 = GetMinesAtPoint($sboard, $point2[0], $point2[1]);
                    $savail2 = GetAvailablePoints($sboard, $point2[0], $point2[1]);

                    if (count($mines2) - count($smines2) == 1)
                    {
                        foreach ($savail2 as $point2)
                        {
                            if (($point2[0] == $savail[0][0] && $point2[1] == $savail[0][1]) || ($point2[0] == $savail[1][0] && $point2[1] == $savail[1][1]))  continue;

                            $sboard[$point2[1]][$point2[0]] = -1;
                            $board[$point2[1]][$point2[0]] = -1;

                            $solver[] = $point2;
                        }
                    }
                }
            }
        }

        if ($spacesleft2 == $spacesleft && count($solver) == $numpoints)
        {
//echo "Path FAILED\n";
            $minnum = false;
            $total = 0;
            $spaces = 0;
            foreach ($solver as $num => $point)
            {
                $mines = GetMinesAtPoint($board, $point[0], $point[1]);
                $smines = GetMinesAtPoint($sboard, $point[0], $point[1]);
                $savail = GetAvailablePoints($sboard, $point[0], $point[1]);

                if ($minnum === false || $total > count($mines2) - count($smines2) || ($total == count($mines2) - count($smines2) && $spaces > count($savail)))
                {
                    $minnum = $num;
                    $total = count($mines2) - count($smines2);
                    $spaces = count($savail);
                }
            }

            if ($minnum !== false)  ClearPoint($board, $solver[$minnum][0], $solver[$minnum][1]);
            else
            {
//echo "No more options.\n";
                break;
            }
        }
    }
var_dump($solver);

    // Fill awkward positions with mines.
    for ($y = 0; $y < $boardy; $y++)
    {
        for ($x = 0; $x < $boardx; $x++)
        {
            if ($board[$y][$x] == 0)
            {
                $board[$y][$x] = 1;

                $minesleft++;
            }
            else if ($board[$y][$x] == -1)
            {
                $maxmines = 0;
                if ($x > 0 && $y > 0)  $maxmines++;
                if ($y > 0)  $maxmines++;
                if ($x < $boardx - 1 && $y > 0)  $maxmines++;

                if ($x > 0)  $maxmines++;
                if ($x < $boardx - 1)  $maxmines++;

                if ($x > 0 && $y < $boardy - 1)  $maxmines++;
                if ($y < $boardy - 1)  $maxmines++;
                if ($x < $boardx - 1 && $y < $boardy - 1)  $maxmines++;

                $mines = GetMinesAtPoint($board, $x, $y);

                if (count($mines) == $maxmines)
                {
                    $board[$y][$x] = 1;

                    $minesleft++;
                }
            }
        }
    }


DumpBoard($board);
DumpBoard($sboard);
var_dump($minesleft);
echo $startx . ", " . $starty . "\n";
var_dump($board[$starty][$startx]);
?>

Writing generators/solvers for various games and puzzles is a satisfying experience as a software developer. Don't cheat yourself of that experience. The key to most puzzle generators/solvers is to start small, stare at various board states for a while, come up with a logical rule that works for most cases, implement that, and then repeat. So don't just grab the above code and use it as-is. Write your own. You should only peek at what other people have done if you truly get stuck or after you've rolled your own.