Coverage for src / hodoku / solver / step_finder.py: 99%

1"""SudokuStepFinder — central dispatcher for all technique solvers. 

2 

3Mirrors Java's SudokuStepFinder. Currently only SimpleSolver is wired in; 

4additional solvers will be added as they are implemented. 

5""" 

6 

7from __future__ import annotations 

8 

9from typing import TYPE_CHECKING 

10 

11from hodoku.core.grid import Grid 

12from hodoku.core.solution_step import SolutionStep 

13from hodoku.core.types import SolutionType 

14from hodoku.solver.als import AlsSolver 

15from hodoku.solver.brute_force import BruteForceSolver 

16from hodoku.solver.chains import ChainSolver 

17from hodoku.solver.coloring import ColoringSolver 

18from hodoku.solver.fish import FishSolver 

19from hodoku.solver.misc import MiscSolver 

20from hodoku.solver.simple import SimpleSolver 

21from hodoku.solver.single_digit import SingleDigitSolver 

22from hodoku.solver.tabling import TablingSolver 

23from hodoku.solver.templates import TemplateSolver 

24from hodoku.solver.uniqueness import UniquenessSolver 

25from hodoku.solver.wings import WingSolver 

26 

27if TYPE_CHECKING: 

28 from hodoku.config import StepSearchConfig 

29 

30 

31_SIMPLE_TYPES = frozenset({ 

32 SolutionType.FULL_HOUSE, 

33 SolutionType.NAKED_SINGLE, 

34 SolutionType.HIDDEN_SINGLE, 

35 SolutionType.LOCKED_CANDIDATES_1, 

36 SolutionType.LOCKED_CANDIDATES_2, 

37 SolutionType.LOCKED_PAIR, 

38 SolutionType.NAKED_PAIR, 

39 SolutionType.LOCKED_TRIPLE, 

40 SolutionType.NAKED_TRIPLE, 

41 SolutionType.NAKED_QUADRUPLE, 

42 SolutionType.HIDDEN_PAIR, 

43 SolutionType.HIDDEN_TRIPLE, 

44 SolutionType.HIDDEN_QUADRUPLE, 

45}) 

46 

47_SINGLE_DIGIT_TYPES = frozenset({ 

48 SolutionType.SKYSCRAPER, 

49 SolutionType.TWO_STRING_KITE, 

50 SolutionType.DUAL_TWO_STRING_KITE, 

51 SolutionType.EMPTY_RECTANGLE, 

52 SolutionType.DUAL_EMPTY_RECTANGLE, 

53}) 

54 

55_WING_TYPES = frozenset({ 

56 SolutionType.W_WING, 

57 SolutionType.XY_WING, 

58 SolutionType.XYZ_WING, 

59}) 

60 

61_COLORING_TYPES = frozenset({ 

62 SolutionType.SIMPLE_COLORS_TRAP, 

63 SolutionType.SIMPLE_COLORS_WRAP, 

64 SolutionType.MULTI_COLORS_1, 

65 SolutionType.MULTI_COLORS_2, 

66}) 

67 

68_FISH_TYPES = frozenset({ 

69 SolutionType.X_WING, 

70 SolutionType.SWORDFISH, 

71 SolutionType.JELLYFISH, 

72 SolutionType.FINNED_X_WING, 

73 SolutionType.FINNED_SWORDFISH, 

74 SolutionType.FINNED_JELLYFISH, 

75 SolutionType.SASHIMI_X_WING, 

76 SolutionType.SASHIMI_SWORDFISH, 

77 SolutionType.SASHIMI_JELLYFISH, 

78 # Franken fish 

79 SolutionType.FRANKEN_X_WING, 

80 SolutionType.FRANKEN_SWORDFISH, 

81 SolutionType.FRANKEN_JELLYFISH, 

82 SolutionType.FINNED_FRANKEN_X_WING, 

83 SolutionType.FINNED_FRANKEN_SWORDFISH, 

84 SolutionType.FINNED_FRANKEN_JELLYFISH, 

85 # Mutant fish 

86 SolutionType.MUTANT_X_WING, 

87 SolutionType.MUTANT_SWORDFISH, 

88 SolutionType.MUTANT_JELLYFISH, 

89 SolutionType.FINNED_MUTANT_X_WING, 

90 SolutionType.FINNED_MUTANT_SWORDFISH, 

91 SolutionType.FINNED_MUTANT_JELLYFISH, 

92 SolutionType.FINNED_MUTANT_SQUIRMBAG, 

93 SolutionType.FINNED_MUTANT_WHALE, 

94 SolutionType.FINNED_MUTANT_LEVIATHAN, 

95}) 

96 

97_ALS_TYPES = frozenset({ 

98 SolutionType.ALS_XZ, 

99 SolutionType.ALS_XY_WING, 

100 SolutionType.ALS_XY_CHAIN, 

101 SolutionType.DEATH_BLOSSOM, 

102}) 

103 

104_CHAIN_TYPES = frozenset({ 

105 SolutionType.TURBOT_FISH, 

106 SolutionType.X_CHAIN, 

107 SolutionType.XY_CHAIN, 

108 SolutionType.REMOTE_PAIR, 

109}) 

110 

111# Nice Loops, AICs, and Forcing Chains/Nets — all handled by TablingSolver 

112# (mirrors Java where TablingSolver.getStep() handles these types) 

