Python 递归数独求解器不返回解决方案

Question

我的最终代码如下所示

import numpy as np

sudoku = np.array([[0, 9, 0, 0, 5, 0, 6, 0, 8],

                   [0, 0, 0, 7, 1, 0, 3, 5, 0],

                   [2, 1, 0, 0, 0, 0, 7, 0, 4],

                   [0, 0, 1, 5, 0, 0, 0, 0, 6],

                   [6, 3, 0, 2, 0, 8, 0, 4, 5],

                   [7, 0, 0, 0, 0, 4, 9, 0, 0],

                   [9, 0, 3, 0, 0, 0, 0, 2, 1],

                   [0, 4, 8, 0, 2, 7, 0, 0, 0],

                   [5, 0, 6, 0, 8, 0, 0, 3, 0]])

#Checking if the number (n) can be placed there (row, col)

def check(sudoku, row, col, n):

    # Row check

    if np.sum(sudoku[row,:] == n) != 0: return False;

    # Col check

    if np.sum(sudoku[:,col] == n) != 0: return False;

    # Sqr check

    row0, col0 = (row//3)*3, (col//3)*3

    if np.sum(sudoku[row0:row0+3,col0:col0+3] == n) != 0: return False;

    return True

def solve_sudoku(sudoku):

    rows, cols = np.where(sudoku == 0)

    for row in rows:

        for col in cols:

            for num in range(1, 10):

                if check(sudoku, row, col, num):

                    sudoku[row, col] = num

                    solve_sudoku(sudoku)

                    sudoku[row, col] = 0

            return

    print(sudoku)

    return sudoku

solved = solve_sudoku(sudoku)

我的问题是，即使解决方案成功打印如下所示，解决的变量只是一个 NoneType 并且不存储任何内容。

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

 [8 6 4 7 1 9 3 5 2]

 [2 1 5 8 3 6 7 9 4]

 [4 8 1 5 9 3 2 7 6]

 [6 3 9 2 7 8 1 4 5]

 [7 5 2 1 6 4 9 8 3]

 [9 7 3 6 4 5 8 2 1]

 [1 4 8 3 2 7 5 6 9]

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

TL;DR该函数打印解决方案但不返回任何内容。我应该如何保存打印的溶液？

Answer 1

考虑这段代码：if check(sudoku, row, col, num):     sudoku[row, col] = num     solve_sudoku(sudoku)     sudoku[row, col] = 0  # undo this move如果数独是可解的，则solve_sudoku(sudoku)调用最终会找到解决方案。当你得到解决方案时，你应该立即停止使用 进行回溯return。否则，下一行将sudoku[row, col] = 0撤消您找到的解决方案，并进一步迭代继续尝试下一个可能的数字。由于数独只有一个解，因此没有必要在找到解后检查更多的数字。您可以只返回一个真值来结束递归。例如，您可以这样编写代码：if solve_sudoku(sudoku):     return True或者if solve_sudoku(sudoku):     return sudoku这可以防止sudoku[row, col] = 0擦除解决方案并最终在递归调用堆栈展开后将解决的网格返回给初始调用者。

Answer 2

def check(grid, num, x, y):    for i in range(9):        if grid[i][y] == num:            return False    for j in range(9):        if grid[x][j] == num:            return False    x0 = (x//3) * 3    y0 = (y//3) * 3    for i in range(3):        for j in range(3):            if grid[x0+i][y0+j] == num:                return False    return Truedef solve(grid):    for i in range(9 + 1):        if i==9:            return True        for j in range(9):            if grid[i][j] == 0:                for num in range(1,10):                    if check(grid, num, i, j):                        grid[i][j] = num                        if solve(grid):                            return True                        grid[i][j] = 0                return False这应该对你有用。它不返回数组，而是修改它。所以如果你通过了solve(sudoku_grid) 然后打印 sudoku_grid 它会给你解决的输出

Answer 3

当使用完全填充的数独数组（没有任何剩余零）调用时，而不是在顶级递归调用中，会print(sudoku)发生该调用。solve_sudoku每次solve_sudoku使用不完整的数独数组调用时，您都在左上角的零填充单元格中测试从一到十之间的每个数字，如果该数字可以放置在该单元格中，则将其放置在那里，尝试解决其余的问题网格，然后将单元格设置回零。一旦您对 1 到 10 之间的每个数字执行此操作，您就会返回None，这就是您看到None从顶级solve_sudoku调用返回的原因。

Answer 4

import numpy as npsudoku = np.array([[0, 9, 0, 0, 5, 0, 6, 0, 8],                   [0, 0, 0, 7, 1, 0, 3, 5, 0],                   [2, 1, 0, 0, 0, 0, 7, 0, 4],                   [0, 0, 1, 5, 0, 0, 0, 0, 6],                   [6, 3, 0, 2, 0, 8, 0, 4, 5],                   [7, 0, 0, 0, 0, 4, 9, 0, 0],                   [9, 0, 3, 0, 0, 0, 0, 2, 1],                   [0, 4, 8, 0, 2, 7, 0, 0, 0],                   [5, 0, 6, 0, 8, 0, 0, 3, 0]])solved = np.zeros_like(sudoku)def check(arg, row, col, n):    if np.sum(arg[row,:] == n) != 0: return False;    if np.sum(arg[:,col] == n) != 0: return False;    row0, col0 = (row//3)*3, (col//3)*3    if np.sum(arg[row0:row0+3,col0:col0+3] == n) != 0: return False;    return Truedef solve_sudoku(arg):    global solved    rows, cols = np.where(arg == 0)    for row in rows:        for col in cols:            for num in range(1, 10):                if check(arg, row, col, num):                    arg[row, col] = num                    solve_sudoku(arg)                    arg[row, col] = 0            return    solved = arg.copy()solve_sudoku(sudoku)我不知道这是否是优化代码的最佳方式，欢迎反馈。

Answer 5

问题出在您的代码中：                    solve_sudoku(sudoku)                     sudoku[row, col] = 0             return在第一行中，您进行递归，但忽略返回值，这会丢弃该调用及其下面的所有递归的任何返回值。在最后一行中，您返回 的默认值None。其中任何一个都会破坏递归返回值的连续性。