作者：石头1988030450 | 来源：互联网 | 2024-12-10 13:37
尽管大多数解决方案倾向于使用递归来解决数独问题，但递归方法并非总是最优选择。本文探讨了一种基于迭代的方法来求解数独，这种方法不仅避免了递归的局限性，还通过使用集合来高效管理空位及其可能的数字选项。此方法未采用剪枝或最小候选数优先策略，而是通过迭代遍历所有可能性来寻找解。
在解决数独问题时，多数人倾向于使用递归算法，然而递归方法存在固有的局限性，比如栈溢出风险。因此，本文介绍一种基于迭代的方法来解决这个问题。与LeetCode第36题类似，我们利用集合来简化空位的处理过程。虽然本方法没有实现剪枝技术或选择最少候选数的位置作为下一步，但它通过迭代的方式，为每个空位存储了三个关键信息：坐标、当前位置的候选数字集（在处理当前位时动态更新）以及当前尝试的候选数字索引。
如果某个位置有可用的候选数字，我们将使用列表中的第一个数字，并继续检查下一个位置。如果没有可用的候选数字，算法将回溯至上一位置，如果有更多的候选方案，将继续尝试下一个候选数字；如果没有其他候选方案，则继续回溯，直到找到解决方案。使用指针来控制前进和回溯的过程。
1 class Solution:
2 def solveSudoku(self, board: List[List[str]]) -> None:
3 """
4 Do not return anything, modify board in-place instead.
5 """
6 row_sets, col_sets, box_sets = [], [], []
7 possible_values = {'1', '2', '3', '4', '5', '6', '7', '8', '9'}
8 empty_positiOns= []
9 for i in range(9):
10 row_set, col_set = set(), set()
11 for j in range(9):
12 if board[i][j] == '.':
13 empty_positions.append((i, j))
14 else:
15 row_set.add(board[i][j])
16 col_set.add(board[j][i])
17 row_sets.append(possible_values - row_set)
18 col_sets.append(possible_values - col_set)
19 for i in range(3):
20 for j in range(3):
21 box_set = set()
22 for x in range(3*i, 3*(i+1)):
23 for y in range(3*j, 3*(j+1)):
24 if board[x][y] != '.':
25 box_set.add(board[x][y])
26 box_sets.append(possible_values - box_set)
27 index, attempts = 0, [0] * len(empty_positions)
28 while index 29 pos = empty_positions[index]
30 box_index = (pos[0] // 3) * 3 + (pos[1] // 3)
31 candidates = list(row_sets[pos[0]] & col_sets[pos[1]] & box_sets[box_index])
32 if candidates:
33 num = candidates[0]
34 attempts[index] = [pos, candidates, 0]
35 row_sets[pos[0]].remove(num)
36 col_sets[pos[1]].remove(num)
37 box_sets[box_index].remove(num)
38 index += 1
39 else:
40 while True:
41 index -= 1
42 last_attempt = attempts[index]
43 num = last_attempt[1][last_attempt[2]]
44 row_sets[last_attempt[0][0]].add(num)
45 col_sets[last_attempt[0][1]].add(num)
46 box_sets[(last_attempt[0][0] // 3) * 3 + (last_attempt[0][1] // 3)].add(num)
47 if last_attempt[2] + 1 48 last_attempt[2] += 1
49 attempts[index] = last_attempt
50 num = last_attempt[1][last_attempt[2]]
51 row_sets[last_attempt[0][0]].remove(num)
52 col_sets[last_attempt[0][1]].remove(num)
53 box_sets[(last_attempt[0][0] // 3) * 3 + (last_attempt[0][1] // 3)].remove(num)
54 index += 1
55 break
56 else:
57 continue
58 for attempt in attempts:
59 board[attempt[0][0]][attempt[0][1]] = attempt[1][attempt[2]]
60 return board
京公网安备 11010802041100号