Coverage for src / hodoku / solver / brute_force.py: 95%

1"""BruteForceSolver — last-resort backtracking solver. 

2 

3When all logical techniques are exhausted, this solver guesses a digit for 

4the most-constrained empty cell and places it. The solve loop keeps calling 

5it (one placement per call) until the puzzle is solved. 

6 

7The solution is computed once via backtracking on a plain int array, cached 

8on the grid object as `grid.solution` (which the generator already populates 

9for puzzles with known solutions). If `grid.solution` is not set, we run 

10backtracking here to fill it. 

11""" 

12 

13from __future__ import annotations 

14 

15from hodoku.core.grid import CONSTRAINTS 

16from hodoku.core.solution_step import SolutionStep 

17from hodoku.core.types import SolutionType 

18 

19 

20# --------------------------------------------------------------------------- 

21# Pure backtracking on a flat int[81] array — no Grid overhead. 

22# Returns True and fills `values` in-place on success. 

23# --------------------------------------------------------------------------- 

24 

25# Precomputed peer-index sets for fast candidate checking 

26def _build_peers() -> tuple[frozenset[int], ...]: 

27 peers: list[frozenset[int]] = [] 

28 for i in range(81): 

29 r, c, b = CONSTRAINTS[i] 

30 br, bc = (r // 3) * 3, (c // 3) * 3 

31 p: set[int] = set() 

32 for j in range(9): 

33 p.add(r * 9 + j) # same row 

34 p.add(j * 9 + c) # same col 

35 p.add((br + j // 3) * 9 + bc + j % 3) # same box 

36 p.discard(i) 

37 peers.append(frozenset(p)) 

38 return tuple(peers) 

39 

40 

41_PEERS: tuple[frozenset[int], ...] = _build_peers() 

42 

43 

44def _allowed(values: list[int], index: int, digit: int) -> bool: 

45 """Return True if digit can legally be placed at index.""" 

46 for p in _PEERS[index]: 

47 if values[p] == digit: 

48 return False 

49 return True 

50 

51 

52def _solve_bt(values: list[int]) -> bool: 

53 """Backtracking solve in-place. Returns True if a solution was found.""" 

54 # Find the first empty cell (simple MRV: just first empty) 

55 for i in range(81): 

56 if values[i] == 0: 

57 for d in range(1, 10): 

58 if _allowed(values, i, d): 

59 values[i] = d 

60 if _solve_bt(values): 

61 return True 

62 values[i] = 0 

63 return False 

64 return True # no empty cell → solved 

65 

66 

67# --------------------------------------------------------------------------- 

68# Solver class 

69# --------------------------------------------------------------------------- 

70 

71class BruteForceSolver: 

72 """Places one digit per call using the precomputed solution.""" 

73 

74 def __init__(self, grid) -> None: 

75 self.grid = grid 

76 self._solution: list[int] | None = None 

77 

78 def _ensure_solution(self) -> bool: 

79 """Compute (or reuse) the solution. Returns False if unsolvable.""" 

80 if self._solution is not None: 

81 return True 

82 # Prefer grid.solution if already filled by the generator 

83 if any(self.grid.solution): 

84 self._solution = list(self.grid.solution) 

85 return True 

86 # Fall back to backtracking from current grid state 

87 trial = list(self.grid.values) 

88 if _solve_bt(trial): 

89 self._solution = trial 

90 return True 

91 return False 

92 

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

94 if sol_type is not SolutionType.BRUTE_FORCE: 

95 return None 

96 if not self._ensure_solution(): 

97 return None 

98 

99 # Collect all unsolved cells, then pick the middle one (matches Java) 

100 unsolved = [i for i in range(81) if self.grid.values[i] == 0] 

101 if not unsolved: 

102 return None # grid is already solved 

103 

104 index = unsolved[len(unsolved) // 2] 

105 digit = self._solution[index] 

106 step = SolutionStep(type=SolutionType.BRUTE_FORCE) 

107 step.indices.append(index) 

108 step.values.append(digit) 

109 return step