Coverage for src / hodoku / solver / simple.py: 99%
429 statements
« prev ^ index » next coverage.py v7.13.5, created at 2026-04-21 08:35 +0000
1"""Simple solver — Full House, Naked/Hidden Singles, Locked Candidates,
2Naked/Hidden Subsets (Pair, Triple, Quad), Locked Pair/Triple.
4Mirrors Java's SimpleSolver for all techniques in that class.
5Iteration order matches HoDoKu exactly.
6"""
8from __future__ import annotations
10from hodoku.core.grid import (
11 ALL_UNITS, BLOCKS, CELL_CONSTRAINTS, COLS, DIGIT_MASKS, LINES, Grid,
12)
13from hodoku.core.solution_step import SolutionStep
14from hodoku.core.types import SolutionType
17class SimpleSolver:
18 """Finds all techniques handled by HoDoKu's SimpleSolver."""
20 def __init__(self, grid: Grid) -> None:
21 self.grid = grid
23 def get_step(self, sol_type: SolutionType) -> SolutionStep | None:
24 if sol_type == SolutionType.FULL_HOUSE:
25 return self.find_full_house()
26 if sol_type == SolutionType.NAKED_SINGLE:
27 return self.find_naked_single()
28 if sol_type == SolutionType.HIDDEN_SINGLE:
29 return self.find_hidden_single()
30 if sol_type in (SolutionType.LOCKED_CANDIDATES_1, SolutionType.LOCKED_CANDIDATES_2):
31 return self._find_locked_candidates(sol_type)
32 if sol_type == SolutionType.LOCKED_PAIR:
33 return self._find_naked_xle(2, locked_only=True)
34 if sol_type == SolutionType.NAKED_PAIR:
35 return self._find_naked_xle(2, locked_only=False)
36 if sol_type == SolutionType.LOCKED_TRIPLE:
37 return self._find_naked_xle(3, locked_only=True)
38 if sol_type == SolutionType.NAKED_TRIPLE:
39 return self._find_naked_xle(3, locked_only=False)
40 if sol_type == SolutionType.NAKED_QUADRUPLE:
41 return self._find_naked_xle(4, locked_only=False)
42 if sol_type == SolutionType.HIDDEN_PAIR:
43 return self._find_hidden_xle(2)
44 if sol_type == SolutionType.HIDDEN_TRIPLE:
45 return self._find_hidden_xle(3)
46 if sol_type == SolutionType.HIDDEN_QUADRUPLE:
47 return self._find_hidden_xle(4)
48 return None
50 # ------------------------------------------------------------------
51 # Full House
52 # ------------------------------------------------------------------
54 def find_full_house(self) -> SolutionStep | None:
55 """Non-consumingly scan ns_queue for a cell that is the last in any unit."""
56 g = self.grid
57 for cell, digit in g.ns_queue:
58 if g.values[cell] != 0:
59 continue
60 for c in CELL_CONSTRAINTS[cell]:
61 if all(g.free[c][d] == 0 for d in range(1, 10) if d != digit):
62 step = SolutionStep(SolutionType.FULL_HOUSE)
63 step.add_value(digit)
64 step.add_index(cell)
65 return step
66 return None
68 # ------------------------------------------------------------------
69 # Naked Single
70 # ------------------------------------------------------------------
72 def find_naked_single(self) -> SolutionStep | None:
73 """Consume ns_queue entries until a valid (unsolved) cell is found."""
74 g = self.grid
75 while g.ns_queue:
76 cell, digit = g.ns_queue.popleft()
77 if g.values[cell] == 0:
78 step = SolutionStep(SolutionType.NAKED_SINGLE)
79 step.add_value(digit)
80 step.add_index(cell)
81 return step
82 return None
84 # ------------------------------------------------------------------
85 # Hidden Single
86 # ------------------------------------------------------------------
88 def find_hidden_single(self) -> SolutionStep | None:
89 """Consume hs_queue; stop at first unsolved cell regardless of outcome."""
90 g = self.grid
91 while g.hs_queue:
92 cell, digit = g.hs_queue.popleft()
93 if g.values[cell] == 0:
94 for c in CELL_CONSTRAINTS[cell]:
95 if g.free[c][digit] == 1:
96 step = SolutionStep(SolutionType.HIDDEN_SINGLE)
97 step.add_value(digit)
98 step.add_index(cell)
99 return step
100 return None # valid cell but stale entry
101 return None
103 # ------------------------------------------------------------------
104 # Locked Candidates
105 # ------------------------------------------------------------------
107 def find_all(self, sol_type: SolutionType) -> list[SolutionStep]:
108 """Return ALL steps of the given type (used by reglib harness and /bsa mode)."""
109 if sol_type == SolutionType.FULL_HOUSE:
110 return self._find_all_full_house()
111 if sol_type == SolutionType.NAKED_SINGLE:
112 return self._find_all_naked_singles()
113 if sol_type == SolutionType.HIDDEN_SINGLE:
114 return self._find_all_hidden_singles()
115 if sol_type == SolutionType.LOCKED_CANDIDATES_1:
116 return self._lc_in_units_all(18, BLOCKS)
117 if sol_type == SolutionType.LOCKED_CANDIDATES_2:
118 return self._lc_in_units_all(0, LINES) + self._lc_in_units_all(9, COLS)
119 if sol_type in (SolutionType.LOCKED_PAIR,):
120 return self._find_naked_xle_all(2, locked_only=True)
121 if sol_type == SolutionType.NAKED_PAIR:
122 return self._find_naked_xle_all(2, locked_only=False)
123 if sol_type in (SolutionType.LOCKED_TRIPLE,):
124 return self._find_naked_xle_all(3, locked_only=True)
125 if sol_type == SolutionType.NAKED_TRIPLE:
126 return self._find_naked_xle_all(3, locked_only=False)
127 if sol_type == SolutionType.NAKED_QUADRUPLE:
128 return self._find_naked_xle_all(4, locked_only=False)
129 if sol_type == SolutionType.HIDDEN_PAIR:
130 return self._find_hidden_xle_all(2)
131 if sol_type == SolutionType.HIDDEN_TRIPLE:
132 return self._find_hidden_xle_all(3)
133 if sol_type == SolutionType.HIDDEN_QUADRUPLE:
134 return self._find_hidden_xle_all(4)
135 # For all other types, fall back to get_step (yields 0 or 1 result).
136 step = self.get_step(sol_type)
137 return [step] if step is not None else []
139 def _find_all_full_house(self) -> list[SolutionStep]:
140 """Return all Full House steps (one per unit with exactly one unsolved cell)."""
141 g = self.grid
142 results: list[SolutionStep] = []
143 seen: set[int] = set()
144 for unit_idx in range(27):
145 unsolved = [c for c in ALL_UNITS[unit_idx] if g.values[c] == 0]
146 if len(unsolved) != 1:
147 continue
148 cell = unsolved[0]
149 if cell in seen:
150 continue
151 seen.add(cell)
152 digit = next(
153 d for d in range(1, 10) if g.candidates[cell] & DIGIT_MASKS[d]
154 )
155 step = SolutionStep(SolutionType.FULL_HOUSE)
156 step.add_value(digit)
157 step.add_index(cell)
158 results.append(step)
159 return results
161 def _find_all_naked_singles(self) -> list[SolutionStep]:
162 """Return all Naked Single steps (one per cell with exactly one candidate)."""
163 g = self.grid
164 results: list[SolutionStep] = []
165 for cell in range(81):
166 if g.values[cell] != 0:
167 continue
168 mask = g.candidates[cell]
169 if not mask or (mask & (mask - 1)): # not exactly one bit set
170 continue
171 digit = mask.bit_length()
172 step = SolutionStep(SolutionType.NAKED_SINGLE)
173 step.add_value(digit)
174 step.add_index(cell)
175 results.append(step)
176 return results
178 def _find_all_hidden_singles(self) -> list[SolutionStep]:
179 """Return all Hidden Single steps by scanning all 27 units x 9 digits."""
180 g = self.grid
181 results: list[SolutionStep] = []
182 seen: set[tuple[int, int]] = set()
183 for unit_idx in range(27):
184 for digit in range(1, 10):
185 if g.free[unit_idx][digit] != 1:
186 continue
187 for cell in ALL_UNITS[unit_idx]:
188 if g.values[cell] == 0 and (g.candidates[cell] & DIGIT_MASKS[digit]):
189 if (cell, digit) not in seen:
190 seen.add((cell, digit))
191 step = SolutionStep(SolutionType.HIDDEN_SINGLE)
192 step.add_value(digit)
193 step.add_index(cell)
194 results.append(step)
195 break
196 return results
198 def _find_locked_candidates(self, sol_type: SolutionType) -> SolutionStep | None:
199 """Dispatch LC1 (blocks→row/col) and LC2 (row/col→block)."""
200 if sol_type == SolutionType.LOCKED_CANDIDATES_1:
201 return self._lc_in_units(18, BLOCKS)
202 # LOCKED_CANDIDATES_2
203 step = self._lc_in_units(0, LINES)
204 if step is not None:
205 return step
206 return self._lc_in_units(9, COLS)
208 def _lc_in_units(
209 self,
210 constraint_base: int,
211 units: tuple[tuple[int, ...], ...],
212 ) -> SolutionStep | None:
213 """Search one group of 9 units for a Locked Candidates step.
215 constraint_base:
216 18 → blocks (LC1: pointing)
217 0 → rows (LC2: claiming)
218 9 → cols (LC2: claiming)
219 """
220 g = self.grid
221 for unit_idx in range(9):
222 for cand in range(1, 10):
223 unit_free = g.free[unit_idx + constraint_base][cand]
224 if unit_free not in (2, 3):
225 continue
226 # Check whether all cells with cand share a secondary constraint
227 first = True
228 same = [True, True, True]
229 constraint = [0, 0, 0]
230 for cell in units[unit_idx]:
231 if not (g.candidates[cell] & DIGIT_MASKS[cand]):
232 continue
233 cc = CELL_CONSTRAINTS[cell]
234 if first:
235 constraint[0], constraint[1], constraint[2] = cc
236 first = False
237 else:
238 for j in range(3):
239 if same[j] and constraint[j] != cc[j]:
240 same[j] = False
242 skip_constraint = unit_idx + constraint_base
243 if constraint_base == 18:
244 # LC1: block cells all in same row → eliminate from that row
245 if same[0] and g.free[constraint[0]][cand] > unit_free:
246 return self._create_lc_step(
247 SolutionType.LOCKED_CANDIDATES_1, cand,
248 skip_constraint, ALL_UNITS[constraint[0]],
249 )
250 if same[1] and g.free[constraint[1]][cand] > unit_free:
251 return self._create_lc_step(
252 SolutionType.LOCKED_CANDIDATES_1, cand,
253 skip_constraint, ALL_UNITS[constraint[1]],
254 )
255 else:
256 # LC2: row/col cells all in same block → eliminate from that block
257 if same[2] and g.free[constraint[2]][cand] > unit_free:
258 return self._create_lc_step(
259 SolutionType.LOCKED_CANDIDATES_2, cand,
260 skip_constraint, ALL_UNITS[constraint[2]],
261 )
262 return None
264 def _lc_in_units_all(
265 self,
266 constraint_base: int,
267 units: tuple[tuple[int, ...], ...],
268 ) -> list[SolutionStep]:
269 """Like _lc_in_units but collects all matching steps instead of returning first."""
270 g = self.grid
271 results = []
272 for unit_idx in range(9):
273 for cand in range(1, 10):
274 unit_free = g.free[unit_idx + constraint_base][cand]
275 if unit_free not in (2, 3):
276 continue
277 first = True
278 same = [True, True, True]
279 constraint = [0, 0, 0]
280 for cell in units[unit_idx]:
281 if not (g.candidates[cell] & DIGIT_MASKS[cand]):
282 continue
283 cc = CELL_CONSTRAINTS[cell]
284 if first:
285 constraint[0], constraint[1], constraint[2] = cc
286 first = False
287 else:
288 for j in range(3):
289 if same[j] and constraint[j] != cc[j]:
290 same[j] = False
292 skip_constraint = unit_idx + constraint_base
293 if constraint_base == 18:
294 if same[0] and g.free[constraint[0]][cand] > unit_free:
295 results.append(self._create_lc_step(
296 SolutionType.LOCKED_CANDIDATES_1, cand,
297 skip_constraint, ALL_UNITS[constraint[0]],
298 ))
299 if same[1] and g.free[constraint[1]][cand] > unit_free:
300 results.append(self._create_lc_step(
301 SolutionType.LOCKED_CANDIDATES_1, cand,
302 skip_constraint, ALL_UNITS[constraint[1]],
303 ))
304 else:
305 if same[2] and g.free[constraint[2]][cand] > unit_free:
306 results.append(self._create_lc_step(
307 SolutionType.LOCKED_CANDIDATES_2, cand,
308 skip_constraint, ALL_UNITS[constraint[2]],
309 ))
310 return results
312 def _create_lc_step(
313 self,
314 sol_type: SolutionType,
315 cand: int,
316 skip_constraint: int,
317 unit_cells: tuple[int, ...],
318 ) -> SolutionStep:
319 """Build an LC step: cells in unit_cells that hold cand and are NOT in
320 skip_constraint are eliminations; those inside skip_constraint are the
321 pattern cells (stored in indices)."""
322 g = self.grid
323 step = SolutionStep(sol_type)
324 step.add_value(cand)
325 for cell in unit_cells:
326 if g.candidates[cell] & DIGIT_MASKS[cand]:
327 if skip_constraint in CELL_CONSTRAINTS[cell]:
328 step.add_index(cell)
329 else:
330 step.add_candidate_to_delete(cell, cand)
331 return step
333 # ------------------------------------------------------------------
334 # Naked Subsets (Pair / Triple / Quad + Locked variants)
335 # ------------------------------------------------------------------
337 def _find_naked_xle(self, anz: int, locked_only: bool) -> SolutionStep | None:
338 """Find Naked/Locked Subset of size anz.
340 Mirrors findNakedXle: BLOCKS first (only place locked subsets arise),
341 then LINES, then COLS.
342 """
343 naked_only = not locked_only
344 step = self._naked_in_units(BLOCKS, anz, locked_only, naked_only)
345 if step is not None or locked_only:
346 return step
347 step = self._naked_in_units(LINES, anz, False, True)
348 if step is not None:
349 return step
350 return self._naked_in_units(COLS, anz, False, True)
352 def _find_naked_xle_all(self, anz: int, locked_only: bool) -> list[SolutionStep]:
353 """Collect ALL Naked/Locked Subset steps of size anz."""
354 naked_only = not locked_only
355 results: list[SolutionStep] = []
356 self._naked_in_units(BLOCKS, anz, locked_only, naked_only, _results=results)
357 if not locked_only:
358 self._naked_in_units(LINES, anz, False, True, _results=results)
359 self._naked_in_units(COLS, anz, False, True, _results=results)
360 return results
362 def _naked_in_units(
363 self,
364 units: tuple[tuple[int, ...], ...],
365 anz: int,
366 locked_only: bool,
367 naked_only: bool,
368 _results: list[SolutionStep] | None = None,
369 ) -> SolutionStep | None:
370 g = self.grid
371 for entity in range(9):
372 # Collect unsolved cells with 1..anz candidates
373 eligible: list[int] = []
374 for cell in units[entity]:
375 cnt = g.candidates[cell].bit_count()
376 if 0 < cnt <= anz:
377 eligible.append(cell)
378 n = len(eligible)
379 if n < anz:
380 continue
382 # Enumerate combinations using mirrored Java nested loops with
383 # early-exit when union already exceeds anz digits.
384 for i1 in range(n - anz + 1):
385 m1 = g.candidates[eligible[i1]]
386 for i2 in range(i1 + 1, n - anz + 2):
387 m2 = m1 | g.candidates[eligible[i2]]
388 if m2.bit_count() > anz:
389 continue
390 if anz == 2:
391 if m2.bit_count() == anz:
392 step = self._create_subset_step(
393 [eligible[i1], eligible[i2]], m2,
394 anz, locked_only, naked_only,
395 )
396 if step is not None:
397 if _results is None:
398 return step
399 _results.append(step)
400 else:
401 for i3 in range(i2 + 1, n - anz + 3):
402 m3 = m2 | g.candidates[eligible[i3]]
403 if m3.bit_count() > anz:
404 continue
405 if anz == 3:
406 if m3.bit_count() == anz:
407 step = self._create_subset_step(
408 [eligible[i1], eligible[i2], eligible[i3]], m3,
409 anz, locked_only, naked_only,
410 )
411 if step is not None:
412 if _results is None:
413 return step
414 _results.append(step)
415 else:
416 for i4 in range(i3 + 1, n):
417 m4 = m3 | g.candidates[eligible[i4]]
418 if m4.bit_count() > anz:
419 continue
420 if m4.bit_count() == anz:
421 step = self._create_subset_step(
422 [eligible[i1], eligible[i2],
423 eligible[i3], eligible[i4]], m4,
424 anz, locked_only, naked_only,
425 )
426 if step is not None:
427 if _results is None:
428 return step
429 _results.append(step)
430 return None
432 def _create_subset_step(
433 self,
434 cells: list[int],
435 cands_mask: int,
436 anz: int,
437 locked_only: bool,
438 naked_only: bool,
439 ) -> SolutionStep | None:
440 """Build and classify a Naked Subset step (Naked/Locked Pair/Triple/Quad).
442 Mirrors createSubsetStep for the Naked branch:
443 - Eliminates cands_mask from all cells in shared constraints outside subset.
444 - Detects Locked if eliminations occur in both the shared row/col AND the
445 shared box, and cells share box + row or box + col.
446 """
447 g = self.grid
448 cells_set = set(cells)
449 cc0 = CELL_CONSTRAINTS[cells[0]]
451 # Which of the 3 constraint types are shared by ALL subset cells?
452 same = [True, True, True]
453 for cell in cells[1:]:
454 cc = CELL_CONSTRAINTS[cell]
455 for j in range(3):
456 if same[j] and cc0[j] != cc[j]:
457 same[j] = False
459 # Collect eliminations; track whether they occur outside the box
460 to_delete: list[tuple[int, int]] = []
461 seen_elims: set[tuple[int, int]] = set()
462 found_constraint = [False, False, False]
463 anz_found = 0
465 for i in range(3):
466 if not same[i]:
467 continue
468 for cell in ALL_UNITS[cc0[i]]:
469 if cell in cells_set:
470 continue
471 del_mask = g.candidates[cell] & cands_mask
472 if not del_mask:
473 continue
474 for d in range(1, 10):
475 if del_mask & DIGIT_MASKS[d]:
476 key = (cell, d)
477 if key not in seen_elims:
478 seen_elims.add(key)
479 to_delete.append(key)
480 if not found_constraint[i]:
481 # Count this constraint if: it's the box (i==2)
482 # OR the cell is outside the block (not sharing block with subset)
483 if i == 2 or CELL_CONSTRAINTS[cell][2] != cc0[2]:
484 found_constraint[i] = True
485 anz_found += 1
487 if not to_delete:
488 return None
490 # Locked: pair/triple sharing box+row or box+col, with deletions in both
491 is_locked = (
492 anz < 4
493 and anz_found > 1
494 and same[2] and (same[0] or same[1])
495 )
497 if locked_only and not is_locked:
498 return None
499 if naked_only and is_locked:
500 return None
502 if is_locked:
503 sol_type = SolutionType.LOCKED_PAIR if anz == 2 else SolutionType.LOCKED_TRIPLE
504 else:
505 sol_type = (
506 SolutionType.NAKED_PAIR,
507 SolutionType.NAKED_TRIPLE,
508 SolutionType.NAKED_QUADRUPLE,
509 )[anz - 2]
511 step = SolutionStep(sol_type)
512 for cell in cells:
513 step.add_index(cell)
514 for d in range(1, 10):
515 if cands_mask & DIGIT_MASKS[d]:
516 step.add_value(d)
517 for cell, d in to_delete:
518 step.add_candidate_to_delete(cell, d)
519 return step
521 # ------------------------------------------------------------------
522 # Hidden Subsets (Pair / Triple / Quad)
523 # ------------------------------------------------------------------
525 def _find_hidden_xle(self, anz: int) -> SolutionStep | None:
526 """Find Hidden Subset of size anz.
528 Mirrors findHiddenXle: BLOCKS (constraintBase=18) first, then LINES
529 (constraintBase=0), then COLS (constraintBase=9).
530 """
531 step = self._hidden_in_units(18, BLOCKS, anz)
532 if step is not None:
533 return step
534 step = self._hidden_in_units(0, LINES, anz)
535 if step is not None:
536 return step
537 return self._hidden_in_units(9, COLS, anz)
539 def _find_hidden_xle_all(self, anz: int) -> list[SolutionStep]:
540 """Collect ALL Hidden Subset steps of size anz."""
541 results: list[SolutionStep] = []
542 self._hidden_in_units(18, BLOCKS, anz, _results=results)
543 self._hidden_in_units(0, LINES, anz, _results=results)
544 self._hidden_in_units(9, COLS, anz, _results=results)
545 return results
547 def _hidden_in_units(
548 self,
549 constraint_base: int,
550 units: tuple[tuple[int, ...], ...],
551 anz: int,
552 _results: list[SolutionStep] | None = None,
553 ) -> SolutionStep | None:
554 g = self.grid
555 for entity in range(9):
556 # Need more than anz unsolved cells for a hidden subset to exist
557 unsolved = sum(1 for cell in units[entity] if g.candidates[cell])
558 if unsolved <= anz:
559 continue
561 constraint_idx = constraint_base + entity
563 # Collect digits whose free count is 1..anz and build per-digit
564 # bitmask of positions within this unit (bit j set → position j has digit)
565 ipc: list[int] = [0] * 10 # ipc[d] = position bitmask for digit d
566 eligible: list[int] = []
567 for d in range(1, 10):
568 f = g.free[constraint_idx][d]
569 if 0 < f <= anz:
570 eligible.append(d)
571 for j, cell in enumerate(units[entity]):
572 if g.candidates[cell] & DIGIT_MASKS[d]:
573 ipc[d] |= 1 << j
575 if len(eligible) < anz:
576 continue
578 ne = len(eligible)
580 # Enumerate digit combinations; union of ipc masks must cover exactly anz cells
581 for i1 in range(ne - anz + 1):
582 d1 = eligible[i1]
583 cm1 = ipc[d1]
584 for i2 in range(i1 + 1, ne - anz + 2):
585 d2 = eligible[i2]
586 cm2 = cm1 | ipc[d2]
587 if anz == 2:
588 if cm2.bit_count() == 2:
589 step = self._create_hidden_step(
590 units[entity], [d1, d2], cm2,
591 )
592 if step is not None:
593 if _results is None:
594 return step
595 _results.append(step)
596 else:
597 for i3 in range(i2 + 1, ne - anz + 3):
598 d3 = eligible[i3]
599 cm3 = cm2 | ipc[d3]
600 if anz == 3:
601 if cm3.bit_count() == 3:
602 step = self._create_hidden_step(
603 units[entity], [d1, d2, d3], cm3,
604 )
605 if step is not None:
606 if _results is None:
607 return step
608 _results.append(step)
609 else:
610 for i4 in range(i3 + 1, ne):
611 d4 = eligible[i4]
612 cm4 = cm3 | ipc[d4]
613 if cm4.bit_count() == 4:
614 step = self._create_hidden_step(
615 units[entity], [d1, d2, d3, d4], cm4,
616 )
617 if step is not None:
618 if _results is None:
619 return step
620 _results.append(step)
621 return None
623 def _create_hidden_step(
624 self,
625 unit_cells: tuple[int, ...],
626 digits: list[int],
627 cell_pos_mask: int,
628 ) -> SolutionStep | None:
629 """Build a Hidden Subset step: delete all non-subset candidates from subset cells."""
630 g = self.grid
631 cands_mask = 0
632 for d in digits:
633 cands_mask |= DIGIT_MASKS[d]
635 cells = [unit_cells[j] for j in range(9) if cell_pos_mask & (1 << j)]
637 to_delete: list[tuple[int, int]] = []
638 for cell in cells:
639 del_mask = g.candidates[cell] & ~cands_mask
640 for d in range(1, 10):
641 if del_mask & DIGIT_MASKS[d]:
642 to_delete.append((cell, d))
644 if not to_delete:
645 return None
647 anz = len(digits)
648 sol_type = (
649 SolutionType.HIDDEN_PAIR,
650 SolutionType.HIDDEN_TRIPLE,
651 SolutionType.HIDDEN_QUADRUPLE,
652 )[anz - 2]
654 step = SolutionStep(sol_type)
655 for cell in cells:
656 step.add_index(cell)
657 for d in digits:
658 step.add_value(d)
659 for cell, d in to_delete:
660 step.add_candidate_to_delete(cell, d)
661 return step