我正在设计一个类似扫雷的游戏（修改了规则），我想防止玩家猜测。我的目标是：生成的棋盘只有很少的显示方格，玩家无需猜测即可解决整个谜题。
维基百科提到：
Minesweeper 的一些实现将通过从不在显示的第一个方格上放置地雷来设置棋盘，或者通过安排棋盘以使解决方案不需要猜测。
但是，我无法弄清楚算法。
此外，在另一个 StackOverflow 问题中：扫雷求解算法
改进：在生成器旁边运行求解器，确保拼图有唯一的解决方案。这需要一些聪明才智，并且在大多数变体中都没有完成。
我怀疑这是否真的有效。众所周知，解决扫雷是NP完全的。
总之，我的问题是：
Simon Tatham 的便携式拼图系列中扫雷的实现无需猜测。（它也是 MIT 许可的，所以如果你愿意，你可以自由地复制他的实现。）
众所周知，解决扫雷是NP完全的。
这是真的，但可能不像你想象的那么重要。所提出的算法类似于“重复生成随机棋盘，直到计算机可以解决一个”。NP 硬度是最坏情况下的属性，但这里我们真正感兴趣的是平均情况下的硬度。如果生成了异常硬的板，我们可以使求解器超时并重新启动新板。
此外，即使有一个可以区分好板和坏板的神谕，你真的希望用户必须解决一个难题以避免猜测吗？一个不太有才华的计算机求解器可能会使选择偏向更公平的电路板。
免责声明：这可能完全相关，也可能不完全相关，但我注意到它很巧妙，并且可能对其他试图找到答案的人有用。
在扫雷中，我在查看不同的扫雷棋盘时发现了一个巧妙的小东西：在游戏中，当生成棋盘时，所有非地雷方块的值都设置为相邻地雷的数量。但是，您可以应用相同的东西，但反过来：所有地雷将每个相邻空间的值加 1。这使得人们可以将地雷视为不像地雷，而更像是分层的 3x3 正方形。为了演示，这里有一块板子，去掉了任何相邻的地雷数量：
....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 张支票。现在，让我们试试 square 方法：
1111x - took 8 checks
2x222 - took 13 checks
x33x1 - took 18 checks
23x32 - took 13 checks
x212x - took 11 checks
这种方法要快得多，总共只有 63 次检查，不到 naïve 方法的一半。
这些“方块”也可以在解板时使用。例如：
0000
?110
??10
???0
在这个例子中，我们可以清楚地看到一个角落，因此是一个正方形，中间有一个地雷（+ 和 - 是排队打开和标志）：
0000
?110
?-10
???0
我们也可以扩大角落，因为它上面没有另一个正方形：
0000
+110
+-10
?++0
但是，我们不能扩展最后一个 ? 以同样的方式，直到我们发现所有排队的瓷砖。举个例子，我将使用一些二：
0000
1110
2x10
?210
现在我们可以看到另一个角落，原来它与一个地雷相交。这可能很难发现，但这是一个角落。
但是，需要注意的一件事是这样的：
00000
01110
12x10
x?210
2x100
在这种情况下，有 3 个正方形。右上角的 4x4 区域与前面的场景相匹配，但不要被愚弄：前面的两个是这一个中两个独立方块的一部分，而未知的瓷砖恰好是一个 3。如果我们在那里放了一个地雷，那两个就完整了，我们就会误判，试图发现一个看起来安全的瓷砖。
TL;DR：地雷可以被认为是分层的 3x3 方块，可以在生成和/或求解时节省时间。
我意识到这个问题已经相当老了，但我想我会添加一个与其他答案有点不同的答案，并且可以产生相当性能的扫雷板生成。此外，我还包括了功能齐全的源代码，尽管缺少注释和我通常的专业润色，而且还不是很完整。
我们将使用以下数字来表示某些条件：
第一步是用-1保留起始位置和周围的8个空格，然后随机生成一个装满可能地雷的棋盘。这是简单的部分。关键是在将板呈现给用户之前在内部解决板。
在进入求解器阶段之前，从起始位置找到该区域内所有没有地雷的点，并将它们标记为要解决的兴趣点。
对于求解器阶段，使用逻辑规则尽可能多地求解，直到碰壁。求解器可以根据需要简单或复杂，但玩家更喜欢相当简单的推理规则，而不是必须进行深入分析才能确定地雷位置。有两种类型的扣除规则：已知地雷位置和已知空位。
第一条规则很明显：周围空间的所有地雷都已找到。打开剩余的空间并将它们标记为兴趣点。将当前点标记为已完成。
下一条规则也很明显：所有周围的空间都已被填满，剩下的空间就是地雷。用永久性地雷填充空间。将当前点标记为已完成。
在那之后，事情变得有点棘手。下一个最常见的模式是具有 3 个相邻未知空间的“1 2 1”（在计算了相邻点剩余的地雷之后）。当垂直或水平遇到该模式时，中间空间不能有地雷，而其他两个空间必须是地雷。
从这里开始，可以应用一些其他逻辑规则，这些规则解释起来相当复杂，但不需要递归或测试一堆不同的点。我会尽力做到最好：
第一个复杂规则是打开逻辑上不可能的位置，其中只有一个地雷可以放置在两个不同的相邻位置，但在一行/列中有三个打开的相邻空间（即打开第三个位置）。例如，对于逻辑“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]);
?>
作为软件开发人员，为各种游戏和谜题编写生成器/求解器是一种令人满意的体验。不要欺骗自己的经验。大多数谜题生成器/求解器的关键是从小处着手，观察各种棋盘状态一段时间，提出适用于大多数情况的逻辑规则，实施该规则，然后重复。所以不要只是抓住上面的代码并按原样使用它。写你自己的。如果你真的被卡住了或者你自己做了什么，你应该只看看别人做了什么。