使用 Python 编写数独求解器

Question

这是我用 python 语言编写的数独求解器，当我运行这个程序时，更新函数和求解函数似乎有问题。

无论我花多少时间查看并移动代码，我似乎都没有运气

任何人都可以帮助我吗？

---

import copy


def display (A):

    if A:
        for i in range (9):
            for j in range (9):
                if type (A[i][j]) == type ([]): print A[i][j][0],
                else: print A[i][j]
            print
        print
    else: print A

def has_conflict(A):

    for i in range(9):
        for j in range(9):
            for (x,y) in get_neighbors(i,j):
                if len(A[i][j])==1 and A[i][j]==A[x][y]: return True
    return False


def get_neighbors(x,y):

    neighbors = []
    for i in range(3):
        for j in range(3):
            a = 3*(x / 3)+i
            b = 3*(y / 3)+j
            if (x,y) != (a,b):
                neighbors += [(a,b)]

    for i in range(9):
        if (x,y) != (x,i) and (x,i) not in neighbors:
            neighbors += [(x,i)]
        if (x,y) != (i,y) and (i,y) not in neighbors:
            neighbors += [(i,y)]

    return neighbors



def update(A,x,y,value):

    B = copy.deepcopy(A)
    B[x][y] = [value]
    for (i,j) in get_neighbors(x,y):
        if B[i][j] == B[x][y]:
            if len(B[i][j]) > 1: B[i][j].remove(value)
            else: return [] 
    if has_conflict(B) == True: return []
    else: return B


def solve(A):

    for x in range (9):
        for y in range(9):
            if len(A[x][y]) == 1: return A[x][y]
            if len(A[x][y]) > 1:
                lst = update(A,x,y,A[x][y])
                if len(lst[x][y]) > 1: solve(lst)
                if lst == []: return []
                if len(lst[x][y]) == 1: return lst
            else: return A[x][y]    



A=[]

infile = open('puzzle1.txt','r')

for i in range(9):

        A += [[]]
        for j in range(9):
            num = int(infile.read(2))
            if num: A[i] += [[num]]
            else: A[i] += [[1,2,3,4,5,6,7,8,9]]

for i in range(9):

        for j in range(9):
            if len(A[i][j])==1: A = update(A, i, j, A[i][j][0])
            if A == []: break
        if A==[]: break

if A<>[]: A = solve(A)

display(A)

---

以下是一些谜题：

谜题 1

0 0 0 2 6 0 7 0 1
6 8 0 0 7 0 0 9 0
1 9 0 0 0 4 5 0 0
8 2 0 1 0 0 0 4 0
0 0 4 6 0 2 9 0 0
0 5 0 0 0 3 0 2 8
0 0 9 3 0 0 0 7 4
0 4 0 0 5 0 0 3 6
7 0 3 0 1 8 0 0 0

谜题 2

1 0 0 4 8 9 0 0 6
7 3 0 0 0 0 0 4 0
0 0 0 0 0 1 2 9 5
0 0 7 1 2 0 6 0 0
5 0 0 7 0 3 0 0 8
0 0 6 0 9 5 7 0 0
9 1 4 6 0 0 0 0 0
0 2 0 0 0 0 0 3 7
8 0 0 5 1 2 0 0 4

谜题 3

0 2 0 6 0 8 0 0 0
5 8 0 0 0 9 7 0 0
0 0 0 0 4 0 0 0 0
3 7 0 0 0 0 5 0 0
6 0 0 0 0 0 0 0 4
0 0 8 0 0 0 0 1 3
0 0 0 0 2 0 0 0 0
0 0 9 8 0 0 0 3 6
0 0 0 3 0 6 0 9 0

---

Answer 1

我会避免诸如“移动代码”之类的事情。这称为“巧合编程”（请参阅务实的程序员）。像这样的编程并不会让你成为更好的程序员。

相反，您应该拿出纸和铅笔，开始思考事情应该如何运作。然后，阅读代码并仔细写出它实际的作用。只有明白了才回到电脑终端。

Answer 2

如果您想稳定代码，请为每个函数编写小测试用例，以确保它们正常工作。

对于您的情况，运行一个谜题，并确定哪个字段是错误的。然后猜测哪个函数可能会产生错误的输出。使用输入调用它，看看它到底做了什么。对您发现的每个错误重复此操作。

[编辑] 模块 unittest 是你的朋友。

Answer 3

我想以一种可以编写实际代码的方式帮助您，所以这里有一些解释和一些伪代码。

那些不模仿人类演绎逻辑的数独求解器是基于暴力的。基本上，您需要一个回溯算法。你有你的 has_conflict 方法，它首先检查候选人是否可以。然后你像这样编写回溯算法：

Solve(s):
    Pick a candidate.
    Does it have a conflict? If yes, go back, and pick another one.
    No more empty cells? Then cool, return True.
    Have you run out of candidates? Then it cant be solved, return False.

    At this point, it seems ok. So call Solve(s) again, lets see how it works 
    out with the new candidate.
    If Solve returned false, then after all it was a bad candidate. Go
    back to picking another one.
    If Solve returned True, then you solved the sudoku!

这里的主要思想是，如果你的猜测是错误的，尽管乍一看没有冲突，那么冲突将在调用树更深处的某个地方显现出来。

最初的数独只有一种解法。您可以将此方法扩展到具有数独的不同解决方案，方法是尝试任何候选方案，尽管有 Solve 的返回值（但使用此方法会非常慢）。

有一个很好的技巧可以找出数独是否有多个解决方案。首先在每次求解调用中按自然顺序尝试候选者。然后向后尝试。然后再次执行这两个步骤，但这次从数独的最后一个单元格向后运行算法。如果这四个解相同，则只有一个解。不幸的是我没有正式的证明，但它似乎一直有效。我试图证明这一点，但我不太擅长图表。

Answer 4

解决数独需要一些暴力方法，我在你的代码中没有看到这些方法。

我之前也尝试过这样做，但最后我看到了 norvig 的代码，它运行得非常完美。

并最终学习了他的代码。