Coverage for src / hodoku / solver / solver.py: 100%

1"""SudokuSolver — main solve loop with scoring and difficulty rating. 

2 

3Mirrors Java's SudokuSolver.solve(). Iterates SOLVER_STEPS in priority order, 

4tries each enabled technique in turn, applies the first step found, and repeats 

5until the puzzle is solved or no progress can be made. 

6""" 

7 

8from __future__ import annotations 

9 

10from dataclasses import dataclass, field 

11from typing import TYPE_CHECKING 

12 

13from hodoku.core.grid import Grid 

14from hodoku.core.solution_step import SolutionStep 

15from hodoku.core.types import DifficultyType, SolutionType 

16from hodoku.solver.step_finder import SudokuStepFinder 

17 

18if TYPE_CHECKING: 

19 from hodoku.config import SolverConfig 

20 

21 

22@dataclass 

23class SolveResult: 

24 """Result of a solve() call.""" 

25 puzzle: str 

26 steps: list[SolutionStep] = field(default_factory=list) 

27 level: DifficultyType = DifficultyType.INCOMPLETE 

28 score: int = 0 

29 solved: bool = False 

30 solution: str = "" # 81-char grid after all steps applied 

31 

32 

33_PLACEMENT_TYPES: frozenset[SolutionType] = frozenset({ 

34 SolutionType.FULL_HOUSE, 

35 SolutionType.NAKED_SINGLE, 

36 SolutionType.HIDDEN_SINGLE, 

37 SolutionType.BRUTE_FORCE, 

38 # Forcing chains/nets can set values via contradiction/verity 

39 SolutionType.FORCING_CHAIN_CONTRADICTION, 

40 SolutionType.FORCING_CHAIN_VERITY, 

41 SolutionType.FORCING_NET_CONTRADICTION, 

42 SolutionType.FORCING_NET_VERITY, 

43}) 

44 

45 

46def _apply_step(grid: Grid, step: SolutionStep) -> None: 

47 """Apply a solution step to the grid. 

48 

49 For placement steps (singles), set_cell is called for each (index, value). 

50 For elimination steps (LC, subsets, …), only candidates_to_delete is applied. 

51 In both cases, step.indices on non-placement steps is pattern context only. 

52 """ 

53 if step.type in _PLACEMENT_TYPES: 

54 for idx, val in zip(step.indices, step.values): 

55 grid.set_cell(idx, val) 

56 for cand in step.candidates_to_delete: 

57 grid.del_candidate(cand.index, cand.value) 

58 

59 

60class SudokuSolver: 

61 """Iterative solver that mirrors the HoDoKu solve loop.""" 

62 

63 def __init__(self, config: SolverConfig | None = None) -> None: 

64 if config is None: 

65 from hodoku.config import DEFAULT_CONFIG 

66 config = DEFAULT_CONFIG 

67 self._config = config 

68 

69 def solve(self, puzzle: str) -> SolveResult: 

70 """Solve *puzzle* and return a SolveResult with steps, level, and score.""" 

71 grid = Grid() 

72 grid.set_sudoku(puzzle) 

73 

74 result = SolveResult(puzzle=grid.get_sudoku_string()) 

75 finder = SudokuStepFinder(grid, self._config.solve_search) 

76 

77 step_config = self._config.step_config 

78 difficulty_max = self._config._difficulty_max_score 

79 solver_steps = self._config.solver_steps 

80 

81 max_level = DifficultyType.INCOMPLETE 

82 total_score = 0 

83 

84 while not grid.is_solved(): 

85 step = self._find_next_step(finder, solver_steps) 

86 if step is None: 

87 # No technique could make progress 

88 break 

89 _apply_step(grid, step) 

90 result.steps.append(step) 

91 

92 cfg = step_config.get(step.type) 

93 if cfg is not None: 

94 total_score += cfg.base_score 

95 if cfg.level.value > max_level.value: 

96 max_level = cfg.level 

97 

98 result.solved = grid.is_solved() 

99 result.score = total_score 

100 if result.solved: 

101 # Mirror Java's post-solve score-threshold bump: 

102 # while (score > level.getMaxScore()) level = nextLevel 

103 level = max_level 

104 while difficulty_max.get(level, 2**31 - 1) < total_score: 

105 level = DifficultyType(level.value + 1) 

106 result.level = level 

107 else: 

108 result.level = DifficultyType.INCOMPLETE 

109 result.solution = grid.get_sudoku_string() 

110 return result 

111 

112 @staticmethod 

113 def _find_next_step(finder: SudokuStepFinder, solver_steps) -> SolutionStep | None: 

114 """Try each enabled technique in priority order; return first hit.""" 

115 for cfg in solver_steps: 

116 step = finder.get_step(cfg.solution_type) 

117 if step is not None: 

118 return step 

119 return None