python - 回溯数独求解，在 C 中工作，在 Python 中出错

Question

class sudoku:
grid=[]
    #using constructor for accepting the grid
    def __init__(self):
        grid=[]
        for i in xrange(9):
            grid.append([])
        print("Enter elements, values 0 to 9, 0 for blank, press enter after each row")
        for i in xrange(9):
            for x in raw_input().split():
                grid[i].append(int(x))
        self.grid = grid
        print self.grid
    #checking whether  the number is legal
    def check_row(self,row,num):
        col=0
        while col<9:
            if self.grid[row][col]==num:
                return 0
            col=col+1
        return 1
    def check_col(self,col,num):
        row=0
        while row<9:
            if self.grid[row][col]==num:
                return 0
            row=row+1
        return 1
    def check_grid(self,row,col,num):
        row=(row/3)*3
        col=(col/3)*3
        r=0
        while r<3:
            c=0
            while c<3:
                if self.grid[row+r][col+c]==num:
                    return 0
                c=c+1
            r=r+1
        return 1
    def navigate(self,row,col):
        if col<8:
            self.solve_sudoku(row,col+1)
        self.solve_sudoku(row+1,0)
    def solve_sudoku(self,row,col):
        if row>8:
                self.display()
        if self.grid[row][col]!=0:
            self.navigate(row,col)
        else:
            ctr=1
            while ctr<=9:
                if self.check_row(row,ctr)==1 and self.check_col(col,ctr)==1 and self.check_grid(row,col,ctr)==1:
                    self.grid[row][col]=ctr
                    self.navigate(row,col)
                ctr=ctr+1
            self.grid[row][col]=0
        return False
    def display(self):
        print "solution"
        i=0
        j=0
        for i in xrange (9):
            for j in xrange (9):
                print self.grid[i][j],
            print 
        input("Enter key to continue")
obj=sudoku()
obj.solve_sudoku(0,0)

图像给出了代码的输出

问题:相同的代码在 C 中运行良好，现在我将其更改为 python，它无法运行，当函数返回回调时发生错误，我无法确定真正的问题。在第一组迭代之后，它不会返回到前一个函数调用并执行其余部分。 我会将输出粘贴到这里

INPUT
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
OUTPUT
[[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]]
solution
1 2 3 4 5 6 7 8 9
4 5 6 1 2 3 0 0 0
7 8 9 0 0 0 0 0 0
2 1 4 3 6 5 8 7 0
3 6 5 2 1 4 9 0 0
8 7 0 0 0 0 0 0 0
5 3 1 6 4 2 0 0 0
6 4 2 5 3 1 0 0 0
9 0 0 0 0 0 0 0 0
Enter key to continue
Traceback (most recent call last):
  File "C:/Users/johan/Desktop/sudoku.py", line 71, in <module>
    obj.solve_sudoku(0,0)
  File "C:/Users/johan/Desktop/sudoku.py", line 56, in solve_sudoku
    self.navigate(row,col)
  File "C:/Users/johan/Desktop/sudoku.py", line 44, in navigate
    self.solve_sudoku(row,col+1)
  File "C:/Users/johan/Desktop/sudoku.py", line 56, in solve_sudoku
    self.navigate(row,col)
  File "C:/Users/johan/Desktop/sudoku.py", line 44, in navigate
    self.solve_sudoku(row,col+1)
  File "C:/Users/johan/Desktop/sudoku.py", line 56, in solve_sudoku
    self.navigate(row,col)
  File "C:/Users/johan/Desktop/sudoku.py", line 44, in navigate
    self.solve_sudoku(row,col+1).....

Answer 1

Tom Zych 提出了一个重要的观点，但您的代码还有其他问题。

• 当您找到解决方案时，将其打印出来，但不要继续递归。这意味着您应该在打印后返回或将递归放在找到的解决方案的 else 子句中。

• 在 navigate 中，您还应该使对 solve_sudoku 的两次调用互斥。在您的情况下，如果解决当前行没有产生可行的结果，则该算法将继续处理下一行。这就是为什么您的解决方案中有这么多零。

• 当您在回溯后将单元格设置回零时，您应该在递归函数调用后立即这样做。否则，非零数据可能会影响其他解决方案的检查。 (这里可能不重要，但马上收拾是很好的作风。)

• 如果您使用 Python 惯用法进行循环而不是模拟 C 的 while 循环，代码会更清晰。

这是您的代码的工作版本:

class Sudoku:
    def __init__(self):
        grid=[]
        for i in xrange(9):
            grid.append([])

        print("Enter elements, values 0 (blank) to 9:")
        for i in xrange(9):
            for x in raw_input().split():
                grid[i].append(int(x))

        self.grid = grid
        print self.grid

    def check_row(self, row, num):
        for col in xrange(9):
            if self.grid[row][col] == num:
                return False
        return True

    def check_col(self, col, num):
        for row in xrange(9):
            if self.grid[row][col] == num:
                return False
        return True

    def check_grid(self, row, col, num):
        row = (row / 3) * 3
        col = (col / 3) * 3

        for r in xrange(3):
            for c in xrange(3):
                if self.grid[row + r][col + c] == num:
                    return False

        return True

    def check(self, row, col, num):
        return (self.check_row(row, num)
            and self.check_col(col, num)
            and self.check_grid(row, col, num));

    def navigate(self, row, col):
        if col < 8:
            self.solve(row, col + 1)
        else:
            self.solve(row + 1, 0)

    def solve(self, row, col):
        if row > 8:
            self.display()
        else:
            if self.grid[row][col]:
                self.navigate(row, col)
            else:
                for num in xrange(1, 10):
                    if self.check(row, col, num):
                        self.grid[row][col] = num
                        self.navigate(row, col)
                        self.grid[row][col] = 0



    def display(self):
        print "solution"
        for i in xrange(9):
            for j in xrange(9):
                print self.grid[i][j], 
            print 
        print

sudoku = Sudoku()
sudoku.solve(0, 0)