关于Python返回矩阵算法的问题

Question

我在练习我的Python小技能，编程一个数独-解算算法。

我实现了单元测试。现在我已经实现了求解器，它返回一个数独的求解矩阵，我在单元测试中检查了它。

但是解算器返回的结果var分配的结果是None。我做了一些断点，在解算结束时，返回值是正确的解算矩阵。谁能给我一个提示，在哪一点上我错过了什么？

非常感谢！我的数独算法类

我的数独算法类。

    class SudokuSolver():

    def testTester(self):
        print('TDDisworking')
        return 'TDDisworking'

    def IsInsertPossible(self, grid:list, x:int, y:int, n:int):

        for i in range(0,9):
            if grid[i][x] == n:
                return False
        for i in range(0,9):
            if grid[y][i] == n:
                return False

        sqX = (x//3)*3
        sqY = (y//3)*3
        for i in range(0,3):
            for j in range(0,3):
                if grid[sqY+i][sqX+j] == n:
                    return False
        return True

    def Solve(self, grid:list, yRange:int, xRange:int):
        localgrid = grid
        for y in range(yRange):
            for x in range(xRange):
                if localgrid[y][x] == 0:
                    for n in range(1,10):
                        if self.IsInsertPossible(localgrid, x, y, n):
                            localgrid[y][x] = n
                            self.Solve(localgrid, yRange, xRange)
                            localgrid[y][x] = 0
                    return
        print(localgrid)
        return localgrid

我的单元测试类

import unittest
from Main.SudokuSolver import SudokuSolver

class SudokuSolverTester(unittest.TestCase):

sudoku_solver = SudokuSolver()
grid = [[0, 0, 0, 0, 0, 3, 0, 1, 7],
        [0, 1, 5, 0, 0, 9, 0, 0, 8],
        [0, 6, 0, 0, 0, 0, 0, 0, 0],
        [1, 0, 0, 0, 0, 7, 0, 0, 0],
        [0, 0, 9, 0, 0, 0, 2, 0, 0],
        [0, 0, 0, 5, 0, 0, 0, 0, 4],
        [0, 0, 0, 0, 0, 0, 0, 2, 0],
        [5, 0, 0, 6, 0, 0, 3, 4, 0],
        [3, 4, 0, 2, 0, 0, 0, 0, 0]]

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

def test_row0_results(self):
    yRange = 9
    xRange = 9
    #This result var is every time : None
    result = self.sudoku_solver.Solve(self.grid, yRange, xRange)
    self.assertListEqual(result[0], self.solgrid[0])

if __name__ == '__main__':
  unittest.main()

Answer 1

我找到了答案。问题是该算法不知道什么时候有一些空闲的单元格可以填充。所以递归并没有停止在解的最后。如果我插入一个控件，检查是否有空闲的单元格，算法就会工作。

下面是我更新的解决方案。

class Cell Utilities:

class CellUtilities():

def findNextCellToFill(self, sudoku):
    for x in range(9):
        for y in range(9):
            if sudoku[x][y] == 0:
                return x, y
    return -1, -1

def IsInsertPossible(self, sudoku, i, j, n):
    rowOk = all([n != sudoku[i][x] for x in range(9)])
    if rowOk:
        columnOk = all([n != sudoku[x][j] for x in range(9)])
        if columnOk:
            secTopX, secTopY = 3 * (i // 3), 3 * (j // 3)
            for x in range(secTopX, secTopX + 3):
                for y in range(secTopY, secTopY + 3):
                    if sudoku[x][y] == n:
                        return False
            return True
    return False

class SudokuSolverI:

from Main.CellUtilities import CellUtilities
class SudokuSolverI():

cellUtil = CellUtilities()

def solveSudoku(self, sudoku, row_i=0, col_j=0):
    row_i, col_j = self.cellUtil.findNextCellToFill(sudoku)
    if row_i == -1:
        return True
    for num in range(1, 10):
        if self.cellUtil.IsInsertPossible(sudoku, row_i, col_j, num):
            sudoku[row_i][col_j] = num
            if self.solveSudoku(sudoku, row_i, col_j):
                return True
            sudoku[row_i][col_j] = 0
    return False

感谢所有帮助我找到解决方案的人！