回溯在 SUDOKU 中失败

Question

我一直在尝试在 Python 中实现数独，但回溯根本不起作用。当我输入 0 的 4x4 网格时，我得到了输出，但大多数时候它无法提供 3x3 的结果。此测试用例正确进行，直到它到达第二行的最后一个元素。

import math

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

#solution=[[0 for x in range(4)] for y in range(4)]

N=9
row=0
col=0

def positionFound():
    global row,col
    for x in range(N):
        for y in range(N):
            if solution[x][y] is 0:
                row,col=x,y
                return row,col
    return False

def isSafe(row,col,num):
    global N
    for c in range(N):
        if solution[row][c] is num:
            return False
    for r in range(N):
        if solution[r][col] is num:
            return False
    r=row-row%int(math.sqrt(N))
    c=col-col%int(math.sqrt(N))

    for x in range(r,r+int(math.sqrt(N))):
        for y in range(c,c+int(math.sqrt(N))):
            if solution[x][y] is num:
                return False

    return True
back=1

def sudoku(solution):
    global row,col
    if positionFound() is False:
        print('SUCCESS')
        for x in solution:
            print(x)
        return True


    for number in range(1,N+1):
        if isSafe(row,col,number):
            solution[row][col]=number
            if sudoku(solution) is True:
                return True
            solution[row][col]=0


    return False


sudoku(solution)
for x in solution:
     print(x)

输出：

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

Answer 1

你的回溯不起作用的原因是你没有实施回溯。一旦您未能在给定位置放置数字，您就无法将 return 您的 [row, col] 光标移至前一个位置。您需要采用一种方法来了解先前填充的职位是什么，并使用该职位的下一个合法编号继续。您的递归保留了堆栈中以前的棋盘位置，但您丢失了光标位置——并且您的重试循环假定它已重置。

一个很大的可能性是创建 row 和 col 局部变量，使它们与它们描述的 solution 网格保持一致。使它们成为参数传递的一部分，以便堆栈为您维护这些值。

回溯在 SUDOKU 中失败

Backtracking is failing in SUDOKU

python

recursion

sudoku

backtracking