一个很酷的算法来检查数独场？

有没有人知道一个简单的算法来检查数独配置是否有效？我提出的最简单的算法是(对于一个大小为n的板)Pseudocode

for each row
  for each number k in 1..n
    if k is not in the row (using another for-loop)
      return not-a-solution

..do the same for each column

但我确信必须有一个更好的(在更优雅的意义上)解决方案.效率非常不重要.

1> Radu094..：

---

您需要检查Sudoku的所有约束:

检查每一行的总和

检查每列的总和

检查每个盒子的总和

检查每行的重复数字

检查每列上的重复数字

检查每个方框上的重复数字

那不是6次检查......使用蛮力方法.如果你知道电路板的尺寸(即3x3或9x9),可以使用某种数学优化

编辑:和约束的解释:首先检查总和(并且如果总和不是45则停止)比检查重复更快(和更简单).它提供了一种丢弃错误解决方案的简单方法.

---

这个答案是错的.和约束是不必要的,因为在不违反3个实际约束之一的情况下,无法以任何其他方式获得45的和.

---

事先检查总和可能会提供比仅仅是天真的重复检查更好的性能,但这不是必需的.检查重复是否足够.

---

任何行或列的总和将是相同的,即1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45,并且欺骗检查是因为如果存在重复,则可以通过其他方式达到45.上述规则是获得有效配置所需的约束.

---

这个答案是对的.数独只有三个约束.

---

数独不涉及总和.

---

首先检查总和(如果总和不是45则停止)比检查重复要快得多.那些跳过数学分词的人可以停止这个请求吗？

---

我同意这种算法对于大多数现实检查来说会更快,但问题明确指出效率"非常不重要",他正在寻找"优雅".这个答案虽然总能产生正确答案,但肯定不是这里发布的最有效或最优雅的解决方案.我觉得它被选为答案,这很奇怪.不过,我认为它不值得投票.

2> daniel..：

---

Peter Norvig有一篇关于解决数独谜题的精彩文章(使用python),

http://norvig.com/sudoku.html

也许这对你想做的事情来说太过分了,但无论如何这都是一个很好的阅读

---

解决和检查是两回事,不是吗？

3> Luk..：

---

只是一个想法:你不需要检查每个3x3平方的数字吗？

我试图弄清楚是否有可能在没有正确的数独的情况下满足行和列条件

---

我现在不知道这是真的:第一行1..9,第二行2..9,1,第三行3..9,1,2 ...将导致正确的行和列,但不是3x3正方形.或者我在这里想念一些东西？

4> SPWorley..：

---

检查每一行,每列和每个框,使其包含数字1-9,不重复.这里的大多数答案已经讨论过了

但如何有效地做到这一点？答:使用类似的循环

result=0;
for each entry:
  result |= 1<<(value-1)
return (result==511);

每个数字将设置结果的一位.如果所有9个数字都是唯一的,则将设置最低的9位.所以"检查重复"测试只是检查所有9位是否设置,这与测试结果== 511相同.您需要执行其中的27个检查..每个行,列和框一个.