Coverage for src / hodoku / solver / single_digit.py: 97%
414 statements
« prev ^ index » next coverage.py v7.13.5, created at 2026-04-21 08:35 +0000
1"""Single-digit pattern solver: Skyscraper, 2-String Kite, Empty Rectangle.
3Mirrors Java's SingleDigitPatternSolver.
4"""
6from __future__ import annotations
8from typing import TYPE_CHECKING
10from hodoku.core.grid import (
11 Grid,
12 ALL_UNITS,
13 BLOCKS,
14 BLOCK_MASKS,
15 BUDDIES,
16 COL_MASKS,
17 CONSTRAINTS,
18 COLS,
19 LINE_MASKS,
20 LINES,
21)
22from hodoku.core.solution_step import Candidate, SolutionStep
23from hodoku.core.types import SolutionType
25if TYPE_CHECKING:
26 from hodoku.config import StepSearchConfig
28# ---------------------------------------------------------------------------
29# Empty Rectangle static lookup tables (computed once at import time)
30# ---------------------------------------------------------------------------
32# Relative grid-index offsets within a block for the "empty" cells of each ER pattern.
33# Offsets are from the top-left cell of the block (index 0 of the block).
34_ER_OFFSETS: list[list[int]] = [
35 [0, 1, 9, 10],
36 [0, 2, 9, 11],
37 [1, 2, 10, 11],
38 [0, 1, 18, 19],
39 [0, 2, 18, 20],
40 [1, 2, 19, 20],
41 [9, 10, 18, 19],
42 [9, 11, 18, 20],
43 [10, 11, 19, 20],
44]
46# Row / col offsets for the ER line/col, relative to the block's first row/col.
47_ER_LINE_OFFSETS: list[int] = [2, 2, 2, 1, 1, 1, 0, 0, 0]
48_ER_COL_OFFSETS: list[int] = [2, 1, 0, 2, 1, 0, 2, 1, 0]
51def _build_er_tables() -> tuple[
52 list[list[int]], list[list[int]], list[list[int]]
53]:
54 """Precompute ER_SETS, ER_LINES, ER_COLS for all 9 blocks × 9 patterns."""
55 er_sets: list[list[int]] = [[0] * 9 for _ in range(9)]
56 er_lines: list[list[int]] = [[0] * 9 for _ in range(9)]
57 er_cols: list[list[int]] = [[0] * 9 for _ in range(9)]
58 for b in range(9):
59 b0 = BLOCKS[b][0] # index of the top-left cell of block b
60 r0, c0, _ = CONSTRAINTS[b0]
61 for p in range(9):
62 er_sets[b][p] = sum(1 << (b0 + off) for off in _ER_OFFSETS[p])
63 er_lines[b][p] = _ER_LINE_OFFSETS[p] + r0
64 er_cols[b][p] = _ER_COL_OFFSETS[p] + c0
65 return er_sets, er_lines, er_cols
68ER_SETS, ER_LINES, ER_COLS = _build_er_tables()
70_BLOCK_ENTITY = 2 # Entity type for BLOCK (matches Java's Sudoku2.BLOCK)
73# ---------------------------------------------------------------------------
74# Solver
75# ---------------------------------------------------------------------------
77class SingleDigitSolver:
78 """Skyscraper, 2-String Kite, Empty Rectangle."""
80 def __init__(self, grid: Grid, search_config: StepSearchConfig | None = None) -> None:
81 self.grid = grid
82 if search_config is not None:
83 self._allow_duals_and_siamese = search_config.allow_duals_and_siamese
84 else:
85 # Backward-compatible default (pre-config behavior)
86 self._allow_duals_and_siamese = True
88 def get_step(self, sol_type: SolutionType) -> SolutionStep | None:
89 if sol_type == SolutionType.SKYSCRAPER:
90 return self._find_skyscraper()
91 if sol_type == SolutionType.TWO_STRING_KITE:
92 return self._find_two_string_kite()
93 if sol_type == SolutionType.EMPTY_RECTANGLE:
94 return self._find_empty_rectangle()
95 if sol_type == SolutionType.DUAL_TWO_STRING_KITE:
96 if not self._allow_duals_and_siamese:
97 return None
98 steps = self._find_dual_two_string_kites()
99 return steps[0] if steps else None
100 if sol_type == SolutionType.DUAL_EMPTY_RECTANGLE:
101 if not self._allow_duals_and_siamese:
102 return None
103 steps = self._find_dual_empty_rectangles()
104 return steps[0] if steps else None
105 return None
107 def find_all(self, sol_type: SolutionType) -> list[SolutionStep]:
108 if sol_type == SolutionType.SKYSCRAPER:
109 return self._find_skyscraper_all()
110 if sol_type == SolutionType.TWO_STRING_KITE:
111 return self._find_two_string_kite_all()
112 if sol_type == SolutionType.EMPTY_RECTANGLE:
113 return self._find_empty_rectangle_all()
114 if sol_type == SolutionType.DUAL_TWO_STRING_KITE:
115 if not self._allow_duals_and_siamese:
116 return []
117 return self._find_dual_two_string_kites()
118 if sol_type == SolutionType.DUAL_EMPTY_RECTANGLE:
119 if not self._allow_duals_and_siamese:
120 return []
121 return self._find_dual_empty_rectangles()
122 return []
124 def _find_skyscraper_all(self) -> list[SolutionStep]:
125 """Return ALL Skyscraper steps."""
126 grid = self.grid
127 results: list[SolutionStep] = []
128 seen_elims: set[tuple] = set()
129 for cand in range(1, 10):
130 for lines in (True, False):
131 c_start, c_end = (0, 9) if lines else (9, 18)
132 pairs = self._collect_pairs(c_start, c_end, cand)
133 n = len(pairs)
134 for i in range(n):
135 a0, a1 = pairs[i]
136 for j in range(i + 1, n):
137 b0, b1 = pairs[j]
138 if lines:
139 if CONSTRAINTS[a0][1] == CONSTRAINTS[b0][1]:
140 other = 1
141 elif CONSTRAINTS[a1][1] == CONSTRAINTS[b1][1]:
142 other = 0
143 else:
144 continue
145 else:
146 if CONSTRAINTS[a0][0] == CONSTRAINTS[b0][0]:
147 other = 1
148 elif CONSTRAINTS[a1][0] == CONSTRAINTS[b1][0]:
149 other = 0
150 else:
151 continue
153 free_i = pairs[i][other]
154 free_j = pairs[j][other]
156 if lines:
157 if CONSTRAINTS[free_i][1] == CONSTRAINTS[free_j][1]:
158 continue
159 else:
160 if CONSTRAINTS[free_i][0] == CONSTRAINTS[free_j][0]:
161 continue
163 elim = (
164 grid.candidate_sets[cand]
165 & BUDDIES[free_i]
166 & BUDDIES[free_j]
167 )
168 if elim:
169 linked_i = pairs[i][1 - other]
170 linked_j = pairs[j][1 - other]
171 key = (cand, elim)
172 if key not in seen_elims:
173 seen_elims.add(key)
174 step = SolutionStep(SolutionType.SKYSCRAPER)
175 step.add_value(cand)
176 step.add_index(free_i)
177 step.add_index(free_j)
178 step.add_index(linked_i)
179 step.add_index(linked_j)
180 tmp = elim
181 while tmp:
182 lsb = tmp & -tmp
183 step.add_candidate_to_delete(
184 lsb.bit_length() - 1, cand
185 )
186 tmp ^= lsb
187 results.append(step)
188 return results
190 def _find_two_string_kite_all(self) -> list[SolutionStep]:
191 """Return ALL 2-String Kite steps."""
192 grid = self.grid
193 results: list[SolutionStep] = []
194 seen_elims: set[tuple] = set()
195 for cand in range(1, 10):
196 line_pairs = self._collect_pairs(0, 9, cand)
197 col_pairs = self._collect_pairs(9, 18, cand)
198 for lp in line_pairs:
199 for cp in col_pairs:
200 la, lb = lp
201 ca, cb = cp
203 la_b = CONSTRAINTS[la][2]
204 lb_b = CONSTRAINTS[lb][2]
205 ca_b = CONSTRAINTS[ca][2]
206 cb_b = CONSTRAINTS[cb][2]
207 if la_b == ca_b:
208 pass
209 elif la_b == cb_b:
210 ca, cb = cb, ca
211 elif lb_b == ca_b:
212 la, lb = lb, la
213 elif lb_b == cb_b:
214 la, lb = lb, la
215 ca, cb = cb, ca
216 else:
217 continue
219 if la == ca or la == cb or lb == ca or lb == cb:
220 continue
222 cross = CONSTRAINTS[cb][0] * 9 + CONSTRAINTS[lb][1]
223 if grid.candidate_sets[cand] >> cross & 1:
224 key = (cand, cross)
225 if key not in seen_elims:
226 seen_elims.add(key)
227 step = SolutionStep(SolutionType.TWO_STRING_KITE)
228 step.add_value(cand)
229 step.add_index(lb)
230 step.add_index(cb)
231 step.add_index(la)
232 step.add_index(ca)
233 step.add_candidate_to_delete(cross, cand)
234 step.fins.append(Candidate(la, cand))
235 step.fins.append(Candidate(ca, cand))
236 results.append(step)
237 return results
239 def _find_empty_rectangle_all(self) -> list[SolutionStep]:
240 """Return ALL Empty Rectangle steps."""
241 grid = self.grid
242 results: list[SolutionStep] = []
243 seen_elims: set[tuple] = set()
244 for cand in range(1, 10):
245 for b in range(9):
246 count = grid.free[18 + b][cand]
247 if count < 2 or count > 5:
248 continue
249 block_cands = grid.candidate_sets[cand] & BLOCK_MASKS[b]
250 for p in range(9):
251 if block_cands & ER_SETS[b][p]:
252 continue
254 er_line = ER_LINES[b][p]
255 er_col = ER_COLS[b][p]
257 line_full = block_cands & LINE_MASKS[er_line]
258 line_part = line_full & ~COL_MASKS[er_col]
259 if not line_part:
260 continue
262 col_full = block_cands & COL_MASKS[er_col]
263 col_part = col_full & ~LINE_MASKS[er_line]
264 if not col_part:
265 continue
267 for cells, col_mode, constr in (
268 (LINES[er_line], False, er_col),
269 (COLS[er_col], True, er_line),
270 ):
271 step = self._check_er(cand, b, block_cands, cells, col_mode, constr)
272 if step:
273 key = tuple(sorted(
274 (c.index, c.value) for c in step.candidates_to_delete
275 ))
276 if key not in seen_elims:
277 seen_elims.add(key)
278 results.append(step)
279 return results
281 # ------------------------------------------------------------------
282 # Dual patterns
283 # ------------------------------------------------------------------
285 def _find_dual_two_string_kites(self) -> list[SolutionStep]:
286 """Find Dual 2-String Kites.
288 A dual 2SK combines two 2SKs that share the same block connection
289 (indices[2] and indices[3]) but produce different eliminations.
290 """
291 kites = self._find_two_string_kite_all()
292 duals: list[SolutionStep] = []
293 n = len(kites)
294 for i in range(n - 1):
295 s1 = kites[i]
296 b11 = s1.indices[2]
297 b12 = s1.indices[3]
298 for j in range(i + 1, n):
299 s2 = kites[j]
300 b21 = s2.indices[2]
301 b22 = s2.indices[3]
302 if not ((b11 == b21 and b12 == b22) or (b12 == b21 and b11 == b22)):
303 continue
304 if s1.candidates_to_delete[0] == s2.candidates_to_delete[0]:
305 continue # same elimination
306 dual = SolutionStep(SolutionType.DUAL_TWO_STRING_KITE)
307 dual.values = list(s1.values)
308 for idx in s1.indices:
309 dual.add_index(idx)
310 for idx in s2.indices:
311 dual.add_index(idx)
312 dual.fins = list(s1.fins)
313 dual.candidates_to_delete = list(s1.candidates_to_delete)
314 dual.add_candidate_to_delete(
315 s2.candidates_to_delete[0].index,
316 s2.candidates_to_delete[0].value,
317 )
318 duals.append(dual)
319 return duals
321 def _find_dual_empty_rectangles(self) -> list[SolutionStep]:
322 """Find Dual Empty Rectangles.
324 A dual ER combines two ERs from the same box with the same ER
325 candidates (fins) but different eliminations.
326 """
327 ers = self._find_empty_rectangle_all()
328 duals: list[SolutionStep] = []
329 n = len(ers)
330 for i in range(n - 1):
331 s1 = ers[i]
332 for j in range(i + 1, n):
333 s2 = ers[j]
334 # Same box (entity/entityNumber)
335 if s1.entity != s2.entity or s1.entity_number != s2.entity_number:
336 continue
337 # Same fins (box candidates)
338 if len(s1.fins) != len(s2.fins):
339 continue
340 if s1.fins != s2.fins:
341 continue
342 # Different elimination
343 if s1.candidates_to_delete[0] == s2.candidates_to_delete[0]:
344 continue
345 dual = SolutionStep(SolutionType.DUAL_EMPTY_RECTANGLE)
346 dual.values = list(s1.values)
347 dual.entity = s1.entity
348 dual.entity_number = s1.entity_number
349 for idx in s1.indices:
350 dual.add_index(idx)
351 for idx in s2.indices:
352 dual.add_index(idx)
353 dual.fins = list(s1.fins)
354 dual.candidates_to_delete = list(s1.candidates_to_delete)
355 dual.add_candidate_to_delete(
356 s2.candidates_to_delete[0].index,
357 s2.candidates_to_delete[0].value,
358 )
359 duals.append(dual)
360 return duals
362 # ------------------------------------------------------------------
363 # Shared helper
364 # ------------------------------------------------------------------
366 def _collect_pairs(
367 self, c_start: int, c_end: int, cand: int
368 ) -> list[tuple[int, int]]:
369 """Return (cell_a, cell_b) for each unit in [c_start, c_end) with
370 exactly 2 candidates for digit cand."""
371 grid = self.grid
372 pairs: list[tuple[int, int]] = []
373 for constr in range(c_start, c_end):
374 if grid.free[constr][cand] == 2:
375 found: list[int] = []
376 for cell in ALL_UNITS[constr]:
377 if grid.candidate_sets[cand] >> cell & 1:
378 found.append(cell)
379 if len(found) == 2:
380 break
381 if len(found) == 2:
382 pairs.append((found[0], found[1]))
383 return pairs
385 # ------------------------------------------------------------------
386 # Skyscraper
387 # ------------------------------------------------------------------
389 def _find_skyscraper(self) -> SolutionStep | None:
390 """Find the first Skyscraper elimination.
392 Row-mode: scan rows; linked ends share the same column.
393 Col-mode: scan cols; linked ends share the same row.
395 Java calls findSkyscraper(rows, onlyOne=true) first for ALL candidates,
396 then findSkyscraper(cols, onlyOne=true). So the outer loop is lines-mode,
397 inner loop is candidate digit.
398 """
399 grid = self.grid
400 for lines in (True, False):
401 for cand in range(1, 10):
402 c_start, c_end = (0, 9) if lines else (9, 18)
403 pairs = self._collect_pairs(c_start, c_end, cand)
404 n = len(pairs)
405 for i in range(n):
406 a0, a1 = pairs[i]
407 for j in range(i + 1, n):
408 b0, b1 = pairs[j]
409 # Find which pair of ends share a row/col (the "linked" ends).
410 # other = index into each pair for the FREE (non-linked) end.
411 if lines:
412 if CONSTRAINTS[a0][1] == CONSTRAINTS[b0][1]:
413 other = 1 # a0,b0 linked (same col); a1,b1 free
414 elif CONSTRAINTS[a1][1] == CONSTRAINTS[b1][1]:
415 other = 0 # a1,b1 linked; a0,b0 free
416 else:
417 continue
418 else:
419 if CONSTRAINTS[a0][0] == CONSTRAINTS[b0][0]:
420 other = 1 # a0,b0 linked (same row); a1,b1 free
421 elif CONSTRAINTS[a1][0] == CONSTRAINTS[b1][0]:
422 other = 0
423 else:
424 continue
426 free_i = pairs[i][other]
427 free_j = pairs[j][other]
429 # If free ends also share the relevant unit → X-Wing, skip
430 if lines:
431 if CONSTRAINTS[free_i][1] == CONSTRAINTS[free_j][1]:
432 continue
433 else:
434 if CONSTRAINTS[free_i][0] == CONSTRAINTS[free_j][0]:
435 continue
437 elim = (
438 grid.candidate_sets[cand]
439 & BUDDIES[free_i]
440 & BUDDIES[free_j]
441 )
442 if elim:
443 linked_i = pairs[i][1 - other]
444 linked_j = pairs[j][1 - other]
445 step = SolutionStep(SolutionType.SKYSCRAPER)
446 step.add_value(cand)
447 step.add_index(free_i)
448 step.add_index(free_j)
449 step.add_index(linked_i)
450 step.add_index(linked_j)
451 tmp = elim
452 while tmp:
453 lsb = tmp & -tmp
454 step.add_candidate_to_delete(
455 lsb.bit_length() - 1, cand
456 )
457 tmp ^= lsb
458 return step
459 return None
461 # ------------------------------------------------------------------
462 # 2-String Kite
463 # ------------------------------------------------------------------
465 def _find_two_string_kite(self) -> SolutionStep | None:
466 """Find the first 2-String Kite elimination.
468 One strong link in a row, one in a col, connected through a shared block.
469 The "free ends" see a common candidate to eliminate.
470 """
471 grid = self.grid
472 for cand in range(1, 10):
473 line_pairs = self._collect_pairs(0, 9, cand)
474 col_pairs = self._collect_pairs(9, 18, cand)
475 for lp in line_pairs:
476 for cp in col_pairs:
477 # Local mutable copies so we can reorder without corrupting lists
478 la, lb = lp # la=index 0, lb=index 1 (mutable labels)
479 ca, cb = cp
481 # Reorder so that la and ca are the block-connected ends.
482 # 4 possible alignments:
483 la_b = CONSTRAINTS[la][2]
484 lb_b = CONSTRAINTS[lb][2]
485 ca_b = CONSTRAINTS[ca][2]
486 cb_b = CONSTRAINTS[cb][2]
487 if la_b == ca_b:
488 pass # la,ca share block → free: lb,cb
489 elif la_b == cb_b:
490 ca, cb = cb, ca # swap col pair
491 elif lb_b == ca_b:
492 la, lb = lb, la # swap line pair
493 elif lb_b == cb_b:
494 la, lb = lb, la
495 ca, cb = cb, ca # swap both
496 else:
497 continue # no shared block
499 # All 4 cells must be distinct
500 if la == ca or la == cb or lb == ca or lb == cb:
501 continue
503 # cross_index = cell at (row of cb, col of lb)
504 cross = CONSTRAINTS[cb][0] * 9 + CONSTRAINTS[lb][1]
505 if grid.candidate_sets[cand] >> cross & 1:
506 step = SolutionStep(SolutionType.TWO_STRING_KITE)
507 step.add_value(cand)
508 step.add_index(lb) # row free end
509 step.add_index(cb) # col free end
510 step.add_index(la) # row block end
511 step.add_index(ca) # col block end
512 step.add_candidate_to_delete(cross, cand)
513 step.fins.append(Candidate(la, cand))
514 step.fins.append(Candidate(ca, cand))
515 return step
516 return None
518 # ------------------------------------------------------------------
519 # Empty Rectangle
520 # ------------------------------------------------------------------
522 def _find_empty_rectangle(self) -> SolutionStep | None:
523 """Find the first Empty Rectangle elimination."""
524 grid = self.grid
525 for cand in range(1, 10):
526 for b in range(9):
527 count = grid.free[18 + b][cand]
528 if count < 2 or count > 5:
529 continue
530 block_cands = grid.candidate_sets[cand] & BLOCK_MASKS[b]
531 for p in range(9):
532 # Cells at these positions must be empty (no candidate)
533 if block_cands & ER_SETS[b][p]:
534 continue
536 er_line = ER_LINES[b][p]
537 er_col = ER_COLS[b][p]
539 # Line part: block candidates in ER row, excluding ER col intersection
540 line_full = block_cands & LINE_MASKS[er_line]
541 line_part = line_full & ~COL_MASKS[er_col]
542 if not line_part:
543 continue
545 # Col part: block candidates in ER col, excluding ER row intersection
546 col_full = block_cands & COL_MASKS[er_col]
547 col_part = col_full & ~LINE_MASKS[er_line]
548 if not col_part:
549 continue
551 # Direction 1: iterate ER row cells, conjugate search in cols
552 step = self._check_er(
553 cand, b, block_cands,
554 LINES[er_line], False, er_col,
555 )
556 if step:
557 return step
559 # Direction 2: iterate ER col cells, conjugate search in rows
560 step = self._check_er(
561 cand, b, block_cands,
562 COLS[er_col], True, er_line,
563 )
564 if step:
565 return step
567 return None
569 def _check_er(
570 self,
571 cand: int,
572 block: int,
573 block_cands: int,
574 cells: tuple[int, ...],
575 reversed_: bool,
576 er_unit_idx: int,
577 ) -> SolutionStep | None:
578 """Check ER eliminations in one scan direction.
580 reversed_=False: iterate ER row; conjugate search in columns.
581 er_unit_idx = er_col (0-8)
582 reversed_=True: iterate ER col; conjugate search in rows.
583 er_unit_idx = er_line (0-8)
584 """
585 grid = self.grid
586 conj_masks = LINE_MASKS if reversed_ else COL_MASKS
587 other_masks = COL_MASKS if reversed_ else LINE_MASKS
589 for index in cells:
590 if grid.values[index] != 0:
591 continue
592 r, c, b = CONSTRAINTS[index]
593 if b == block:
594 continue
595 if not (grid.candidate_sets[cand] >> index & 1):
596 continue
598 # Perpendicular dimension unit for conjugate-pair search
599 unit = r if reversed_ else c
600 conj_set = grid.candidate_sets[cand] & conj_masks[unit]
601 if conj_set.bit_count() != 2:
602 continue
604 index2 = (conj_set ^ (1 << index)).bit_length() - 1
605 r2, c2, _ = CONSTRAINTS[index2]
607 # index2's other-dimension unit
608 other_unit = c2 if reversed_ else r2
609 line_cands = grid.candidate_sets[cand] & other_masks[other_unit]
611 tmp = line_cands
612 while tmp:
613 lsb = tmp & -tmp
614 index_del = lsb.bit_length() - 1
615 tmp ^= lsb
616 _, _, b_del = CONSTRAINTS[index_del]
617 if b_del == block:
618 continue
619 r_del, c_del, _ = CONSTRAINTS[index_del]
620 unit_del = r_del if reversed_ else c_del
621 if unit_del == er_unit_idx:
622 step = SolutionStep(SolutionType.EMPTY_RECTANGLE)
623 step.entity = _BLOCK_ENTITY
624 step.entity_number = block + 1
625 step.add_value(cand)
626 step.add_index(index)
627 step.add_index(index2)
628 bc = block_cands
629 while bc:
630 lsb2 = bc & -bc
631 step.fins.append(
632 Candidate(lsb2.bit_length() - 1, cand)
633 )
634 bc ^= lsb2
635 step.add_candidate_to_delete(index_del, cand)
636 return step
638 return None