我正在设计一个类似扫雷的游戏（修改了规则），我想防止玩家猜测。我的目标是：生成的棋盘只有很少的方块被揭示，玩家可以在不猜测的情况下解决整个谜题。
维基百科 提到：
一些扫雷实现方式会在设置棋盘时，不在第一个被揭开的方块上放置地雷，或者安排棋盘使得解决方案不需要猜测。
然而，我无法找出算法。
另外，在 StackOverflow 上的另一个问题：Minesweeper solving algorithm
改进：让求解器和生成器同时运行，并确保谜题有唯一解。这需要一些巧妙的方法，在大多数变体中都没有完成。
我怀疑这是否真的可行。众所周知，解决扫雷 是 NP 完全问题。
总之，我的问题是：
Simon Tatham's Portable Puzzle Collection 中扫雷的实现是无需猜测的。（它还使用 MIT 许可证，因此如果您愿意，可以自由复制他的实现。）
众所周知，扫雷是NP完全问题。
这是事实，但可能并不像你想象的那样相关。所提出的算法类似于“重复生成随机棋盘，直到计算机可以解决一个”。NP硬度是最坏情况下的属性，但在这里我们真正关心的是平均情况的难度。如果生成了一个异常难的棋盘，我们可以超时解算器并重新开始使用新棋盘。
此外，即使有一个用于区分好的棋盘和坏的棋盘的预言机，你是否真的希望用户为了避免猜测而必须解决一个困难的问题？一个不太聪明的计算机求解器可能会对选择更公平的棋盘进行偏向。
我知道这个问题已经很老了，但我想添加一个与其他答案略有不同且可以得到相当高性能的扫雷板生成答案。此外，我提供了完全功能的源代码，虽然缺少注释和我的通常专业抛光，并且还不太完整。
我们将使用以下数字来指示特定条件：
第一步是用-1保留起始位置和周围的8个空间，然后随机生成填满可能的地雷的板。这是简单的部分。关键是在向用户呈现之前，在内部解决板。
进入解算器阶段之前，找到从起始位置开始的区域中没有地雷的所有点，并将它们标记为要解决的点。
对于解算器阶段，请使用逻辑规则尽可能多地解决，直到遇到障碍。解算器可以简单或复杂，但玩家更喜欢推断合理简单的规则，而不是进行深入分析以找出地雷位置。有两种推断规则：已知地雷位置和已知空位。
第一条规则很明显：找到了周围所有空间的地雷。打开剩余的空间并将其标记为要解决的点。将当前点标记为完成。
下一个规则也很明显：周围的所有空间都已填满，唯一剩下的空间是地雷。用永久地雷填充空格。将当前点标记为完成。
之后，事情变得有些棘手。下一个最常见的模式是“1 2 1”，其中有3个相邻的未知空间（在计算相邻点的剩余地雷后）。当水平或垂直遇到该模式时，中间空间不能有地雷，其他两个空间必须是地雷。
从这里开始，还有几个可以应用的逻辑规则，这些规则相当复杂，但不需要递归或测试大量不同的点。我会尽力而为：
第一个复杂规则是打开逻辑上不可能的位置，只能在两个不同的相邻位置放置一个地雷，但是在一列/行中有三个开放的相邻空格（例如，打开第三个空格）。例如，对于逻辑“1 1？”必须在两个1位置中的一个中放置地雷，“？”必须是开放空间。
另一个复杂规则是打开逻辑上不可能的位置，只能在两个不同的位置放置一个地雷，但相邻空间只有一个地雷，而且还有超过相同的两个可能位置（即其余清晰）。例如：
???
?11
?1
当处理中间的点时，左侧的三个方块必须是开放空间，因为其他两个方块必须是地雷。
我认为这些更复杂的规则在生成一些棋盘并首次遇到它们后会变得更加明显。
所有这些规则都可以通过仅使用当前感兴趣的点而不进行递归或任何更复杂的操作来完成。
好的，现在假设解算器在逻辑上遇到了瓶颈，没有打开任何新的区域，并且对任何其他地雷位置也不确定。解决方法是将一个或多个非永久性地雷随机移动到棋盘上的另一个非永久性位置。这很不幸地容易将一些地雷推到边缘和角落，但它在其他方面表现得相当好。这样做有时也会导致先前已解决的位置变得无法解决。
下一步是填补那些无法到达的区域（即将 0 改成 1）。
如果解算器移动了任何地雷，则将 -1 重置为 0，将 2 重置为 1，重新打开起始位置，然后重新开始解算器，直到没有移动更多的地雷。此外，如果输出结果超过目标地雷数量的 20％，则几乎可以确定大部分棋盘都被地雷占据。对于这些情况，只需使用全新的棋盘重新开始即可。使用此算法在大多数编程/脚本语言中，在内部生成和解决一个相当大的棋盘需要不到 1 秒钟。因此，玩家可以等待额外的半秒钟。
我没有查看 Simon Tatham 的算法，但我已经玩了他的移动版扫雷小游戏很多次，知道它倾向于在外边缘和角落上有许多地雷。因此，他的算法可能与上述类似。
以下是 PHP 中大多数算法的快速而简单的实现（主要是没有执行最后一步并重复解算器循环，这会导致结果略微不完美 - 这是您自己实现的练习）：
<?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]);
?>
....x
.x...
x..x.
..x..
x...x
1111x
2x222
x33x1
23x32
x212x
那么使用这种方法有什么问题呢？问题在于我们检查地雷的次数太多了。让我们看一下：
1111x - took 23 checks
2x222 - took 31 checks
x33x1 - took 26 checks
23x32 - took 31 checks
x212x - took 20 checks
哎呀！ 这一共有131个检查点。现在，让我们来试试平方方法：
1111x - took 8 checks
2x222 - took 13 checks
x33x1 - took 18 checks
23x32 - took 13 checks
x212x - took 11 checks
这种方法速度更快，仅需63次检查，少于朴素方法的一半。
在解决棋盘问题时，这些“方块”也可以被利用。例如：
0000
?110
??10
???0
0000
?110
?-10
???0
0000
+110
+-10
?++0
然而，在我们揭开所有排队的方块之前，我们无法以同样的方式扩展最后一个？。举个例子，我将使用一些2：
0000
1110
2x10
?210
现在我们可以看到另一个角落，结果发现它与一座矿井相交。这可能很难发现，但这就是一个角落。
需要注意的一件事是像这样的情况：
00000
01110
12x10
x?210
2x100