1

这是我用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
4

4 回答 4

3

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

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

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

于 2009-11-23T08:55:12.327 回答
3

我会避免诸如“移动代码”之类的事情。这被称为“巧合编程”（参见The Pragmatic Programmer）。像这样的编程不会让你成为一个更好的程序员。

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

于 2009-11-23T09:04:21.573 回答
2

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

那些不模仿人类推理逻辑的数独求解器是基于蛮力的。基本上，你需要一个回溯算法。你有你的 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 的返回值（但这种方法会非常慢）。

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

于 2009-11-23T10:03:06.680 回答
0

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

我以前也尝试过，但最后我看到了norvig 的代码，它工作得很好。

最后终于学会了他的代码。

于 2009-11-23T08:41:48.930 回答