113_TABLING_TYPES = frozenset({ 

114 SolutionType.CONTINUOUS_NICE_LOOP, 

115 SolutionType.DISCONTINUOUS_NICE_LOOP, 

116 SolutionType.AIC, 

117 SolutionType.GROUPED_CONTINUOUS_NICE_LOOP, 

118 SolutionType.GROUPED_DISCONTINUOUS_NICE_LOOP, 

119 SolutionType.GROUPED_AIC, 

120 SolutionType.FORCING_CHAIN_CONTRADICTION, 

121 SolutionType.FORCING_CHAIN_VERITY, 

122 SolutionType.FORCING_NET_CONTRADICTION, 

123 SolutionType.FORCING_NET_VERITY, 

124}) 

125 

126_MISC_TYPES = frozenset({ 

127 SolutionType.SUE_DE_COQ, 

128}) 

129 

130_TEMPLATE_TYPES = frozenset({ 

131 SolutionType.TEMPLATE_SET, 

132 SolutionType.TEMPLATE_DEL, 

133}) 

134 

135_UNIQUENESS_TYPES = frozenset({ 

136 SolutionType.UNIQUENESS_1, 

137 SolutionType.UNIQUENESS_2, 

138 SolutionType.UNIQUENESS_3, 

139 SolutionType.UNIQUENESS_4, 

140 SolutionType.UNIQUENESS_5, 

141 SolutionType.UNIQUENESS_6, 

142 SolutionType.HIDDEN_RECTANGLE, 

143 SolutionType.AVOIDABLE_RECTANGLE_1, 

144 SolutionType.AVOIDABLE_RECTANGLE_2, 

145 SolutionType.BUG_PLUS_1, 

146}) 

147 

148 

149class SudokuStepFinder: 

150 """Dispatches get_step() calls to the appropriate specialized solver.""" 

151 

152 def __init__(self, grid: Grid, search_config: StepSearchConfig | None = None) -> None: 

153 self.grid = grid 

154 self._simple = SimpleSolver(grid) 

155 self._single_digit = SingleDigitSolver(grid, search_config) 

156 self._wings = WingSolver(grid) 

157 self._coloring = ColoringSolver(grid) 

158 self._fish = FishSolver(grid, search_config) 

159 self._uniqueness = UniquenessSolver(grid) 

160 self._chains = ChainSolver(grid, search_config) 

161 self._tabling = TablingSolver(grid, search_config) 

162 self._als = AlsSolver(grid, search_config) 

163 self._misc = MiscSolver(grid) 

164 self._templates = TemplateSolver(grid) 

165 self._brute_force = BruteForceSolver(grid) 

166 

167 def find_all(self, sol_type: SolutionType, *, for_candidate: int = -1) -> list[SolutionStep]: 

168 """Return ALL steps of the given type (for /bsa mode and reglib harness). 

169 

170 for_candidate: when 1-9, restricts fish search to that digit only. 

171 """ 

172 if sol_type in _SIMPLE_TYPES: 

173 return self._simple.find_all(sol_type) 

174 if sol_type in _SINGLE_DIGIT_TYPES: 

175 return self._single_digit.find_all(sol_type) 

176 if sol_type in _WING_TYPES: 

177 return self._wings.find_all(sol_type) 

178 if sol_type in _COLORING_TYPES: 

179 return self._coloring.find_all(sol_type) 

180 if sol_type in _FISH_TYPES: 

181 return self._fish.find_all(sol_type, for_candidate=for_candidate) 

182 if sol_type in _UNIQUENESS_TYPES: 

183 return self._uniqueness.find_all(sol_type) 

184 if sol_type in _ALS_TYPES: 

185 return self._als.find_all(sol_type) 

186 if sol_type in _CHAIN_TYPES: 

187 return self._chains.find_all(sol_type) 

188 if sol_type in _TABLING_TYPES: 

189 return self._tabling.find_all(sol_type) 

190 if sol_type in _MISC_TYPES: 

191 return self._misc.find_all(sol_type) 

192 if sol_type in _TEMPLATE_TYPES: 

193 return self._templates.find_all(sol_type) 

194 step = self.get_step(sol_type) 

195 return [step] if step is not None else [] 

196 

197 def get_step(self, sol_type: SolutionType) -> SolutionStep | None: 

198 """Return the next step of the given type, or None if not found.""" 

199 if sol_type in _SIMPLE_TYPES: 

200 return self._simple.get_step(sol_type) 

201 if sol_type in _SINGLE_DIGIT_TYPES: 

202 return self._single_digit.get_step(sol_type) 

203 if sol_type in _WING_TYPES: 

204 return self._wings.get_step(sol_type) 

205 if sol_type in _COLORING_TYPES: 

206 return self._coloring.get_step(sol_type) 

207 if sol_type in _FISH_TYPES: 

208 return self._fish.get_step(sol_type) 

209 if sol_type in _UNIQUENESS_TYPES: 

210 return self._uniqueness.get_step(sol_type) 

211 if sol_type in _ALS_TYPES: 

212 return self._als.get_step(sol_type) 

213 if sol_type in _CHAIN_TYPES: 

214 return self._chains.get_step(sol_type) 

215 if sol_type in _TABLING_TYPES: 

216 return self._tabling.get_step(sol_type) 

217 if sol_type in _MISC_TYPES: 

218 return self._misc.get_step(sol_type) 

219 if sol_type in _TEMPLATE_TYPES: 

220 return self._templates.get_step(sol_type) 

221 if sol_type is SolutionType.BRUTE_FORCE: 

222 return self._brute_force.get_step(sol_type) 

223 return None