数独回溯使用c#

Question

我在编程中做一个项目 class 我选择做一个数独求解器。然而，我之前没有做过任何算法，发现这是一个相当大的挑战。我已经阅读了一些关于解决数独问题的文章，但我正在为实际的代码编写而苦苦挣扎。谁能给我一些帮助？

所以我的老师坚持要我使用双数组（int[] 类型），所以我努力坚持下去。问题是我真的不知道如何回去尝试另一件事，或者我真正的意思是如何回溯。如果有人可以帮助我编写代码（即使是 3x3 数独），我将不胜感激。

此外，为了防止不清楚我想要什么，我上传了说明性图片

真正不清楚的是我如何编写第三步（红色圆圈）。

Answer 1

无需任何递归即可解决简单的数独难题。您遍历每个空块并尝试解决它。如果它是

中的唯一块

1. 行
2. 或列
3. 或区块

然后你输入号码。你这样做直到你的谜语被解决。

递归开始！

但是，如果您停滞不前并且无法使用此方法解决更多空字段，则必须递归。选择具有 最少 可能选项的块，例如只有 3 个数字可能的块。对这 3 个数字执行递归，尝试每一个。然后，通过上述方法重试。当你再次停滞不前时，再递归一步。

您的许多递归案例将以错误的数独谜题结束（即无法解决）。你只是忽略它们。这些情况之一将解决它。

伪代码

我会尝试在这里调解思路，而不是只是粘贴一堆代码。你应该能够解决这个问题。这是一个脑筋急转弯，但可能

function Solve(grid)
    while
        SolveByLogic(grid)
        
        if (grid is not solved)
            cell = find cell with the least possible options
            for each of this option
                try to => Solve(grid)
            next
        end
    wend
end

function SolveByLogic(grid)
    // Try to solve it by pure logic
    while
        foundAny = false
        for each empty cell
            if (cell is the only empty cell in row)
                cell = what's left in that row
                foundAny = true
            else if (cell is the only empty cell in column)
                cell = what's left in that column
                foundAny = true
            else if (cell is the only empty cell in grid)
                cell = what's left in that grid (by grid I mean the 3x3 grid)
                foundAny = true
        next
        if (foundAny == false) return //No more logic solving possible
    wend
end

注意：这不是一个完整的算法，您可以将其转换成您的语言并使用！但它应该给你解决这个问题所需的想法！

祝你好运:)

Answer 2

我会尝试一下 Dancing Links 算法，尽管与矩形数组相比，自定义 Node 对象确实更有效。

http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz

问题类型是精确覆盖。研究可以解决此类问题的不同算法，然后选择最适合您现有参数的算法。