使用策略的数独解题器

• Git 仓库: https://github.com/DHancock/SudokuSolver

引言

作为一名自学的数独求解者，我喜欢解数独本身，但真正的挑战在于找出解决它们所需的策略。有时，我会被一个谜题卡住，而通过尝试所有策略来寻找下一个数字可能会变得有些无聊。也许它很明显，但我就是看不出来。这就是我编写这个程序的原因。我已经将我所知道的所有策略都转换成了代码，这些代码永远不会感到厌倦，也不会犯错误。

不过，有些谜题我还是无法解决。我非常确定我遗漏了一个策略，而这个程序将证实这一点。

用户界面

这是一个简单的 WPF 程序。它使用了 MahApps 库，提供了一个无标题栏窗口，并轻松实现了暗模式。

请注意，没有“求解”按钮。该代码将在用户每次更改数独时尝试即时求解。

代码

程序结构遵循最小的 MVVM 设计模式。

模型包含所有求解策略以及一个包含 81 个**单元格**的一维数组。解决数独谜题的技巧不在于直接找出数字的位置，而在于找出它们不能去哪里，当只剩下一个可能性时，那就是它了。为此，每个单元格都包含一个可能的单元格值列表，然后由策略更新。该列表实际上是一个位字段，允许使用布尔代数来辅助所需的模式匹配。另一个值得注意的地方是，我没有编写两个函数来实现一个策略，一个用于行，另一个非常相似的版本用于列，我只编写了行版本，然后旋转数独，然后再次调用行函数。数独并没有真正旋转，代码只是改变了每个单元格的 [x, y] 坐标如何转换为数组索引。

视图模型也包含一个 81 个单元格的列表，这次存储在 `ObservableCollection` 中。当用户更改数独时，视图模型中的一个回调将被执行。它确定需要执行的操作，并调用适当的模型函数，无论是添加、编辑、删除等，以便可以重新计算数独。当模型函数返回时，将比较两个单元格列表，并在需要时更新视图模型列表，这将重绘单元格。

视图包含一个自定义布局面板 `SudokuGrid`，用于排列单元格和网格线。我在网上找不到太多关于编写布局面板的信息，所以我使用 ILSpy 反向工程了 `UniformGrid`。事实证明它们很简单，如果你写过自定义控件，很多东西都会很熟悉。网格包含在一个 `Viewbox` 中，该 `Viewbox` 提供自动缩放。

求解策略

这些对其他数独解谜者来说可能非常熟悉，但作为自学者，它们会有不同的名称和术语。81 个单元格也分为九个**方块**，每个方块包含九个单元格。行和列如你所料。

1. 简单方块、行和列排除

如果用户在红色单元格中输入一个数字，那么该数字将从蓝色区域所有单元格的可能值中删除。如果这导致一个单元格只剩下一个可能值，那么它将被添加到堆栈中，代码将循环处理单元格，直到堆栈中没有更多单元格为止。

2. 方向排除

如果方块中 3 个单元格的一行内的单元格的可能值是独占的，那么数独行中剩余的六个单元格就不能包含这些独占的可能值。这是一行，所以独占值的影响方向是水平的。对列中的方块（垂直方向）使用相同的过程。可能值将显示为红色，如果它们的方向是水平的，显示为绿色，如果方向是垂直的。

此外，如果一个单元格有一个可能值同时具有垂直和水平方向，那么它必须是该单元格的值。

3. 单一可能值

虽然一行或一列中的单元格可能有多个可能值，但如果只有一个单元格具有特定值，那么它必须是该单元格的值。

4. 模式匹配排除

这个策略有点复杂。下面显示的任何彩色单元格都没有值，只有可能值。

两个方块中的四个绿色单元格在其可能值列表中将包含六。六可以出现在不同列的顶部和底部单元格或底部和顶部单元格中，这两种排列方式都是有效的。这意味着我们可以推断出剩余方块中的红色单元格在其可能值中必须包含六，因此六可以从蓝色区域的单元格可能值中删除。所示绿色单元格的模式是 `Pattern.Lower2`，两列中两个单元格的其他可能模式是 `Pattern.Upper2` 和 `Pattern.TopAndBottom`。

四个绿色单元格不需要在同一列，它们可以是任何组合。结果将是相同的。为了适应这一点，代码聚合了三个方块中所有三行单元格的可能值。这会产生一个结构，其中包含三列，每列对应一个方块，包含三组可能值。正是这个结构被用于模式匹配。

此策略应用于数独中的所有三行方块，以及每三个方块的列。

5. 简单试错

我知道我总是需要实现这个策略，因为你偶尔会遇到一个谜题，其中两行两列交叉处的四个单元格可能有两个可能值，但它们的排列是无法确定的。谜题可能有多个正确的解决方案。你只需要选择一个值，插入它，然后让逻辑策略处理其余部分。

事实证明，这可能一直是我遗漏的策略。虽然逻辑策略本身足以解决简单的问题，但添加这个策略可以解决更难的谜题。专家级谜题解算者可能可以在脑海中做到这一点，跟踪谜题的状态，但这对我来说超出了能力范围。这也是为什么我不擅长下棋；我无法提前规划那么多步。

调用策略

模型方法 `CalculatePossibleValues`（如下所示）在用户每次更改数独时都会被调用。它首先构建一个要更新的单元格堆栈。当用户在空单元格中输入新值时，它将包含一个单元格，或者对于更复杂的操作（如删除），它将加载所有已有值的单元格，以便模型可以重建。然后，当各种求解策略发现只剩下一个可能值时，可以将单元格添加到堆栈中。

代码包含两个嵌套的 `while` 循环，它们会一直运行，直到堆栈中没有更多单元格为止。内部循环包含相互影响结果的策略，因此在模型发生任何更改时，它们会继续循环。

private void CalculatePossibleValues(Cell updatedCell, bool forceRecalculation)
{
    Stack<Cell> cellsToUpdate = new Stack<Cell>(Cells.Count);

    if (updatedCell.HasValue && !forceRecalculation)
        cellsToUpdate.Push(updatedCell);
    else
    {
        // it's much simpler to just start from scratch and rebuild it...
        foreach (Cell cell in Cells)
        {
            if (cell.Origin == Origins.User)
                cellsToUpdate.Push(cell);
            else
                cell.Reset(); 
        }
    }

    do
    {

        while (cellsToUpdate.Count > 0)
        {
            Cell cell = cellsToUpdate.Pop();

            if (!cell.HasValue) // convert a single possible into a cell value
            {
                cell.Value = cell.Possibles.First;
                cell.Origin = Origins.Calculated;
            }

            SimpleEliminationForCell(cell, cellsToUpdate);
        }

        bool modelChanged;

        do
        {
            modelChanged = DirectionElimination(cellsToUpdate);

            CheckForSinglePossibles(cellsToUpdate);

            modelChanged |= CubePatternMatchElimination(cellsToUpdate);
        }
        while ((cellsToUpdate.Count == 0) && modelChanged);

    }
    while (cellsToUpdate.Count > 0);
}
    

当此方法返回时，如果用户发起的更改适用，则会调用试错策略。

总结

好了，就这样。这是我的 Covid 封锁项目。在任何学科中自学的麻烦在于，你永远无法真正确定你已经覆盖了问题的多少空间。但这个解决方案似乎至少是合理的。我希望你喜欢它，也许，你可以在自己的代码中重用一些技术。

历史

• 2020 年 6 月 30 日：首次提交
• 2021 年 2 月 4 日：更新文章以发布应用程序 1.2.0