Coverage for src / hodoku / core / grid.py: 100%

1"""Grid — the central mutable state of a sudoku puzzle. 

2 

3Mirrors Java's Sudoku2. Cells are indexed 0-80, row-major: 

4 row r, col c → index r*9 + c 

5 

6Candidate masks: bit (d-1) set means digit d is still a candidate. 

7""" 

8 

9from __future__ import annotations 

10 

11import collections 

12 

13# --------------------------------------------------------------------------- 

14# Static lookup tables — computed once at module load, never mutated 

15# --------------------------------------------------------------------------- 

16 

17LENGTH = 81 

18UNITS = 9 

19 

20# row/col/box membership 

21LINES: tuple[tuple[int, ...], ...] = tuple( 

22 tuple(range(r * 9, r * 9 + 9)) for r in range(9) 

23) 

24COLS: tuple[tuple[int, ...], ...] = tuple( 

25 tuple(r * 9 + c for r in range(9)) for c in range(9) 

26) 

27BLOCKS: tuple[tuple[int, ...], ...] = tuple( 

28 tuple( 

29 (br * 3 + dr) * 9 + (bc * 3 + dc) 

30 for dr in range(3) 

31 for dc in range(3) 

32 ) 

33 for br in range(3) 

34 for bc in range(3) 

35) 

36ALL_UNITS: tuple[tuple[int, ...], ...] = LINES + COLS + BLOCKS 

37 

38 

39# For each cell: (row_index, col_index, box_index) — all 0-based within their type 

40def _build_constraints() -> tuple[tuple[int, int, int], ...]: 

41 result = [] 

42 for i in range(81): 

43 r = i // 9 

44 c = i % 9 

