Python递归数独求解器

Question

这是递归数独求解代码，这不是学校作业。我不知道如何让它通过我以前的 Action “备份”。它卡在 第一行 的末尾，因为该位置没有有效数字，只是一直试图找到适合该位置的数字。我遇到问题的功能是 check。

在阅读了您的回答后，我对这个问题有了更进一步的了解，但还远远不够。它一直返回并退出递归

import sys

class Board:

    def __init__(self, grid):
        self.grid = grid
        self.ogrid = grid

    def get_col(self, col):
        column = []
        for i in self.grid:
           column.append(str(i[col]))
        return column

    def get_row(self, row):
        return self.grid[row]

    def check_row(self, r, val):
        row = self.grid[r]
        for i in range(0,9):
            if str(val) in row:
                return False

        return True

    def check_col(self, column, val):
        col = self.get_col(column)
        for i in range(0,9):
            if str(val) in col:
                return False

        return True

    def check_square(self, x, y, val):
        col = (y//3)*3
        row = (x//3)*3
        s = ''
        for i in range(row, row+3):
            for j in range(col, col+3):
                s += str(self.grid[i][j])
        if str(val) in s:
                return False

        return True       

    def check_cell(self, x, y, val):
    if self.check_col(y, val) == False:

        return False
    elif self.check_row(x, val) == False:

        return False
    elif self.check_square(x, y, val) == False:

        return False
    return True


def check(self, x, y):

        if y == 9:
            y = 0
            x += 1

        if x == 9:  
            self.print_board()
            sys.exit()

        if self.ogrid[x][y] == '.':
            for val in range(1,10):
                if self.check_cell(x, y, val): 
                    self.grid[x][y] = str(val)
                    self.check(x, y+1)
                ##I don't think the reset is working and I'm not sure why
                if self.ogrid[x][y] == '.': #reset index
                    self.grid[x][y] = '.'
                    self.print_board() #Notice it never prints a '.' in spots that have changed
        else:
            self.check(x,y+1)
        return

    def print_board(self):
        for i in range(0,9):
            for j in range(0,9):
                sys.stdout.write(self.grid[i][j])
                if j == 2 or j == 5:
                    sys.stdout.write(' ')
            if i == 2 or i == 5:
                sys.stdout.write('\n')
            print('')

def main():

    f = open("./easySudoku.txt",'r')
    s = ''

    grid = []
    row = []
    for line in f:
        s += line
        print line
    s = s.replace(' ','')
    s = s.replace('\n','')

    for i in range(0,9):
        row = []
        for j in range(0,9):
            row.append(s[(i*9) + j])
        grid.append(row)

    sudoku = Board(grid)
    sudoku.check(0,0, 1)

if __name__ == "__main__":
    main()

这里是检查函数应该如何工作

check takes an x and y coordinate for the board and starts at 0,0 it runs through a for loop from 1-9 and sets the first value that works at that index and then moves to the next index. When it reaches the end of a row it moves down one row and back to the first column. If no values work at an index then reset current index to '.' and move index back one and continue counting towards 9. i.e. if current value at index 0,0 is 2 then continue to 3. If 3 works then move forward one index so on and so forth until the board has been filled. For the simplistic answer it tries every value, 1-9, at every empty index

如果不清楚，请告诉我

这也是我正在使用的开发板

..6 ..7 3..
.18 ..9 .5.
5.. ... .64

92. .8. ...
... 763 ...
... .9. .75

63. ... ..8
.9. 3.. 52.
..2 4.. 6..

Answer 1

我为检查您的代码所做的工作:将此行添加为您的 check 方法的第一行:

raw_input('x: %d, y: %d, val: %d' % (x,y,val))

并在插入数字后打印板。

看起来您的求解器在 (x,y) = (0,3) 处犯了第一个错误。它检查所有不超过 9 的数字，然后将 9 放在那里。根据您的算法，它应该放一个 1。挂断是您的 check_square 方法。你应该有

col = (y//3)*3
row = (x//3)*3

修复后，下一个错误出现在 (x,y) = (1,8)，从 self.check(1, 8, 1) 开始>。这个正方形(一直到 self.check(1, 8, 9))没有合法值(到目前为止使用您的算法)。所以接下来调用 self.check(1, 8, 10)。由于 val==10，它返回，然后在对 self.check(1, 8, 9) 的调用中，最后一行，self.check (x, y-1, val+1)，被调用，即 self.check(1, 7, 10)。它当然也会立即返回，因为 val == 10。我们回到 self.check(1, 8, 8) 并调用方法定义的最后一行。接下来要执行的是 self.check(1, 7, 9)，它会生成下一个 self.check(1, 8, 1)。看起来熟悉？我们已经在这里，同时没有状态变化。不知不觉中，这变成了一个死循环。

那是不是很困惑？当然是。程序员试图避免递归是有原因的，除非在教授递归概念时。追踪这些类型的递归错误很困难，但只需打印几行即可完成。

附言你的算法很有趣。我想知道你是在哪里找到它的……这绝对不是人类的游戏方式(包括所有的猜测和编辑)。 FWIW，我首先只会在棋盘上插入一个值，如果该值是该方 block 的唯一合法移动，并且仅当棋盘上的所有空白方 block 都不明确时才进行猜测。

编辑后编辑

在顶部添加标准库的一部分import copy并将__init__更改为self.ogrid = copy.deepcopy(grid)。应该可以解决你的问题。参见 https://stackoverflow.com/a/2612815/2100286 .您创建网格复制版本的方法实现了相同的目的。