Coverage for src / hodoku / solver / wings.py: 97%
255 statements
« prev ^ index » next coverage.py v7.13.5, created at 2026-04-21 08:35 +0000
1"""Wing pattern solver: W-Wing, XY-Wing, XYZ-Wing.
3Mirrors Java's WingSolver.
4"""
6from __future__ import annotations
8from hodoku.core.grid import BUDDIES, Grid
9from hodoku.core.solution_step import Candidate, SolutionStep
10from hodoku.core.types import SolutionType
13class WingSolver:
14 """W-Wing, XY-Wing, XYZ-Wing."""
16 def __init__(self, grid: Grid) -> None:
17 self.grid = grid
19 def get_step(self, sol_type: SolutionType) -> SolutionStep | None:
20 if sol_type == SolutionType.W_WING:
21 return self._find_w_wing()
22 if sol_type == SolutionType.XY_WING:
23 return self._find_xy_wing()
24 if sol_type == SolutionType.XYZ_WING:
25 return self._find_xyz_wing()
26 return None
28 def find_all(self, sol_type: SolutionType) -> list[SolutionStep]:
29 if sol_type == SolutionType.W_WING:
30 return self._find_w_wing_all()
31 if sol_type == SolutionType.XY_WING:
32 return self._find_wing_all(xyz=False)
33 if sol_type == SolutionType.XYZ_WING:
34 return self._find_wing_all(xyz=True)
35 return []
37 def _find_wing_all(self, xyz: bool) -> list[SolutionStep]:
38 grid = self.grid
39 bi_cells: list[int] = []
40 tri_cells: list[int] = []
41 for i in range(81):
42 if grid.values[i] != 0:
43 continue
44 n = bin(grid.candidates[i]).count("1")
45 if n == 2:
46 bi_cells.append(i)
47 elif xyz and n == 3:
48 tri_cells.append(i)
50 pivot_list = tri_cells if xyz else bi_cells
51 results: list[SolutionStep] = []
52 seen_elims: set[tuple] = set()
54 for pi, pivot in enumerate(pivot_list):
55 pivot_mask = grid.candidates[pivot]
56 for ji, j_cell in enumerate(bi_cells):
57 if xyz and j_cell == pivot:
58 continue
59 if not xyz and ji <= pi:
60 continue
61 j_mask = grid.candidates[j_cell]
62 if bin(pivot_mask | j_mask).count("1") != 3:
63 continue
64 k_start = ji + 1
65 for k_cell in bi_cells[k_start:]:
66 if k_cell == pivot:
67 continue
68 k_mask = grid.candidates[k_cell]
69 if bin(pivot_mask | j_mask | k_mask).count("1") != 3:
70 continue
71 if pivot_mask == j_mask or j_mask == k_mask or k_mask == pivot_mask:
72 continue
74 candidates_for_pivot = [(pivot, j_cell, k_cell)]
75 if not xyz:
76 candidates_for_pivot += [
77 (j_cell, pivot, k_cell),
78 (k_cell, j_cell, pivot),
79 ]
81 for idx1, idx2, idx3 in candidates_for_pivot:
82 step = self._check_wing(idx1, idx2, idx3, xyz)
83 if step:
84 key = tuple(sorted(
85 (c.index, c.value) for c in step.candidates_to_delete
86 ))
87 if key not in seen_elims:
88 seen_elims.add(key)
89 results.append(step)
90 return results
92 def _find_w_wing_all(self) -> list[SolutionStep]:
93 grid = self.grid
94 bi_cells: list[int] = []
95 for i in range(81):
96 if grid.values[i] == 0 and bin(grid.candidates[i]).count("1") == 2:
97 bi_cells.append(i)
99 results: list[SolutionStep] = []
100 seen_elims: set[tuple] = set()
102 for ii, i in enumerate(bi_cells):
103 cell_i = grid.candidates[i]
104 bits = [b + 1 for b in range(9) if cell_i >> b & 1]
105 cand_a, cand_b = bits[0], bits[1]
106 peers_a = grid.candidate_sets[cand_a] & BUDDIES[i]
107 peers_b = grid.candidate_sets[cand_b] & BUDDIES[i]
109 for j in bi_cells[ii + 1:]:
110 if grid.candidates[j] != cell_i:
111 continue
113 elim_a = peers_a & BUDDIES[j]
114 if elim_a:
115 step = self._check_w_link(cand_a, cand_b, i, j, elim_a)
116 if step:
117 key = tuple(sorted(
118 (c.index, c.value) for c in step.candidates_to_delete
119 ))
120 if key not in seen_elims:
121 seen_elims.add(key)
122 results.append(step)
124 elim_b = peers_b & BUDDIES[j]
125 if elim_b:
126 step = self._check_w_link(cand_b, cand_a, i, j, elim_b)
127 if step:
128 key = tuple(sorted(
129 (c.index, c.value) for c in step.candidates_to_delete
130 ))
131 if key not in seen_elims:
132 seen_elims.add(key)
133 results.append(step)
135 return results
137 # ------------------------------------------------------------------
138 # XY-Wing / XYZ-Wing shared logic
139 # ------------------------------------------------------------------
141 def _find_xy_wing(self) -> SolutionStep | None:
142 return self._find_wing(xyz=False)
144 def _find_xyz_wing(self) -> SolutionStep | None:
145 return self._find_wing(xyz=True)
147 def _find_wing(self, xyz: bool) -> SolutionStep | None:
148 """Search for XY-Wing (xyz=False) or XYZ-Wing (xyz=True).
150 Logic mirrors WingSolver.getWing():
151 - Collect bivalue cells (candidate count == 2) and optionally trivalue.
152 - For XY-Wing: try each bivalue cell as pivot, two others as pincers.
153 - For XYZ-Wing: try each trivalue cell as pivot, two bivalue pincers.
154 - All three cells together must span exactly 3 distinct candidates.
155 - Pivot must see both pincers.
156 - Pincers share exactly one candidate z.
157 - Eliminate z from cells that see both pincers (and pivot for XYZ).
158 """
159 grid = self.grid
160 bi_cells: list[int] = []
161 tri_cells: list[int] = []
162 for i in range(81):
163 if grid.values[i] != 0:
164 continue
165 n = bin(grid.candidates[i]).count("1")
166 if n == 2:
167 bi_cells.append(i)
168 elif xyz and n == 3:
169 tri_cells.append(i)
171 pivot_list = tri_cells if xyz else bi_cells
173 for pi, pivot in enumerate(pivot_list):
174 pivot_mask = grid.candidates[pivot]
175 for ji, j_cell in enumerate(bi_cells):
176 if xyz and j_cell == pivot:
177 continue
178 if not xyz and ji <= pi:
179 continue # avoid duplicate (pivot, j) pairs for XY
180 j_mask = grid.candidates[j_cell]
181 if bin(pivot_mask | j_mask).count("1") != 3:
182 continue # can't form a 3-candidate wing
183 k_start = ji + 1
184 for k_cell in bi_cells[k_start:]:
185 if k_cell == pivot:
186 continue
187 k_mask = grid.candidates[k_cell]
188 if bin(pivot_mask | j_mask | k_mask).count("1") != 3:
189 continue
190 # No two cells may have identical candidate sets
191 if pivot_mask == j_mask or j_mask == k_mask or k_mask == pivot_mask:
192 continue
194 # For XY-Wing, try all 3 rotations (each cell as pivot)
195 candidates_for_pivot = [(pivot, j_cell, k_cell)]
196 if not xyz:
197 candidates_for_pivot += [
198 (j_cell, pivot, k_cell),
199 (k_cell, j_cell, pivot),
200 ]
202 for idx1, idx2, idx3 in candidates_for_pivot:
203 step = self._check_wing(idx1, idx2, idx3, xyz)
204 if step:
205 return step
206 return None
208 def _check_wing(
209 self, pivot: int, pincer1: int, pincer2: int, xyz: bool
210 ) -> SolutionStep | None:
211 """Check if (pivot, pincer1, pincer2) form a valid wing and return step."""
212 grid = self.grid
213 # Pivot must see both pincers
214 if not (BUDDIES[pivot] >> pincer1 & 1) or not (BUDDIES[pivot] >> pincer2 & 1):
215 return None
217 p1_mask = grid.candidates[pincer1]
218 p2_mask = grid.candidates[pincer2]
219 shared = p1_mask & p2_mask
220 if bin(shared).count("1") != 1:
221 return None # pincers must share exactly one candidate z
223 cand_z = shared.bit_length() # digit (1-9)
225 # Cells to eliminate from: see both pincers (and pivot for XYZ)
226 elim_set = grid.candidate_sets[cand_z] & BUDDIES[pincer1] & BUDDIES[pincer2]
227 if xyz:
228 elim_set &= BUDDIES[pivot]
229 # Remove the wing cells themselves
230 elim_set &= ~((1 << pivot) | (1 << pincer1) | (1 << pincer2))
231 if not elim_set:
232 return None
234 sol_type = SolutionType.XYZ_WING if xyz else SolutionType.XY_WING
235 step = SolutionStep(sol_type)
237 pivot_mask = grid.candidates[pivot]
238 # Values stored: the three candidates of the pivot cell
239 for bit in range(1, 10):
240 if pivot_mask >> (bit - 1) & 1:
241 step.add_value(bit)
242 if not xyz:
243 # XY-Wing: add Z digit as third value (HoDoKu convention)
244 step.add_value(cand_z)
246 step.add_index(pivot)
247 step.add_index(pincer1)
248 step.add_index(pincer2)
250 # Fins: pincers carry z; pivot also carries z for XYZ
251 if xyz:
252 step.fins.append(Candidate(pivot, cand_z))
253 step.fins.append(Candidate(pincer1, cand_z))
254 step.fins.append(Candidate(pincer2, cand_z))
256 tmp = elim_set
257 while tmp:
258 lsb = tmp & -tmp
259 step.add_candidate_to_delete(lsb.bit_length() - 1, cand_z)
260 tmp ^= lsb
261 return step
263 # ------------------------------------------------------------------
264 # W-Wing
265 # ------------------------------------------------------------------
267 def _find_w_wing(self) -> SolutionStep | None:
268 """Find the first W-Wing elimination.
270 Two bivalue cells with identical candidates {a, b}.
271 A strong link on b connects them (one end sees cell1, the other sees cell2).
272 Eliminate a from all cells that see both bivalue cells.
273 """
274 grid = self.grid
275 bi_cells: list[int] = []
276 for i in range(81):
277 if grid.values[i] == 0 and bin(grid.candidates[i]).count("1") == 2:
278 bi_cells.append(i)
280 for ii, i in enumerate(bi_cells):
281 cell_i = grid.candidates[i]
282 # Extract the two digits from the bitmask
283 bits = [b + 1 for b in range(9) if cell_i >> b & 1]
284 cand_a, cand_b = bits[0], bits[1]
286 # Pre-compute peers of i that carry cand_a / cand_b
287 peers_a = grid.candidate_sets[cand_a] & BUDDIES[i]
288 peers_b = grid.candidate_sets[cand_b] & BUDDIES[i]
290 for j in bi_cells[ii + 1:]:
291 if grid.candidates[j] != cell_i:
292 continue # must have identical candidate sets
294 # Potential eliminations of cand_a: cells seeing both i and j
295 elim_a = peers_a & BUDDIES[j]
296 if elim_a:
297 step = self._check_w_link(cand_a, cand_b, i, j, elim_a)
298 if step:
299 return step
301 # Potential eliminations of cand_b: cells seeing both i and j
302 elim_b = peers_b & BUDDIES[j]
303 if elim_b:
304 step = self._check_w_link(cand_b, cand_a, i, j, elim_b)
305 if step:
306 return step
308 return None
310 def _check_w_link(
311 self,
312 cand_elim: int,
313 cand_link: int,
314 idx1: int,
315 idx2: int,
316 elim_set: int,
317 ) -> SolutionStep | None:
318 """Find a strong link on cand_link that bridges idx1 and idx2.
320 The strong link must have one end seeing idx1 and the other seeing idx2.
321 A single end cannot see BOTH idx1 and idx2 (forbidden by HoDoKu).
322 """
323 grid = self.grid
324 # Scan all 27 constraints for a strong link on cand_link
325 for constr in range(27):
326 if grid.free[constr][cand_link] != 2:
327 continue
328 # Find the two cells in this unit with cand_link
329 link_cells: list[int] = []
330 for cell in self._unit_cells(constr):
331 if cell != idx1 and cell != idx2 and grid.candidate_sets[cand_link] >> cell & 1:
332 link_cells.append(cell)
333 if len(link_cells) == 2:
334 break
335 if len(link_cells) != 2:
336 continue
338 w1, w2 = link_cells
339 # One must see idx1, the other idx2; neither may see BOTH
340 w1_sees1 = bool(BUDDIES[w1] >> idx1 & 1)
341 w1_sees2 = bool(BUDDIES[w1] >> idx2 & 1)
342 w2_sees1 = bool(BUDDIES[w2] >> idx1 & 1)
343 w2_sees2 = bool(BUDDIES[w2] >> idx2 & 1)
345 if w1_sees1 and w1_sees2:
346 continue # forbidden
347 if w2_sees1 and w2_sees2:
348 continue # forbidden
350 if w1_sees1 and w2_sees2:
351 pass # w1→idx1, w2→idx2
352 elif w1_sees2 and w2_sees1:
353 w1, w2 = w2, w1 # swap so w1→idx1
354 else:
355 continue # no valid bridge
357 # Valid W-Wing!
358 step = SolutionStep(SolutionType.W_WING)
359 step.add_value(cand_elim)
360 step.add_value(cand_link)
361 step.add_index(idx1)
362 step.add_index(idx2)
363 step.fins.append(Candidate(idx1, cand_link))
364 step.fins.append(Candidate(idx2, cand_link))
365 step.fins.append(Candidate(w1, cand_link))
366 step.fins.append(Candidate(w2, cand_link))
368 tmp = elim_set
369 while tmp:
370 lsb = tmp & -tmp
371 step.add_candidate_to_delete(lsb.bit_length() - 1, cand_elim)
372 tmp ^= lsb
373 return step
375 return None
377 # ------------------------------------------------------------------
378 # Helper
379 # ------------------------------------------------------------------
381 def _unit_cells(self, constr: int) -> list[int]:
382 """Return all cell indices in constraint unit constr (0-26)."""
383 from hodoku.core.grid import ALL_UNITS # avoid circular at module level
384 return list(ALL_UNITS[constr])