45 b = (r // 3) * 3 + (c // 3) 

46 result.append((r, c, b)) 

47 return tuple(result) 

48 

49 

50CONSTRAINTS: tuple[tuple[int, int, int], ...] = _build_constraints() 

51 

52# For each cell: indices into ALL_UNITS — (row_idx, col_idx+9, box_idx+18) 

53CELL_CONSTRAINTS: tuple[tuple[int, int, int], ...] = tuple( 

54 (r, c + 9, b + 18) for r, c, b in CONSTRAINTS 

55) 

56 

57 

58# Buddy sets: for each cell, the int bitmask of its 20 peers 

59def _build_buddies() -> tuple[int, ...]: 

60 buddies = [] 

61 for i in range(81): 

62 r, c, b = CONSTRAINTS[i] 

63 mask = 0 

64 for j in LINES[r]: 

65 if j != i: 

66 mask |= 1 << j 

67 for j in COLS[c]: 

68 if j != i: 

69 mask |= 1 << j 

70 for j in BLOCKS[b]: 

71 if j != i: 

72 mask |= 1 << j 

73 buddies.append(mask) 

74 return tuple(buddies) 

75 

76 

77BUDDIES: tuple[int, ...] = _build_buddies() 

78 

79# House bitmasks (for CellSet-style operations without CellSet objects) 

80LINE_MASKS: tuple[int, ...] = tuple( 

81 sum(1 << j for j in LINES[r]) for r in range(9) 

82) 

83COL_MASKS: tuple[int, ...] = tuple( 

84 sum(1 << j for j in COLS[c]) for c in range(9) 

85) 

86BLOCK_MASKS: tuple[int, ...] = tuple( 

87 sum(1 << j for j in BLOCKS[b]) for b in range(9) 

88) 

89ALL_UNIT_MASKS: tuple[int, ...] = LINE_MASKS + COL_MASKS + BLOCK_MASKS 

90 

91# Digit masks for candidate shorts 

92DIGIT_MASKS: tuple[int, ...] = (0,) + tuple(1 << (d - 1) for d in range(1, 10)) 

93ALL_DIGITS_MASK: int = 0x1FF # bits 0-8 set 

94 

95 

96# --------------------------------------------------------------------------- 

97# Grid 

98# --------------------------------------------------------------------------- 

99 

100class Grid: 

101 """Mutable sudoku grid.""" 

102 

103 __slots__ = ( 

104 "values", 

105 "candidates", 

106 "candidate_sets", 

107 "solution", 

108 "free", 

109 "ns_queue", 

110 "hs_queue", 

111 "givens", 

112 ) 

113 

114 def __init__(self) -> None: 

115 # 0 = empty, 1-9 = placed digit 

116 self.values: list[int] = [0] * 81 

117 # per-cell candidate mask (9-bit int, bit d-1 = digit d present) 

118 self.candidates: list[int] = [ALL_DIGITS_MASK] * 81 

119 # per-digit bitmask of cells where that digit is still a candidate 

120 # index 0 unused; indices 1-9 are valid 

121 self.candidate_sets: list[int] = [0] * 10 

122 for d in range(1, 10): 

123 self.candidate_sets[d] = (1 << 81) - 1 # all cells initially 

124 # solution array — filled by generator after uniqueness check 

125 self.solution: list[int] = [0] * 81 

126 # free[constraint_index][digit] = count of unsolved cells in that 

127 # constraint still holding digit as a candidate. 

128 # 27 constraints (rows 0-8, cols 9-17, boxes 18-26), digits 0-9 (0 unused) 

129 self.free: list[list[int]] = [[0] * 10 for _ in range(27)] 

130 for c in range(27): 

131 for d in range(1, 10): 

132 self.free[c][d] = 9 # all 9 cells start with all candidates 

133 # Naked-single queue: (cell_index, digit) — cell has exactly 1 candidate left 

134 self.ns_queue: collections.deque[tuple[int, int]] = collections.deque() 

135 # Hidden-single queue: (constraint_index, digit) — constraint has exactly 1 

136 # cell left for digit 

137 self.hs_queue: collections.deque[tuple[int, int]] = collections.deque() 

138 # Bitmask of cells that are original givens (not placed during solving) 

139 self.givens: int = 0 

140 

141 # ------------------------------------------------------------------ 

142 # Parsing 

143 # ------------------------------------------------------------------ 

144 

145 def set_sudoku(self, puzzle: str) -> None: 

146 """Load a puzzle string ('.' or '0' for empty). 

147 

148 Digits prefixed with '+' are placed (solved) cells; digits without 

149 '+' are givens. Both are set on the grid, but only non-'+' cells 

150 are recorded in the ``givens`` bitmask. 

151 """ 

152 # Parse into (is_placed, char) pairs 

153 cells: list[tuple[bool, str]] = [] 

154 i = 0 

155 while i < len(puzzle): 

156 ch = puzzle[i] 

157 if ch == '+': 

158 i += 1 

159 if i < len(puzzle) and (puzzle[i].isdigit() or puzzle[i] == '.'): 

160 cells.append((True, puzzle[i])) 

161 elif ch.isdigit() or ch == '.': 

162 cells.append((False, ch)) 

163 i += 1 

164 if len(cells) != 81: 

165 raise ValueError(f"Expected 81 cells, got {len(cells)}: {puzzle!r}") 

166 self.__init__() 

167 for idx, (is_placed, ch) in enumerate(cells): 

168 if ch not in ('.', '0'): 

169 self.set_cell(idx, int(ch)) 

170 if not is_placed: 

171 self.givens |= 1 << idx 

172 

173 def is_fixed(self, index: int) -> bool: 

174 """True if the cell is an original given (not placed during solving).""" 

175 return bool(self.givens & (1 << index)) 

176 

177 def get_sudoku_string(self) -> str: 

178 return "".join(str(v) if v else "0" for v in self.values) 

179 

180 # ------------------------------------------------------------------ 

181 # Cell mutation — keep values, candidates, candidate_sets, free in sync 

182 # ------------------------------------------------------------------ 

183 

184 def _del_cand(self, index: int, digit: int) -> None: 

185 """Remove one candidate from a cell, update free[] and queues.""" 

186 mask = DIGIT_MASKS[digit] 

187 if not (self.candidates[index] & mask): 

188 return 

189 self.candidates[index] &= ~mask 

190 self.candidate_sets[digit] &= ~(1 << index) 

191 for c in CELL_CONSTRAINTS[index]: 

192 self.free[c][digit] -= 1 

193 if self.free[c][digit] == 1: 

194 # Find the one remaining cell in this unit that still has digit. 

195 # candidate_sets[digit] is already updated, so bitwise-AND with 

196 # the unit mask gives exactly that cell. 

197 rem = self.candidate_sets[digit] & ALL_UNIT_MASKS[c] 

198 if rem: 

199 cell = (rem & -rem).bit_length() - 1 

200 self.hs_queue.append((cell, digit)) 

201 remaining = self.candidates[index] 

202 if remaining != 0 and (remaining & (remaining - 1)) == 0: 

203 self.ns_queue.append((index, remaining.bit_length())) 

204 

205 def set_cell(self, index: int, value: int) -> None: 

206 """Place a digit in a cell and propagate eliminations to buddies. 

207 

208 Mirrors Sudoku2.setCell: 

209 1. Remove value from all buddy candidates (triggers HS/NS queue updates). 

210 2. Remove all remaining candidates from own cell, update free[]. 

211 """ 

212 if self.values[index] == value: 

213 return 

214 self.values[index] = value 

215 

216 # Step 1: eliminate value from every buddy 

217 buddies = BUDDIES[index] 

218 while buddies: 

219 lsb = buddies & -buddies 

220 j = lsb.bit_length() - 1 

221 buddies ^= lsb 

222 self._del_cand(j, value) 

223 

224 # Step 2: clear all remaining candidates from this cell, update free[] 

225 old_mask = self.candidates[index] 

226 self.candidates[index] = 0 

227 for d in range(1, 10): 

228 if old_mask & DIGIT_MASKS[d]: 

229 self.candidate_sets[d] &= ~(1 << index) 

230 for c in CELL_CONSTRAINTS[index]: 

231 self.free[c][d] -= 1 

232 if self.free[c][d] == 1 and d != value: 

233 rem = self.candidate_sets[d] & ALL_UNIT_MASKS[c] 

234 if rem: 

235 cell = (rem & -rem).bit_length() - 1 

236 self.hs_queue.append((cell, d)) 

237 

238 def del_candidate(self, index: int, digit: int) -> None: 

239 """Public API: remove a candidate digit from a cell.""" 

240 self._del_cand(index, digit) 

241 

242 # ------------------------------------------------------------------ 

243 # Queries 

244 # ------------------------------------------------------------------ 

245 

246 def get_value(self, index: int) -> int: 

247 return self.values[index] 

248 

249 def get_candidates(self, index: int) -> list[int]: 

250 """Return list of candidate digits for a cell.""" 

251 mask = self.candidates[index] 

252 result = [] 

253 for d in range(1, 10): 

254 if mask & DIGIT_MASKS[d]: 

255 result.append(d) 

256 return result 

257 

258 def is_solved(self) -> bool: 

259 return all(v != 0 for v in self.values) 

260 

261 def unsolved_count(self) -> int: 

262 return self.values.count(0) 

263 

264 def unsolved_candidates_count(self) -> int: 

265 return sum(c.bit_count() for c in self.candidates) 

266 

267 def get_solution(self, index: int) -> int: 

268 return self.solution[index] 

269 

270 def set_solution(self, solution: list[int]) -> None: 

271 self.solution = list(solution) 

272 

273 def is_solution_set(self) -> bool: 

274 return any(v != 0 for v in self.solution) 

275 

276 # ------------------------------------------------------------------ 

277 # Cloning 

278 # ------------------------------------------------------------------ 

279 

280 def clone(self) -> Grid: 

281 g = Grid.__new__(Grid) 

282 g.values = list(self.values) 

283 g.candidates = list(self.candidates) 

284 g.candidate_sets = list(self.candidate_sets) 

285 g.solution = list(self.solution) 

286 g.free = [list(row) for row in self.free] 

287 g.ns_queue = collections.deque(self.ns_queue) 

288 g.hs_queue = collections.deque(self.hs_queue) 

289 return g 

290 

291 def set(self, other: Grid) -> None: 

292 """Copy another grid's state into self.""" 

293 self.values = list(other.values) 

294 self.candidates = list(other.candidates) 

295 self.candidate_sets = list(other.candidate_sets) 

296 self.solution = list(other.solution) 

297 self.free = [list(row) for row in other.free] 

298 self.ns_queue = collections.deque(other.ns_queue) 

299 self.hs_queue = collections.deque(other.hs_queue) 

300 

301 def __repr__(self) -> str: 

302 return f"Grid({self.get_sudoku_string()})"