Python 递归数独求解器没有 Return 解决方案

Question

我尝试优化了this代码，我的最终代码如下图

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)

我的问题是，即使解决方案成功打印如下所示，变量 solved 只是一个 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 该函数打印解决方案，但 returns 什么都不打印。我应该如何存储打印的解决方案？

Answer 1

问题出在您的代码中：

                    solve_sudoku(sudoku)
                    sudoku[row, col] = 0
            return

在第一行中，您重复了，但您忽略了 return 值，该值会丢弃来自该调用及其下方所有递归的任何 return 值。

在最后一行中，您 return 默认值 None。这些中的任何一个都会破坏递归 return 值的连续性。

Answer 2

当使用 completely-filled 数独数组（一个没有任何剩余零的数组）调用 solve_sudoku 时，会发生 print(sudoku) 调用，而不是在 top-level 递归调用中。

每次使用不完整的数独数组调用 solve_sudoku 时，您正在测试 upper-leftmost zero-filled 单元格中 1 到 10 之间的每个数字，以及是否可以放置该数字在单元格中，您将它放在那里，尝试解决网格的其余部分，然后将单元格设置回零。对 1 到 10 之间的每个数字执行此操作后，您 return None，这就是为什么您从 top-level [=] 中看到 None returned 11=] 呼叫.

Answer 3

几个小时后，我想到了这个解决方案。 已解决 现在存储解决方案。

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]])
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 True

def 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 4

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 True

def 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

这应该适合你。它不 return 数组但修改它。所以如果你通过

solve(sudoku_grid)

然后打印 sudoku_grid 它会给你解决输出

Answer 5

考虑这段代码：

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 将撤消您找到的解决方案，并且进一步的迭代会继续尝试下一个可能的数字。由于数独只有一种解决方案，因此无需在找到解决方案后检查更多数字。您可以 return 一个真值来结束递归。

例如，您可以这样编码：

if solve_sudoku(sudoku):
    return True

或

if solve_sudoku(sudoku):
    return sudoku

这可以防止 sudoku[row, col] = 0 擦除解决方案并最终在递归调用堆栈展开后 return 将已解决的网格发送给初始调用者。

Python 递归数独求解器没有 Return 解决方案

Python Recursive Sudoku Solver Doesn't Return the Solution

python

numpy

sudoku