python之用 Python 编写数独求解器

这是我用 python 语言编写的 Sudoku Solver，当我运行这个程序时，Update 函数和 Solve 函数似乎有问题。

无论我翻了多少遍代码，我似乎都没有运气

谁能帮帮我？

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 

请您参考如下方法:

我会避免诸如“四处移动代码”之类的事情。这叫做 "Programming by Coincidence" (参见 The Pragmatic Programmer)。像这样编程不会让你成为更好的程序员。

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