用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

我想帮助你，让你能写出实际的代码，所以这里有一些解释和伪代码。

那些不模仿人类推理逻辑的数独解法，都是基于暴力破解的。简单来说，你需要一个回溯算法。你有一个叫做 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 2

我建议不要做一些像“随便移动代码”这样的事情。这种做法被称为“偶然编程”（可以参考《务实程序员》）。这样编程并不会让你成为更好的程序员。

相反，你应该拿出纸和笔，开始思考一下事情应该如何运作。然后，仔细阅读代码，写下它实际上做了什么。只有在你理解了之后，再回到电脑前。

Answer 3

如果你想让你的代码更稳定，那就为每个函数写一些小的测试案例，确保它们能正常工作。

在你的情况下，先运行一个程序，找出哪个地方出错了。然后猜测哪个函数可能会产生错误的结果。用输入去调用这个函数，看看它到底是怎么工作的。对你发现的每个bug都重复这个过程。

[编辑] 模块 unittest 是你的好帮手。