我正在尝试使用递归来制作数独求解器，方法是将可能的值存储在字典中，以索引为键，将可能值的集合作为值。参数 b 只是表示为单个列表的板，并且 .get_row、.get_col、.get_box 方法正确返回各自的值。如果字典中的条目有一个包含单个元素的集合，则它将被放入板 b 中，否则，如果没有可能的包含单个元素的集合，则从可能的数字集中选取一个值并开始递归。这是完整的可重复代码：
class Sudoku:
def solve_it(self, board: List[List[str]]) -> None:
"""
:param board: sudoku board gets modified inplace at .create_board_from_list
:return: None
"""
unit_values = []
for i in range(len(board)): # flattening the board into unit_values
for j in range(len(board[i])):
unit_values.append(board[i][j])
self.go_through_recursive(board, unit_values)
def get_row(self, n: int, b): # retrieve all elements of nth row in the board
assert 0 <= n <= 8
return set(b[9 * n: 9 * (n + 1)])
def get_col(self, n: int, b): # retrieve all elements of nth col in the board
assert 0 <= n <= 8
return set(b[n::9])
def get_box(self, n: int, b): # retrieve all elements of nth box in the board
assert 0 <= n <= 8
return set(b[i] for i in range(81) if (i // 27) == (n // 3) and i % 9 // 3 == n % 3)
def go_through_recursive(self, board, b, d=False):
"""
:param board: sudoku board as matrix where each row is a line
:param b: sudoku board as a single long list
"""
numbers = {'1', '2', '3', '4', '5', '6', '7', '8', '9'}
while True:
if d:
return True
missing_dict = {} # populate missing_dict
for idx in range(len(b)):
if b[idx] == '.':
row, col, box = idx // 9, idx % 9, (idx // 27) * 3 + (idx % 9) // 3
# union of all the present values in current row, col and box
values = self.get_row(row, b).union(self.get_col(col, b)).union(self.get_box(box, b))
values.remove('.')
missing_ones = numbers.difference(values) # possible values to input in the slot
if len(missing_ones) == 0: # impossible to continue
return False
missing_dict[idx] = missing_ones
old_count = b.count('.')
# now we iterate through the dictionary of possible values per index,
# if one index has a set with a single number it means that that's the only possible number so we store it
for idx, missings in missing_dict.items(): # store assured values
if len(missings) == 1:
b[idx] = missings.pop()
if b.count('.') == 0: # check if complete
self.create_board_from_list(board, b)
return True
if b.count('.') == old_count: # if no progress has been made
for idx, s in missing_dict.items(): # iterate through the dictionary
for number in s: # create a new board and store indecisive value then recur
if d:
return True
bb = b[:]
bb[idx] = number
d = self.go_through_recursive(board, bb)
def create_board_from_list(self, board, b):
temp_board = []
chunk = 9
for idx in range(0, len(b), chunk):
temp_board.append(b[idx: idx + chunk])
for idx in range(len(board)):
board[idx] = temp_board[idx]
print('done')
我遇到的问题是，一旦完成，一些数字就会重复（在行、列或框中）。我还注意到，如果我检查“存储保证值”循环内的可能值，它有时会返回整个范围 [1, 9] 可能是某些重写的原因：
row, col, box = idx // 9, idx % 9, (idx // 27) * 3 + (idx % 9) // 3
values = self.get_row(row, b).union(self.get_col(col, b)).union(self.get_box(box, b))
values.remove('.') # some of these values are [1, 9]
鉴于此板的输入：
board =
[[".",".","9","7","4","8",".",".","."],
["7",".",".",".",".",".",".",".","."],
[".","2",".","1",".","9",".",".","."],
[".",".","7",".",".",".","2","4","."],
[".","6","4",".","1",".","5","9","."],
[".","9","8",".",".",".","3",".","."],
[".",".",".","8",".","3",".","2","."],
[".",".",".",".",".",".",".",".","6"],
[".",".",".","2","7","5","9",".","."]]
正确的输出是
board =
[["5","1","9","7","4","8","6","3","2"],
["7","8","3","6","5","2","4","1","9"],
["4","2","6","1","3","9","8","7","5"],
["3","5","7","9","8","6","2","4","1"],
["2","6","4","3","1","7","5","9","8"],
["1","9","8","5","2","4","3","6","7"],
["9","7","5","8","6","3","1","2","4"],
["8","3","2","4","9","1","7","5","6"],
["6","4","1","2","7","5","9","8","3"]]
虽然代码有错误的板
board =
[["3","1","9","7","4","8","6","5","2"],
["7","8","5","6","3","2","1","1","9"],
["4","2","6","1","5","9","8","7","3"],
["5","3","7","9","8","6","2","4","1"],
["2","6","4","3","1","7","5","9","8"],
["1","9","8","5","2","4","3","6","7"],
["9","7","1","8","6","3","4","2","5"],
["8","5","2","4","9","1","7","3","6"],
["6","4","3","2","7","5","9","8","4"]]
编辑：
我更改了
go_through_recursive def go_through_recursive(self, board, b, d=False):
"""
:param board: sudoku board as matrix where each row is a line
:param b: sudoku board as a single long list
"""
numbers = {'1', '2', '3', '4', '5', '6', '7', '8', '9'}
while True:
old_count = b.count('.')
missing_dict = {} # populate missing_dict
for idx in range(len(b)):
if b[idx] == '.':
row, col, box = idx // 9, idx % 9, (idx // 27) * 3 + (idx % 9) // 3
# union of all the present values in current row, col and box
values = self.get_row(row, b).union(self.get_col(col, b)).union(self.get_box(box, b))
values.remove('.')
missing_ones = numbers.difference(values) # possible values to input in the slot
if len(missing_ones) == 0: # impossible to continue
return False
elif len(missing_ones) == 1:
b[idx] = missing_ones.pop()
else:
missing_dict[idx] = missing_ones
if b.count('.') == 0: # check if complete
self.create_board_from_list(board, b)
return True
if b.count('.') == old_count: # if no progress has been made
for idx, s in missing_dict.items(): # iterate through the dictionary
for number in s: # create a new board and store indecisive value then recur
bb = b[:]
bb[idx] = number
if self.go_through_recursive(board, bb):
return True
这里有两个问题：
当你执行
b[idx] = missings.pop()missings在给出的示例中，棋盘最初没有强制条目（使用字典检查后空单元格的数量保持不变），因此对左上角单元格进行了随机选择。在示例输出中，结果表明选择是 3，但这使得这个特定的数独无法解决。但你的算法没有实现回溯。当它后来发现没有解决方案时，它就返回
False