求解数独问题的回溯算法

Question

我在学习算法的理论和它们可能的解决方法方法在这个案例中，我遇到了一些回溯的问题。我想写一个填充数独的函数。但它什么也没印出来。错误在哪里？ 函数defsett（i，j）以两个数字作为输入，这两个数字是所选数字的坐标，并设置两个整数（w和o），这两个整数是输入数字的3x3部分的起点。 相反，数独函数递归地尝试用数独规则填充矩阵。你知道吗

# defsett = returns the coordinates of the first cell of the section 3x3 
# where is the cell [i,j]
def defsett(i,j):
    if(0<=i<=2):
        if(0<=j<=2):
            return (0,0)
        elif(3<=j<=5):
            return (0,3)
        elif(6<=j<=8):
            return (0,6)
    elif(3<=i<=5):
        if(0<=j<=2):
            return (3,0)
        elif(3<=j<=5):
            return (3,3)
        elif(6<=j<=8):
            return (3,6)
    else:
        if(0<=j<=2):
            return (6,0)
        elif(3<=j<=5):
            return (6,3)
        elif(6<=j<=8):
            return (6,6)
M = [[5,3,0,0,7,0,0,0,0],
     [6,0,0,1,9,5,0,0,0],
     [0,9,8,0,0,0,0,6,0],
     [8,0,0,0,6,0,0,0,3],
     [4,0,0,8,0,3,0,0,1],
     [7,0,0,0,2,0,0,0,6],
     [0,6,0,0,0,0,2,8,0],
     [0,0,0,4,1,9,0,0,5],
     [0,0,0,0,8,0,0,7,9]]

# n = matrix side
# i = index of rows
# j = index of cols

def sudoku(n,i,j,M):
        if(i==n):
            print(M)
        elif(j==n):
            j=0
            i=i+1
            sudoku(n,i,j,M)
        else:
            if(M[i][j]==0):
                for number in range(1,n+1):

                    xInRows = False
                    xInCols = False
                    xInSection = False

   # checking if number already present in this row 
                    for k in range(n): 
                        if (number == M[i][k]):
                            xInRows = True

   # checking if number already present in this cols 
                    for k in range(n):
                        if(number == M[k][j]):
                            xInCols = True

                    w,o=defsett(i,j) # first cell of this section

   # checking if number already present in this section 3x3
                    for t in range(w,w+3):
                        for b in range(o,o+3):
                            if(number == M[t][b]):
                                xInSection = True

                    if(not(xInRows) and not(xInCols) and not(xInSection)):
                        M[i][j] = x
                        sudoku(n,i,j+1,M)
            else:
                sudoku(n,i,j+1,M)
sudoku(9,0,0,M)
-----
For this input works:
M = [[5,3,0,0,7,0,0,0,0],
     [6,0,0,1,9,5,0,4,8],
     [1,9,8,3,4,2,5,6,7],
     [8,5,9,7,6,1,4,2,3],
     [4,2,6,8,5,3,7,9,1],
     [7,1,3,9,2,4,8,5,6],
     [9,6,1,5,3,7,2,8,4],
     [2,8,7,4,1,9,6,3,5],
     [3,4,5,0,8,6,1,7,9]]
For this doesn't:
M = [[5,3,0,0,7,0,0,0,0],
     [6,0,0,1,9,5,0,0,8],
     [1,9,8,3,4,2,5,6,7],
     [8,5,9,7,6,1,4,2,3],
     [4,2,6,8,5,3,7,9,1],
     [7,1,3,9,2,4,8,5,6],
     [9,6,1,5,3,7,2,8,4],
     [2,8,7,4,1,9,6,3,5],
     [3,4,5,0,8,6,1,7,9]]

Answer 1

什么都不打印的原因很简单：sudoku()没有进展到i == 9曾经产生True。所以让我们分析一下这是怎么发生的。。。你知道吗

1. i == 9⇒带解决方案退出
2. i != 9 and j == 9⇒下一行递归；sudoku(9, i+1, 0, M)
3. i != 9 and j != 9
   1. M[i][j] != 0⇒下一列递归sudoku(9, i, j+1, M)
   2. M[i][j] == 0⇒尝试输入一个数字
      1. 找到候选项number⇒设置M[i][j] = number（不M[i][j] = x）并使用下一列sudoku(9, i, j+1, M)进行递归

这就是整个决策过程。一旦sudoku()退出，这就是M：

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

为了理解出了什么问题，假设您在第八列中放置了4之后调用sudoku(9, 0, 8, M)。。。你知道吗

1是唯一一个还没有放在这一行的数字，但在这里是禁止的，因为它已经出现在第五行（M[4][8]）。sudoku(9, 0, 8, M)退出，因为没有其他号码可以尝试。从这里开始，控件在调用堆栈中向上移动，因为没有人能够在其他任何地方放置1。为什么1这么重要？因为所有其他的数字都已经放在这一行的某个地方了，而且当sudko()回溯时，不会改变！

解决方法很简单：在递归步骤之后添加一行，在该步骤中您已经填写了一个数字，这将撤消对正确回溯的更改。你知道吗

(...)
                    if(not(xInRows) and not(xInCols) and not(xInSection)):
                        M[i][j] = x
                        sudoku(n,i,j+1,M)
                        M[i][j] = 0
(...)

仅此一项就可以使给定的M完成sudoku()。不过，我不能保证它会找到任何M的解决方案。；—）