我找到了答案。问题是，算法不知道何时有一些空闲单元格需要填充。因此递归不会在解决方案结束时停止。如果我插入一个控件来检查是否有空闲单元格，算法就会工作。
我正在通过编程数独求解算法来练习我的Python小技能。
我实现了对的单元测试。现在我已经实现了求解器，它返回一个已求解的数独矩阵，我在单元测试中检查它。
但是由解算器结果None的返回指定的结果var。我做了一些断点，在求解器的末尾，返回值是正确的求解矩阵。有人能告诉我在哪一点上我遗漏了什么吗？
非常感谢！
我的数独算法类：
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()
这里是我更新的解决方案：
class Cell实用程序：
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
类数独求解器I:
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
感谢所有帮助我找到解决方案的人！