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

Question

有没有人知道一个简单的算法来检查数独配置是否有效？我提出的最简单的算法是(对于一个大小为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

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

Answer 1

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

• 检查每一行的总和
• 检查每列的总和
• 检查每个盒子的总和
• 检查每行的重复数字
• 检查每列上的重复数字
• 检查每个方框上的重复数字

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

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

Answer 2

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

http://norvig.com/sudoku.html

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

Answer 3

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

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

Answer 4

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

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

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

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

Answer 5

这是我在 Python 中的解决方案，我很高兴看到它是迄今为止最短的一个 :)

编码：

def check(sud):
    zippedsud = zip(*sud)

    boxedsud=[]
    for li,line in enumerate(sud):
        for box in range(3):
            if not li % 3: boxedsud.append([])    # build a new box every 3 lines
            boxedsud[box + li/3*3].extend(line[box*3:box*3+3])

    for li in range(9):
        if [x for x in [set(sud[li]), set(zippedsud[li]), set(boxedsud[li])] if x != set(range(1,10))]:
            return False
    return True  

和执行：

sudoku=[
[7, 5, 1,  8, 4, 3,  9, 2, 6],
[8, 9, 3,  6, 2, 5,  1, 7, 4], 
[6, 4, 2,  1, 7, 9,  5, 8, 3],
[4, 2, 5,  3, 1, 6,  7, 9, 8],
[1, 7, 6,  9, 8, 2,  3, 4, 5],
[9, 3, 8,  7, 5, 4,  6, 1, 2],
[3, 6, 4,  2, 9, 7,  8, 5, 1],
[2, 8, 9,  5, 3, 1,  4, 6, 7],
[5, 1, 7,  4, 6, 8,  2, 3, 9]]

print check(sudoku)