Coverage for src / hodoku / solver / misc.py: 95%
171 statements
« prev ^ index » next coverage.py v7.13.5, created at 2026-04-21 08:35 +0000
1"""Miscellaneous solver — Sue de Coq.
3Port of HoDoKu's MiscellaneousSolver.java.
4"""
6from __future__ import annotations
8from hodoku.core.grid import (
9 Grid, LINES, COLS,
10 LINE_MASKS, COL_MASKS, BLOCK_MASKS,
11)
12from hodoku.core.solution_step import Candidate, SolutionStep
13from hodoku.core.types import SolutionType
16def _popcount(v: int) -> int:
17 return v.bit_count()
20def _iter_bits(mask: int):
21 """Yield individual bit positions from a bitmask."""
22 while mask:
23 lsb = mask & -mask
24 yield lsb.bit_length() - 1
25 mask ^= lsb
28def _cand_mask_for_cells(grid: Grid, cell_mask: int) -> int:
29 """OR together the candidate bitmasks for all cells in *cell_mask*."""
30 result = 0
31 for idx in _iter_bits(cell_mask):
32 result |= grid.candidates[idx]
33 return result
36class MiscSolver:
37 """Sue de Coq solver."""
39 def __init__(self, grid: Grid) -> None:
40 self.grid = grid
42 # ------------------------------------------------------------------
43 # public API
44 # ------------------------------------------------------------------
46 def get_step(self, sol_type: SolutionType) -> SolutionStep | None:
47 if sol_type is SolutionType.SUE_DE_COQ:
48 return self._find_sdc(only_one=True)
49 return None
51 def find_all(self, sol_type: SolutionType) -> list[SolutionStep]:
52 if sol_type is SolutionType.SUE_DE_COQ:
53 results: list[SolutionStep] = []
54 self._find_sdc(only_one=False, results=results)
55 return results
56 return []
58 # ------------------------------------------------------------------
59 # Sue de Coq core
60 # ------------------------------------------------------------------
62 def _find_sdc(
63 self,
64 only_one: bool = True,
65 results: list[SolutionStep] | None = None,
66 ) -> SolutionStep | None:
67 grid = self.grid
68 # Build bitmask of empty (unsolved) cells
69 empty = 0
70 for i in range(81):
71 if grid.values[i] == 0:
72 empty |= 1 << i
74 # Try every (row_or_col, block) pair
75 for line_masks, line_units in ((LINE_MASKS, LINES), (COL_MASKS, COLS)):
76 for li in range(9):
77 non_block_all = line_masks[li] & empty
78 for bi in range(9):
79 block_all = BLOCK_MASKS[bi] & empty
80 intersection = non_block_all & block_all
81 if _popcount(intersection) < 2:
82 continue
83 step = self._check_intersection(
84 grid, intersection, non_block_all, block_all,
85 only_one, results,
86 )
87 if only_one and step is not None:
88 return step
89 return None
91 def _check_intersection(
92 self,
93 grid: Grid,
94 intersection: int,
95 non_block_all: int,
96 block_all: int,
97 only_one: bool,
98 results: list[SolutionStep] | None,
99 ) -> SolutionStep | None:
100 """Try all 2-cell and 3-cell subsets of the intersection."""
101 cells = list(_iter_bits(intersection))
102 n = len(cells)
104 for i1 in range(n - 1):
105 c1 = cells[i1]
106 cand1 = grid.candidates[c1]
107 mask1 = 1 << c1
109 for i2 in range(i1 + 1, n):
110 c2 = cells[i2]
111 cand2 = cand1 | grid.candidates[c2]
112 mask2 = mask1 | (1 << c2)
114 # 2-cell subset: need |V| >= |C| + 2, i.e. >= 4 candidates
115 n_plus = _popcount(cand2) - 2
116 if n_plus >= 2:
117 step = self._check_houses(
118 grid, mask2, cand2, n_plus,
119 non_block_all, block_all,
120 only_one, results,
121 )
122 if only_one and step is not None:
123 return step
125 # 3-cell subsets
126 for i3 in range(i2 + 1, n):
127 c3 = cells[i3]
128 cand3 = cand2 | grid.candidates[c3]
129 mask3 = mask2 | (1 << c3)
130 n_plus3 = _popcount(cand3) - 3
131 if n_plus3 >= 2:
132 step = self._check_houses(
133 grid, mask3, cand3, n_plus3,
134 non_block_all, block_all,
135 only_one, results,
136 )
137 if only_one and step is not None:
138 return step
139 return None
141 def _check_houses(
142 self,
143 grid: Grid,
144 inter_cells: int,
145 inter_cands: int,
146 n_plus: int,
147 non_block_all: int,
148 block_all: int,
149 only_one: bool,
150 results: list[SolutionStep] | None,
151 ) -> SolutionStep | None:
152 """Search for matching cell sets in the row/col and block."""
153 # Source cells: row/col cells NOT in the intersection
154 nb_source = non_block_all & ~inter_cells
155 # First pass: enumerate row/col subsets
156 return self._search_non_block(
157 grid, nb_source, inter_cells, inter_cands, n_plus,
158 block_all, only_one, results,
159 )
161 def _search_non_block(
162 self,
163 grid: Grid,
164 nb_source: int,
165 inter_cells: int,
166 inter_cands: int,
167 n_plus: int,
168 block_all: int,
169 only_one: bool,
170 results: list[SolutionStep] | None,
171 ) -> SolutionStep | None:
172 """Enumerate subsets of nb_source cells for the row/col part."""
173 if not nb_source:
174 return None
175 source_list = list(_iter_bits(nb_source))
177 # Iterative subset enumeration (matching Java's stack approach)
178 # We try all subsets of source_list, from size 1 upward.
179 # For each subset, check if it qualifies, then hand off to block search.
180 #
181 # Use a simple recursive generator for clarity.
182 return self._enum_nb_subsets(
183 grid, source_list, 0, 0, 0, 0,
184 inter_cells, inter_cands, n_plus,
185 block_all, only_one, results,
186 )
188 def _enum_nb_subsets(
189 self,
190 grid: Grid,
191 source: list[int],
192 pos: int,
193 level: int,
194 sel_cells: int,
195 sel_cands: int,
196 inter_cells: int,
197 inter_cands: int,
198 n_plus: int,
199 block_all: int,
200 only_one: bool,
201 results: list[SolutionStep] | None,
202 ) -> SolutionStep | None:
203 """Recursively enumerate non-block (row/col) subsets."""
204 for i in range(pos, len(source)):
205 idx = source[i]
206 new_cands = sel_cands | grid.candidates[idx]
208 # Prune: all candidates must be either from intersection or "extra"
209 # No constraint on allowed cands for first pass (allowedCandSet = MAX_MASK)
211 cands_from_inter = new_cands & inter_cands
212 n_contained = _popcount(cands_from_inter)
213 cands_extra = new_cands & ~inter_cands
214 n_extra = _popcount(cands_extra)
215 new_level = level + 1
216 new_cells = sel_cells | (1 << idx)
218 # The row/col set must:
219 # 1. Contain at least one candidate from the intersection (n_contained > 0)
220 # 2. Have more cells than extra candidates (new_level > n_extra)
221 # 3. Leave some intersection candidates for the block (new_level - n_extra < n_plus)
222 if n_contained > 0 and new_level > n_extra and new_level - n_extra < n_plus:
223 # Viable: search block
224 remaining_n_plus = n_plus - (new_level - n_extra)
225 # Block source: block cells not in intersection and not in nb selection
226 blk_source = block_all & ~inter_cells & ~new_cells
227 # Block can't use candidates already claimed by row/col
228 # (but extra candidates shared by both sets ARE allowed — handled in elimination)
229 blk_disallowed = new_cands & ~cands_extra # = intersection cands used by nb
230 blk_allowed_mask = ~blk_disallowed & 0x1FF
232 step = self._search_block(
233 grid, blk_source, blk_allowed_mask,
234 inter_cells, inter_cands, remaining_n_plus,
235 new_cells, new_cands,
236 block_all & ~inter_cells, # full block minus intersection for elims
237 only_one, results,
238 )
239 if only_one and step is not None:
240 return step
242 # Continue to larger subsets
243 step = self._enum_nb_subsets(
244 grid, source, i + 1, new_level, new_cells, new_cands,
245 inter_cells, inter_cands, n_plus,
246 block_all, only_one, results,
247 )
248 if only_one and step is not None:
249 return step
250 return None
252 def _search_block(
253 self,
254 grid: Grid,
255 blk_source: int,
256 blk_allowed_mask: int,
257 inter_cells: int,
258 inter_cands: int,
259 n_plus: int,
260 nb_cells: int,
261 nb_cands: int,
262 blk_elim_region: int,
263 only_one: bool,
264 results: list[SolutionStep] | None,
265 ) -> SolutionStep | None:
266 """Enumerate block cell subsets for the second pass."""
267 if not blk_source:
268 return None
269 source_list = list(_iter_bits(blk_source))
270 return self._enum_blk_subsets(
271 grid, source_list, 0, 0, 0, 0,
272 blk_allowed_mask, inter_cells, inter_cands, n_plus,
273 nb_cells, nb_cands, blk_elim_region,
274 only_one, results,
275 )
277 def _enum_blk_subsets(
278 self,
279 grid: Grid,
280 source: list[int],
281 pos: int,
282 level: int,
283 sel_cells: int,
284 sel_cands: int,
285 allowed_mask: int,
286 inter_cells: int,
287 inter_cands: int,
288 n_plus: int,
289 nb_cells: int,
290 nb_cands: int,
291 blk_elim_region: int,
292 only_one: bool,
293 results: list[SolutionStep] | None,
294 ) -> SolutionStep | None:
295 for i in range(pos, len(source)):
296 idx = source[i]
297 cell_cands = grid.candidates[idx]
299 # Cell must not contain disallowed candidates
300 if cell_cands & ~allowed_mask:
301 continue
303 new_cands = sel_cands | cell_cands
304 cands_from_inter = new_cands & inter_cands
305 n_contained = _popcount(cands_from_inter)
306 cands_extra = new_cands & ~inter_cands
307 n_extra = _popcount(cands_extra)
308 new_level = level + 1
309 new_cells = sel_cells | (1 << idx)
311 # For block (second pass): need exactly n_plus intersection-cands covered
312 if n_contained > 0 and new_level - n_extra == n_plus:
313 # It's a Sue de Coq! Check for eliminations.
314 step = self._build_step(
315 grid, inter_cells, inter_cands,
316 nb_cells, nb_cands,
317 new_cells, new_cands,
318 blk_elim_region,
319 )
320 if step is not None:
321 if only_one:
322 return step
323 if results is not None:
324 results.append(step)
326 # Try larger subsets: continue even at exact match because adding
327 # a cell with extra candidates keeps coverage constant (Java always
328 # goes deeper, pruning only via allowed_mask).
329 if new_level - n_extra <= n_plus:
330 step = self._enum_blk_subsets(
331 grid, source, i + 1, new_level, new_cells, new_cands,
332 allowed_mask, inter_cells, inter_cands, n_plus,
333 nb_cells, nb_cands, blk_elim_region,
334 only_one, results,
335 )
336 if only_one and step is not None:
337 return step
338 return None
340 def _build_step(
341 self,
342 grid: Grid,
343 inter_cells: int,
344 inter_cands: int,
345 nb_cells: int,
346 nb_cands: int,
347 blk_cells: int,
348 blk_cands: int,
349 blk_elim_region: int,
350 ) -> SolutionStep | None:
351 """Build a SolutionStep if any eliminations exist.
353 Elimination rules (matching Java):
354 - In block cells (block - intersection - blockActSet):
355 eliminate ((inter_cands | blk_cands) & ~nb_cands) | shared_extra
356 - In row/col cells (row/col - intersection - nbActSet):
357 eliminate ((inter_cands | nb_cands) & ~blk_cands) | shared_extra
359 shared_extra = extra candidates appearing in BOTH nb and block sets.
360 """
361 # Extra candidates shared between both sets
362 shared_extra = (nb_cands & blk_cands) & ~inter_cands
364 elims: list[Candidate] = []
366 # Block eliminations: cells in block not part of SDC
367 blk_check = blk_elim_region & ~blk_cells
368 if blk_check:
369 blk_elim_cands = ((inter_cands | blk_cands) & ~nb_cands) | shared_extra
370 if blk_elim_cands:
371 for idx in _iter_bits(blk_check):
372 hit = grid.candidates[idx] & blk_elim_cands
373 for d in _iter_bits(hit):
374 elims.append(Candidate(idx, d + 1))
376 # Row/col eliminations: cells in row/col not part of SDC
377 # The non-block region for eliminations is all non-block cells minus
378 # intersection minus nb selection. We reconstruct it from the line.
379 # Actually, we can get non_block_all from the caller... let me
380 # use a trick: nb_cells are in the row/col, inter_cells are in both,
381 # and blk_cells are in the block. The row/col elim region is:
382 # (all row/col empty cells) - intersection - nb_cells
383 # We don't have non_block_all here directly. But we can compute the
384 # row/col from inter_cells and nb_cells: they share the same row/col.
385 # Let me instead pass non_block_all through... Actually, let me
386 # restructure: pass non_block_all to _build_step.
387 #
388 # For now, compute from the grid: find which row/col contains inter_cells.
389 # All inter cells share a row and a col; check which is the line.
390 first_inter = (inter_cells & -inter_cells).bit_length() - 1
391 row = first_inter // 9
392 col = first_inter % 9
393 # Check if all inter cells are in the same row
394 if inter_cells & LINE_MASKS[row] == inter_cells:
395 nb_all = LINE_MASKS[row]
396 else:
397 nb_all = COL_MASKS[col]
398 # Only empty cells
399 nb_empty = 0
400 for idx in _iter_bits(nb_all):
401 if grid.values[idx] == 0:
402 nb_empty |= 1 << idx
403 nb_check = nb_empty & ~inter_cells & ~nb_cells
404 if nb_check:
405 nb_elim_cands = ((inter_cands | nb_cands) & ~blk_cands) | shared_extra
406 if nb_elim_cands:
407 for idx in _iter_bits(nb_check):
408 hit = grid.candidates[idx] & nb_elim_cands
409 for d in _iter_bits(hit):
410 elims.append(Candidate(idx, d + 1))
412 if not elims:
413 return None
415 step = SolutionStep(SolutionType.SUE_DE_COQ)
416 step.candidates_to_delete = elims
417 # Store intersection cells and candidates in indices/values
418 for idx in _iter_bits(inter_cells):
419 step.add_index(idx)
420 for d in _iter_bits(inter_cands):
421 step.add_value(d + 1)
422 return step