Python sudoku回溯

Question

我用一个简单的例子(sudoku)尝试回溯算法。我第一次尝试了另一种方法，取消了更多的可能性，但在得到同样的错误后，我切换到了一个更简单的解决方案。

1. 寻找第一个未解决的点
2. ，填充1到9之间的每一个数字，如果它是有效的

，则回溯新字段。

当我运行它并输出无效字段时，我可以看到，当算法退出递归调用时，递归调用中的点仍然是9(因此算法找不到该点的任何内容)。

例如，前两行看起来如下(它试图解决一个空字段)：

[1, 2, 3, 4, 6, 9, 9, 9, 9]

[9, 9, 9, 9, 9, 9, 9, 0, 0]

我认为这是一个引用错误，并在回溯调用中插入了[e for e in field]，这样旧字段就不会被更改，尽管这似乎没有帮助。

这是我的代码：

    for i in range(9):
        a = [field[i][j] for j in range(9) if field[i][j] != 0]
        if len(a) != len(set(a)):
            return False

    for i in range(9):
        a = [field[j][i] for j in range(9) if field[j][i] != 0]
        if len(a) != len(set(a)):
            return False

    for x in range(3):
        for y in range(3):
            a = []
            for addX in range(3):
                for addY in range(3):
                    spot = field[x * 3 + addX][y * 3 + addY]
                    if spot != 0:
                        a.append(spot)
            if len(a) != len(set(a)):
                return False

    return True

def findEmpty(field):

    for i in range(9):
        for j in range(9):
            if field[i][j] == 0:
                return i, j


def backtracking(field):

    find = findEmpty(field)
    if not find:
        return True, field
    else:
        x, y = find
 
    for i in range(1, 10):
        print(f"Trying {i} at {x} {y}")
        field[x][y] = i
        if isValid(field):
            s = backtracking([e for e in field])
            if s[0]:
                return s
        else:
            print("Not valid")
            for row in field:
                print(row)

    return False, None


field = [[0, 0, 0, 0, 1, 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 = backtracking(field)
if solution[0]:
    print("There was a solution. The field is:")
    for row in solution[1]:
        print(row)
else:
    print("No solution was found")

Answer 1

我做了一些研究，显然这确实是一个参考错误。对于我来说，导入pythons复制库并分配每个新字段，说f = copy.deepcopy(field)修复了这个问题(这也适用于复杂的示例)。

Answer 2

好的，根据我在日志中所看到的，当代码到达9，仍然没有得到答案时，它会回溯，但是将值保持在9。

因此，每次程序回溯时，它都会将值保留在9，然后再转到前一个值，这个值也可能会变为9，这是无效的，因为我们已经从其中返回的值是9。这会导致一个循环，程序将直接返回到起始位置，并将大部分插槽设置为9，正如您在您的示例中所看到的那样。

因此，解决方案是添加几行回溯()，如下所示。简而言之，额外的2行检查无效的答案是否为9，如果是，则将其重置为0，并返回到以前的值，直到得到有效的答案为止。

def backtracking(field):
    find = findEmpty(field)
    if not find:
        return True, field
    else:
        x, y = find

    for i in range(1, 10):
        print(f"Trying {i} at {x} {y}")
        field[x][y] = i
        if isValid(field):
            s = backtracking(field)
            if s[0]:
                return s
        else:
            print("Not valid")
            if field[x][y] == 9:
                field[x][y] = 0
            for row in field:
                print(row)

    return False, None

它给出的解决办法：

[2, 3, 4, 5, 1, 6, 7, 8, 9]
[1, 5, 6, 7, 8, 9, 2, 3, 4]
[7, 8, 9, 2, 3, 4, 1, 5, 6]
[3, 1, 2, 4, 5, 7, 6, 9, 8]
[4, 6, 5, 1, 9, 8, 3, 2, 7]
[8, 9, 7, 3, 6, 2, 4, 1, 5]
[5, 2, 8, 6, 4, 1, 9, 7, 3]
[6, 7, 3, 9, 2, 5, 8, 4, 1]
[9, 4, 1, 8, 7, 3, 5, 6, 2]

Answer 3

1-创建字典的行、科尔和方框(3x3单位)数组，以存储每行、各行和框中有数字的索引。

2-拍摄董事会的截图。运行一个for-循环并标记包含数字的点。

3-调用递归backtrack函数。

4-始终在递归函数中定义从递归中退出的大小写。

5-启动一个for-循环，查看哪个坐标是"."。如果你看到"."，应用步骤:6，7，8，9

现在我们需要在这里插入一个有效的数字。有效数字是指当前行、行和框中不存在的数字。

7-如果你找到一个有效的数字，把它插入董事会，并更新行，科尔，和框。

8-插入有效点后，我们调用下一个“”的backtrack函数。

9-当打电话给backtrack时，决定你在哪一点。如果您位于最后一列，则下一个回溯函数将从下一行和第0列开始。但是，如果您位于行中间，则只需增加下一个回溯函数的列参数。

10-如果在步骤5中，您的值不是"."，这意味着这里已经有一个有效的数字，所以根据位置的不同，调用下一个回溯。如果您位于最后一列，则下一个回溯函数将从下一行和第0列开始。但是，如果您位于行中间，则只需增加下一个回溯函数的列参数。

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        n=len(board)
        # create state variables,keep track of rows, cols and boxes
        rows=[{} for _ in range(n)]
        cols=[{} for _ in range(n)]
        boxes=[{} for _ in range(n)]
       # get the initial state of the grid
        for r in range(n):
            for c in range(n):
                if board[r][c]!='.':
                    val=board[r][c]
                    box_id=self.get_box_id(r,c)
                    boxes[box_id][val]=True
                    rows[r][val]=True
                    cols[c][val]=True
        # this backtracking just tells if shoul move to the next cell or not
        self.backtrack(board,boxes,rows,cols,0,0)
        
    def backtrack(self,board,boxes,rows,cols,r,c):
        # base case. If I hit the last row or col, means all digits were correct so far
        if r>=len(board) or c>=len(board[0]):
            return True
        # situation when cell is empty, fill it with correct value
        if board[r][c]==".":
            for num in range(1,10):
                box_id=self.get_box_id(r,c)
                box=boxes[box_id]
                row=rows[r]
                col=cols[c]
                str_num=str(num)
                # check rows, cols and boxes make sure str_num is not used before
                if self.is_valid(box,col,row,str_num):
                    board[r][c]=str_num
                    boxes[box_id][str_num]=True
                    cols[c][str_num]=True
                    rows[r][str_num]=True
                    # if I am the last col and I placed the correct val, move to next row. So first col of the next row
                    if c==len(board)-1:
                        if self.backtrack(board,boxes,rows,cols,r+1,0):
                            return True
                    # if I am in col between 0-8, move to the col+1, in the same row
                    else:
                        if self.backtrack(board,boxes,rows,cols,r,c+1):
                            return True
                    # If I got a wrong value, then backtrack. So clear the state that you mutated
                    del box[str_num]
                    del row[str_num]
                    del col[str_num]
                    board[r][c]="."
       # if cell is not empty just call the next backtracking
        else:
            if c==len(board)-1:
                if self.backtrack(board,boxes,rows,cols,r+1,0):
                    return True
            else:
                if self.backtrack(board,boxes,rows,cols,r,c+1):
                    return True
        return False
                
    def is_valid(self,box,row,col,num):
        if num in box or num in row or num in col:
            return False
        else:
            return True
        
        
    # a helper to get the id of the 3x3 sub grid, given row and column
    def get_box_id(self,r,c):
        row=(r//3)*3
        col=c//3
        return row+col