Python递归数独求解器

Question

这是一个递归解决数独的代码，不是学校作业。我无法想出如何通过先前的步骤来“回退”。由于第一行没有有效数字，它会在第一行末尾卡住，并继续尝试找到适合那个位置的数字。我遇到问题的函数是“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函数的预期工作方式：

check函数接收棋盘的x和y坐标，并从0,0开始运行一个for循环，从1到9设置第一个在该索引下有效的值，然后移动到下一个索引。当它到达一行的末尾时，它会向下移动一行并回到第一列。如果在索引处没有任何值有效，则将当前索引重置为'.'，并将索引向后移动一个并继续计数到9。例如，如果索引0,0处的当前值为2，则继续到3。如果3有效，则向前移动一个索引，以此类推，直到填满棋盘。对于简单的答案，它尝试在每个空索引处使用每个值1-9。

如果不清楚，请告诉我。

此外，这是我使用的棋盘。

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

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

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

- SirParselot

---

你遇到的一个问题是 self.grid 和 self.ogrid 是同一个对象。如果你改变其中一个，那么另一个也会被改变。你应该使用 deepcopy 或以不同的方式存储网格数据。 - James Pringle

@JamesPringle 我注意到在你发布更新之前，当我打印出 ogrid 时，它正在改变，尽管它不应该这样。 - SirParselot

Answer 1

问题在于您似乎尝试每个数字都递归一步，这将消耗所有合理的堆栈。我建议您也使用迭代，并使用return进行备份（这样您应该只使用81个堆栈帧左右 - 当您获得1000级堆栈帧时它会失败）。

我以前做过一个解算器，它可以很快地找到解决方案...

- skyking

---

我之前用C++解决过这个问题，速度相当快。目前我正在尝试一种不使用二维数组的不同方法，但是现在我读到这篇文章后认为它会有相同的问题。我注意到我对每个数字进行递归处理，这给我带来了问题，而且我无法想出如何解决它，但是现在应该可以解决了。 - SirParselot

Answer 2

我在检查您的代码时所做的事情：将此行添加为您的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

修复了之前的错误后，在坐标为（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)。很熟悉吧？我们已经到这里了，而且在此期间没有状态改变。甚至没有意识到，这变成了一个无限循环。

这让人困惑吗？当然困惑。程序员尽量避免递归，除了教递归的概念时。追踪这些递归错误很困难，但是加上几行打印语句就可以解决。

附言：你的算法很有趣。我想知道你从哪里找到它的......它绝对不是人类玩游戏的方式（所有的猜测和编辑）。为了方便起见，我将首先仅在该值是该方格唯一合法移动时将一个值插入到棋盘中，并且只有在棋盘上的所有空白方格都是模棱两可的时候才会猜测。

在你的修改之后：

在顶部添加import copy，这是标准库的一部分，并在__init__中更改为self.ogrid = copy.deepcopy(grid)。应该可以解决你的问题。请参见https://dev59.com/XXE85IYBdhLWcg3wyGp_#2612815。创建网格的副本的方法实现了相同的效果。

- James Pringle

---

y//3是什么意思？我前几天看到了，但是轻松搜索后没有找到答案。 - SirParselot

啊，这很有趣也很有用。如果那是一个 bug 的话，我可能需要很长时间才能找出来。 - SirParselot

虽然它没有解决问题，但它确实修复了我的check_square函数，所以对此给予加分。如果你没有注意到，我已经更新了我的代码，虽然更接近目标，但还不完全符合要求。 - SirParselot

我不确定你的 check 函数应该做什么。算法是什么？你能给一个链接或描述一下吗？ - James Pringle

我会在帖子中描述它。 - SirParselot

Answer 3

我不理解这段代码片段：

        if y == -1:
            y = 8
            x -= 1

如果y等于您正在设置的行中的最后一个位置，则将其设置为8，这是该行中最后一个位置的索引吗？这可能是导致它无法正确进行的原因吗？

- userE

---

由于它是一个2D数组，当“y”低于“0”时，它需要回绕，因此向上移动一行并将“y”设置为最后一列。“x”是行，“y”是列。如果您将其绘制出来，很容易理解。 - SirParselot

Answer 4

好了，我解决了我的问题！

这是我所做的。我采用了@Skyking给我的建议，只对索引进行递归，而不是按原始索引值进行递归。第二件我改变的事情是采用@James Pringle关于如何修复我的check_square函数和复制网格的建议，所以当grid改变时，ogrid不会发生变化。 由于我不能给两个绿色勾，所以我把它给了@James Pringle，因为他/她帮助我最多，但是如果没有@Skyking的建议，我就无法得到它。

这是完成的代码。

import sys
import copy

class Board:

    def __init__(self, grid):
        self.grid = grid
        self.ogrid = copy.deepcopy(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]

        if str(val) in row:
            return False
        return True

    def check_col(self, column, val):
        col = self.get_col(column)

        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)

                    if self.ogrid[x][y] == '.':
                        self.grid[x][y] = self.ogrid[x][y]                    
            else:
                self.check(x,y+1)
            return True

    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

    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)
    print('shouldn\'t be here')

if __name__ == "__main__":
    main()

- SirParselot