问题标签 [sudoku]

这个问题的重点是创建最短且不滥用缓慢的数独求解器。这被定义为：当棋盘上有可能只有一位数的点时，不要递归。

这是迄今为止我在python中最短的：

我将最后一行作为 cmd 行输入的一部分，它可以更改为：

这类似于其他数独高尔夫挑战，只是我想消除不必要的递归。任何语言都可以接受。挑战来了！

有谁知道一个简单的算法来检查数独配置是否有效？我想出的最简单的算法是伪代码中的（对于大小为 n 的板）

但我很确定一定有更好的（在更优雅的意义上）解决方案。效率是相当不重要的。

我正在用 PHP 编写算法来解决给定的数独难题。我已经建立了一个有点面向对象的实现，它有两个类：一个Square类用于 9x9 板上的每个单独的瓷砖，一个Sudoku类，它有一个Squares 矩阵来表示板。

我正在使用的算法的实现是一种三层方法。第一步，将只解决最基本的难题（但最有效），是根据棋盘的初始设置填充任何只能取单个值的方格，并相应地调整其余部分的约束未解的正方形。

通常，这种“不断传播”的过程并不能完全解决棋盘问题，但它确实解决了相当大的问题。然后第二层将启动。这会解析每个单元（或 9 个必须都具有唯一编号分配的方格，例如行或列）以获取每个未解决方格的“可能”值。此可能值列表在类中表示为字符串Square：

给定一个单元中的整个未解正方形数组（如上面第二层所述），第二层会将所有“可能”字符串连接成一个字符串。然后它将在该单个字符串中搜索任何唯一字符值 - 不会重复的值。这将表明，在方格单位内，只有一个方格可以采用该特定值。

我的问题是：为了实现第二层，我如何解析一个单元中所有可能值的字符串并轻松检测唯一值？我知道我可以创建一个数组，其中每个索引由数字 1-9 表示，并且我可以为我找到的该数字的每个可能值将相应索引处的值增加 1，然后再次扫描数组以查找任何值 1，但这似乎效率极低，需要对每个单元的数组进行两次线性扫描，而在数独游戏中有 27 个单元。

I'm trying to create a sudoku solver program in Java (maybe Python). I'm just wondering how I should go about structuring this...

Do I create a class and make each box a object of that class (9x9=81 objects)? If yes, how do I control all the objects - in other words, how do I make them all call a certain method in the class?

Do I just create functions to calculate and just control all the numbers in there with something like an multi-D array?

And actually, even if I could just create multiple functions, how would I control all the objects if I were to make each box an object?

Thanks.

给定一个包含 81 个元素的数组（表示 9x9 网格），我如何遍历每个元素，抓住它周围的三个元素，然后对它们执行操作，然后继续到每行、列或子矩阵的下三个元素。查看下方或数独网格以查看布局。

例如，我有

和

由于总共 9x9 的网格可以拆分为以下 9 个类别，每个数组有 9 个元素，我希望将每列（x 轴）的元素三人一组，执行

在它们上，取三个结果数，并对它们执行，然后将其存储到数组中。

如果这听起来不可能，对不起，我想要一种不同的方式来做到这一点。绝对开放的建议...

我需要一个衬垫（或接近它）来验证给定的 9 个元素数组不包含重复数字 1、2、3、...、9。重复的零不算数（它们代表空单元格）。

到目前为止，我出来的最好的是：

如果您不想解决我的问题:)，您至少可以判断上述算法是否正常工作吗？

而且，是的，一个已经读过这个。

A-star 用于在图中找到起始节点和结束节点之间的最短路径。如果目标状态不是具体已知的，而我们只有目标状态的标准，则使用什么算法来解决问题？

例如，一个数独游戏可以用类似 Astar 的算法来解决吗？我们不知道最终状态会是什么样子（哪个数字在哪里），但我们知道数独的规则，即获胜状态的标准。因此，我有一个 startnode 和一个 endnode 的标准，使用哪种算法？

我有一个家庭作业要编写一个多线程数独求解器，它可以找到给定谜题的所有解决方案。我之前写过一个非常快速的单线程回溯数独求解器，所以我在数独求解方面不需要任何帮助。

我的问题可能与并非真正理解并发有关，但我看不出这个问题如何从多线程中受益。我不明白如何在不维护拼图的多个副本的情况下同时找到同一问题的不同解决方案。鉴于这个假设（请证明它是错误的），我看不出多线程解决方案如何比单线程更有效。

如果有人能给我一些关于算法的起始建议，我将不胜感激（请不要代码......）

我忘了提，要使用的线程数被指定为程序的参数，所以据我所知，它与拼图的状态没有任何关系......

此外，可能没有唯一的解决方案 - 有效的输入可能是一个完全空的板。我必须报告min(1000, number of solutions)并显示其中之一（如果存在）

我一直在研究数独求解器，我目前的求解器使用回溯算法，但仍然需要很长时间。

在大多数情况下，我希望将其降低到不到一秒。因此，我决定用跳舞链接算法重写它，理解它是更好的蛮力方法之一，尤其适用于数独难题等约束问题。

我试图阅读 Wiki 和Knuth 的论文，但是它们都很难理解并且非常冗长。

我还阅读了 Suododia 的版本，似乎一旦进入数独的实现，它就变得太抽象了。

有人可以尝试解释 Dancing Links 算法，而不是根据它的推导而是它的实现吗？（以数独为例会很棒）

谢谢！

我希望为我的数独求解器优化我的回溯算法。

它现在的作用：

递归求解器函数采用具有各种给定值的数独游戏。

我将遍历拼图中的所有空槽，寻找可能性最小的槽，并获取值列表。

从值列表中，我将通过将列表中的一个值放入槽中来循环遍历它，并递归求解它，直到填满整个网格。

对于一些谜题，这个实现仍然需要非常长的时间，我希望进一步优化它。有谁知道我如何能够进一步优化这个？

如果您有兴趣，这是我的 Java 代码。