用Python编写Sudoku Solver

Question

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

不管我看了多少时间，移动代码，我似乎没有运气。

有谁可以帮我？

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

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

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

编辑unittest是你的朋友。

Answer 2

我会避免“移动代码”之类的东西。这称为“巧合编程” (参见务实的程序员)。这样的编程不会让你成为一个更好的程序员。

相反，你应该拿出一张纸和一支铅笔，开始思考应该如何工作。然后，阅读代码并仔细编写它实际上所做的事情。只有当你明白的时候，才能回到电脑终端。

Answer 3

我想以一种可以编写实际代码的方式来帮助您，下面是一些解释和一些伪代码。

那些不模仿人类推理逻辑的sudoku解说员是基于蛮力的。基本上，你需要一个回溯算法。您有您的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!

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

原来的sudokus只有一个解决方案。您可以将此方法扩展到具有这些方法的sudokus的不同解决方案，方法是尝试任何备选方案，而不考虑解题的返回值(但这种方法会非常慢)。

有一个很好的技巧来找出一个sudoku是否有多个解决方案。首先，在解决问题的每一次调用中，按自然顺序试一试候选人。那就倒着试试。然后再次执行这两个步骤，但是这次从sudoku的最后一个单元格运行算法，然后向后移动。如果这四个解是相同的，那么它只有一个解。不幸的是，我没有正式的证据，但它似乎一直有效。我试着证明这一点，但我对图表没那么在行。