Coverage for src / hodoku / solver / fish.py: 99%

1"""Fish solver: basic, finned/sashimi, Franken, and Mutant variants. 

2 

3Mirrors Java's FishSolver. Basic and finned/sashimi were already implemented; 

4Franken and Mutant extend the unit pool to include boxes as base/cover sets. 

5 

6Fish category classification (mirrors Java's createFishStep logic): 

7 BASIC — base = rows only, cover = cols only (or vice versa) 

8 FRANKEN — base ⊆ {rows, blocks}, cover ⊆ {cols, blocks} (or vice versa) 

9 MUTANT — any other combination (rows and cols appear on the same side) 

10 

11Unit pools for initForCandidat (fishType, lines=True): 

12 BASIC: base = rows, cover = cols 

13 FRANKEN: base = rows + blocks, cover = cols + blocks 

14 MUTANT: base = all 27 units, cover = all 27 units (one orientation) 

15 

16Endo fins: cells that appear in two or more base units (possible when blocks 

17overlap rows/cols). At most MAX_ENDO_FINS=2 endo fins are allowed. 

18Endo fins that are not covered appear in the regular fins mask and are 

19handled identically to external fins when computing eliminations. 

20""" 

21 

22from __future__ import annotations 

23 

24import os 

25from itertools import combinations 

26from typing import TYPE_CHECKING 

27 

28from hodoku.core.grid import ( 

29 ALL_UNIT_MASKS, 

30 BUDDIES, 

31 COL_MASKS, 

32 Grid, 

33 LINE_MASKS, 

34) 

35 

36if TYPE_CHECKING: 

37 from hodoku.config import StepSearchConfig 

38 

39# All 81 cells mask 

40_ALL_CELLS = (1 << 81) - 1 

41 

42# ---- C accelerator for cover search (optional, huge speedup) ---- 

43 

44try: 

45 if os.environ.get("HODOKU_NO_ACCEL"): 

46 raise ImportError("disabled by HODOKU_NO_ACCEL") 

47 from hodoku.solver import _fish_accel as _accel 

48 _accel.set_buddies(list(BUDDIES)) 

49except ImportError: 

50 _accel = None 

51 

52 

53def _fin_buddies(fin_mask: int) -> int: 

54 """Return the intersection of buddies of all fin cells. 

55 

56 A cell is in the result iff it can see every fin cell simultaneously. 

57 """ 

58 common = _ALL_CELLS 

59 tmp = fin_mask 

60 while tmp: 

61 lsb = tmp & -tmp 

62 common &= BUDDIES[lsb.bit_length() - 1] 

63 tmp ^= lsb 

64 return common 

65 

66 

67from hodoku.core.solution_step import Entity, SolutionStep # noqa: E402 

68from hodoku.core.types import SolutionType # noqa: E402 

69 

70# Entity type constants (mirror Java's Sudoku2.LINE / COL / BLOCK) 

71_LINE = 0 

72_COL = 1 

73 

74# Size for each basic fish type 

75_FISH_SIZE = { 

76 SolutionType.X_WING: 2, 

77 SolutionType.SWORDFISH: 3, 

78 SolutionType.JELLYFISH: 4, 

79} 

80 

81# Finned and Sashimi types with their size 

82_FINNED_SIZE = { 

83 SolutionType.FINNED_X_WING: 2, 

84 SolutionType.FINNED_SWORDFISH: 3, 

85 SolutionType.FINNED_JELLYFISH: 4, 

86} 

87 

88_SASHIMI_SIZE = { 

89 SolutionType.SASHIMI_X_WING: 2, 

90 SolutionType.SASHIMI_SWORDFISH: 3, 

91 SolutionType.SASHIMI_JELLYFISH: 4, 

92} 

93 

94# Map finned → sashimi counterpart (same size, different classification) 

95_FINNED_TO_SASHIMI = { 

96 SolutionType.FINNED_X_WING: SolutionType.SASHIMI_X_WING, 

97 SolutionType.FINNED_SWORDFISH: SolutionType.SASHIMI_SWORDFISH, 

98 SolutionType.FINNED_JELLYFISH: SolutionType.SASHIMI_JELLYFISH, 

99} 

100 

101# --------------------------------------------------------------------------- 

102# Franken / Mutant fish 

103# --------------------------------------------------------------------------- 

104 

105# Fish category constants (mirror Java FishSolver BASIC/FRANKEN/MUTANT) 

106_CAT_BASIC = 0 

107_CAT_FRANKEN = 1 

108_CAT_MUTANT = 2 

109 

110# Unit type bit-flags (for category classification) 

111_BIT_LINE = 1 

112_BIT_COL = 2 

113_BIT_BLOCK = 4 

114 

115# HoDoKu defaults for fin/endo-fin limits 

116_MAX_FINS = 5 

117_MAX_ENDO_FINS = 2 

118 

119# Entity type constants for boxes (Java's Sudoku2.BLOCK = 0) 

120_BLOCK = 2 

121 

122# Entity type constants (reuse existing _LINE=0, _COL=1, new _BLOCK_ENT=2) 

123_BLOCK_ENT = 2 

124 

125# SolutionType → (category, size, with_fins) 

126_GENERALIZED_INFO: dict[SolutionType, tuple[int, int, bool]] = { 

127 # Franken (basic / no fins) 

128 SolutionType.FRANKEN_X_WING: (_CAT_FRANKEN, 2, False), 

129 SolutionType.FRANKEN_SWORDFISH: (_CAT_FRANKEN, 3, False), 

130 SolutionType.FRANKEN_JELLYFISH: (_CAT_FRANKEN, 4, False), 

131 # Franken (finned) 

132 SolutionType.FINNED_FRANKEN_X_WING: (_CAT_FRANKEN, 2, True), 

133 SolutionType.FINNED_FRANKEN_SWORDFISH: (_CAT_FRANKEN, 3, True), 

134 SolutionType.FINNED_FRANKEN_JELLYFISH: (_CAT_FRANKEN, 4, True), 

135 # Mutant (basic / no fins) 

136 SolutionType.MUTANT_X_WING: (_CAT_MUTANT, 2, False), 

137 SolutionType.MUTANT_SWORDFISH: (_CAT_MUTANT, 3, False), 

138 SolutionType.MUTANT_JELLYFISH: (_CAT_MUTANT, 4, False), 

139 # Mutant (finned) 

140 SolutionType.FINNED_MUTANT_X_WING: (_CAT_MUTANT, 2, True), 

141 SolutionType.FINNED_MUTANT_SWORDFISH: (_CAT_MUTANT, 3, True), 

142 SolutionType.FINNED_MUTANT_JELLYFISH: (_CAT_MUTANT, 4, True), 

143 SolutionType.FINNED_MUTANT_SQUIRMBAG: (_CAT_MUTANT, 5, True), 

144 SolutionType.FINNED_MUTANT_WHALE: (_CAT_MUTANT, 6, True), 

145 SolutionType.FINNED_MUTANT_LEVIATHAN: (_CAT_MUTANT, 7, True), 

146} 

147 

148# (category, size, with_fins) → basic SolutionType (for step annotation when no fins) 

149_CAT_BASIC_TYPES: dict[tuple[int, int], SolutionType] = { 

150 (_CAT_FRANKEN, 2): SolutionType.FRANKEN_X_WING, 

151 (_CAT_FRANKEN, 3): SolutionType.FRANKEN_SWORDFISH, 

152 (_CAT_FRANKEN, 4): SolutionType.FRANKEN_JELLYFISH, 

153 (_CAT_MUTANT, 2): SolutionType.MUTANT_X_WING, 

154 (_CAT_MUTANT, 3): SolutionType.MUTANT_SWORDFISH, 

155 (_CAT_MUTANT, 4): SolutionType.MUTANT_JELLYFISH, 

156} 

157 

158# (category, size) → finned SolutionType 

159_CAT_FINNED_TYPES: dict[tuple[int, int], SolutionType] = { 

160 (_CAT_FRANKEN, 2): SolutionType.FINNED_FRANKEN_X_WING, 

161 (_CAT_FRANKEN, 3): SolutionType.FINNED_FRANKEN_SWORDFISH, 

162 (_CAT_FRANKEN, 4): SolutionType.FINNED_FRANKEN_JELLYFISH, 

163 (_CAT_MUTANT, 2): SolutionType.FINNED_MUTANT_X_WING, 

164 (_CAT_MUTANT, 3): SolutionType.FINNED_MUTANT_SWORDFISH, 

165 (_CAT_MUTANT, 4): SolutionType.FINNED_MUTANT_JELLYFISH, 

166 (_CAT_MUTANT, 5): SolutionType.FINNED_MUTANT_SQUIRMBAG, 

167 (_CAT_MUTANT, 6): SolutionType.FINNED_MUTANT_WHALE, 

168 (_CAT_MUTANT, 7): SolutionType.FINNED_MUTANT_LEVIATHAN, 

169} 

170 

171 

172def _classify_fish(base_type_bits: int, cover_type_bits: int) -> int: 

173 """Classify a fish as BASIC/FRANKEN/MUTANT based on unit type bits. 

174 

175 Mirrors Java FishSolver.createFishStep type-determination logic. 

176 LINE_MASK=1, COL_MASK=2, BLOCK_MASK=4 in Java. 

177 """ 

178 if ((base_type_bits == _BIT_LINE and cover_type_bits == _BIT_COL) or 

179 (base_type_bits == _BIT_COL and cover_type_bits == _BIT_LINE)): 

180 return _CAT_BASIC 

181 # Franken: base ⊆ {LINE,BLOCK} and cover ⊆ {COL,BLOCK}, or vice versa 

182 if (((base_type_bits & ~(_BIT_LINE | _BIT_BLOCK)) == 0 and 

183 (cover_type_bits & ~(_BIT_COL | _BIT_BLOCK)) == 0) or # noqa: E127 

184 ((base_type_bits & ~(_BIT_COL | _BIT_BLOCK)) == 0 and 

185 (cover_type_bits & ~(_BIT_LINE | _BIT_BLOCK)) == 0)): 

186 return _CAT_FRANKEN 

187 return _CAT_MUTANT 

188 

189 

190def _unit_type_bit(unit_idx: int) -> int: 

191 """Return the type bit for a unit index (0-8=row, 9-17=col, 18-26=block).""" 

192 if unit_idx < 9: 

193 return _BIT_LINE 

194 if unit_idx < 18: 

195 return _BIT_COL 

196 return _BIT_BLOCK 

197 

198 

199def _build_unit_pools( 

200 cand_set: int, 

201 fish_cat: int, 

202 lines: bool, 

203 n: int, 

204 with_fins: bool, 

205) -> tuple[list[tuple[int, int]], list[tuple[int, int]]]: 

206 """Build (base_pool, cover_pool) for a generalized fish search. 

207 

208 Each pool entry is (unit_cands, unit_index) where unit_index is 0-26 

209 (0-8=rows, 9-17=cols, 18-26=blocks). 

210 

211 Mirrors Java FishSolver.initForCandidat(). 

212 """ 

213 base_pool: list[tuple[int, int]] = [] 

214 cover_pool: list[tuple[int, int]] = [] 

215 

216 for i in range(27): 

217 if fish_cat == _CAT_BASIC and i >= 18: 

218 continue 

219 unit_cands = cand_set & ALL_UNIT_MASKS[i] 

220 if not unit_cands: 

221 continue 

222 

223 if i < 9: # row 

224 if lines or fish_cat == _CAT_MUTANT: 

225 # row → base (with size filter), and cover if MUTANT 

226 if with_fins or unit_cands.bit_count() <= n: 

227 base_pool.append((unit_cands, i)) 

228 if fish_cat == _CAT_MUTANT: 

229 cover_pool.append((unit_cands, i)) 

230 else: 

231 # row → cover only (non-MUTANT, lines=False) 

232 cover_pool.append((unit_cands, i)) 

233 elif i < 18: # col 

234 if lines or fish_cat == _CAT_MUTANT: 

235 # col → cover, and base if MUTANT 

236 cover_pool.append((unit_cands, i)) 

237 if fish_cat == _CAT_MUTANT: 

238 if with_fins or unit_cands.bit_count() <= n: 

239 base_pool.append((unit_cands, i)) 

240 else: 

241 # col → base (with size filter), and cover if MUTANT 

242 if with_fins or unit_cands.bit_count() <= n: 

243 base_pool.append((unit_cands, i)) 

244 if fish_cat == _CAT_MUTANT: 

245 cover_pool.append((unit_cands, i)) 

246 else: # block (i >= 18) 

247 if fish_cat != _CAT_BASIC: 

248 cover_pool.append((unit_cands, i)) 

249 if with_fins or unit_cands.bit_count() <= n: 

250 base_pool.append((unit_cands, i)) 

251 

252 return base_pool, cover_pool 

253 

254 

255def _apply_siamese(steps: list[SolutionStep]) -> None: 

256 """Append siamese combinations to *steps* (modifies in place). 

257 

258 Two finned/sashimi fish are siamese when they share the same base 

259 entities (same candidate, same rows/cols) but differ in their fin 

260 configuration and eliminations. HoDoKu merges them into a single 

261 step with the combined cover + fin + elimination sets. 

262 """ 

263 n = len(steps) 

264 for i in range(n - 1): 

265 s1 = steps[i] 

266 if not s1.base_entities: 

267 continue 

268 # Entity is a frozen dataclass with fields .type and .number 

269 base_key1 = tuple((e.type, e.number) for e in s1.base_entities) 

270 cand1 = s1.values[0] if s1.values else None 

271 elim1 = frozenset((c.index, c.value) for c in s1.candidates_to_delete) 

272 for j in range(i + 1, n): 

273 s2 = steps[j] 

274 if not s2.base_entities: 

275 continue 

276 if (s2.values[0] if s2.values else None) != cand1: 

277 continue 

278 base_key2 = tuple((e.type, e.number) for e in s2.base_entities) 

279 if base_key1 != base_key2: 

280 continue 

281 elim2 = frozenset((c.index, c.value) for c in s2.candidates_to_delete) 

282 if elim1 == elim2: 

283 continue 

284 # Build siamese step: clone s1, add s2's covers/fins/elims 

285 # Entity and Candidate are frozen dataclasses — safe to share refs 

286 siam = SolutionStep(s1.type) 

287 siam.add_value(cand1) 

288 for idx in s1.indices: 

289 siam.add_index(idx) 

290 siam.base_entities.extend(s1.base_entities) 

291 siam.cover_entities.extend(s1.cover_entities) 

292 siam.fins.extend(s1.fins) 

293 for c in s1.candidates_to_delete: 

294 siam.add_candidate_to_delete(c.index, c.value) 

295 # Add s2's additional covers, fins, elims 

296 siam.cover_entities.extend(s2.cover_entities) 

297 siam.fins.extend(s2.fins) 

298 for c in s2.candidates_to_delete: 

299 if (c.index, c.value) not in elim1: 

300 siam.add_candidate_to_delete(c.index, c.value) 

301 steps.append(siam) 

302 

303 

304class FishSolver: 

305 """X-Wing, Swordfish, Jellyfish — basic, finned/sashimi, Franken, Mutant.""" 

306 

307 def __init__(self, grid: Grid, search_config: StepSearchConfig | None = None) -> None: 

308 self.grid = grid 

309 if search_config is not None: 

310 self._max_fins = search_config.fish.max_fins 

311 self._max_endo_fins = search_config.fish.max_endo_fins 

312 self._allow_duals_and_siamese = search_config.allow_duals_and_siamese 

313 else: 

314 # Backward-compatible defaults (pre-config behavior) 

315 self._max_fins = _MAX_FINS 

316 self._max_endo_fins = _MAX_ENDO_FINS 

317 self._allow_duals_and_siamese = True 

318 

319 def get_step(self, sol_type: SolutionType) -> SolutionStep | None: 

320 if sol_type in _FISH_SIZE: 

321 return self._find_basic_fish(sol_type) 

322 if sol_type in _FINNED_SIZE: 

323 return self._find_finned_fish(sol_type, sashimi=False) 

324 if sol_type in _SASHIMI_SIZE: 

325 return self._find_finned_fish(sol_type, sashimi=True) 

326 if sol_type in _GENERALIZED_INFO: 

327 steps = self._find_generalized_fish_all(sol_type) 

328 # NOTE: Java calls Collections.sort(steps) here using 

329 # SolutionStep.compareTo(). We rely on iteration order matching 

330 # instead. If a parity divergence traces to generalized fish 

331 # step selection, add a sort here (see getCandidateString() sort 

332 # side-effect documented in chains.py _elim_sort_key). 

333 return steps[0] if steps else None 

334 return None 

335 

336 def find_all(self, sol_type: SolutionType, *, for_candidate: int = -1) -> list[SolutionStep]: 

337 if sol_type in _FISH_SIZE: 

338 return self._find_basic_fish_all(sol_type) 

339 if sol_type in _FINNED_SIZE: 

340 n = _FINNED_SIZE[sol_type] 

341 steps = self._find_finned_fish_all(sol_type, sashimi=False) 

342 if n >= 3: 

343 # HoDoKu finds finned+sashimi together for siamese combinations 

344 sashimi_type = _FINNED_TO_SASHIMI[sol_type] 

345 steps = steps + self._find_finned_fish_all(sashimi_type, sashimi=True) 

346 if self._allow_duals_and_siamese: 

347 _apply_siamese(steps) 

348 return steps 

349 if sol_type in _SASHIMI_SIZE: 

350 n = _SASHIMI_SIZE[sol_type] 

351 sashimi_steps = self._find_finned_fish_all(sol_type, sashimi=True) 

352 if n >= 3: 

353 finned_type = {v: k for k, v in _FINNED_TO_SASHIMI.items()}[sol_type] 

354 steps = self._find_finned_fish_all(finned_type, sashimi=False) + sashimi_steps 

355 if self._allow_duals_and_siamese: 

356 _apply_siamese(steps) 

357 return steps 

358 return sashimi_steps 

359 if sol_type in _GENERALIZED_INFO: 

360 steps = self._find_generalized_fish_all(sol_type, for_candidate=for_candidate) 

361 if self._allow_duals_and_siamese: 

362 _apply_siamese(steps) 

363 return steps 

364 return [] 

365 

366 def _find_basic_fish_all(self, sol_type: SolutionType) -> list[SolutionStep]: 

367 """Return ALL basic fish of the given size.""" 

368 n = _FISH_SIZE[sol_type] 

369 grid = self.grid 

370 results: list[SolutionStep] = [] 

371 seen_elims: set[tuple] = set() 

372 

373 for cand in range(1, 10): 

374 cand_set = grid.candidate_sets[cand] 

375 if not cand_set: 

376 continue 

377 

378 for row_mode in (True, False): 

379 unit_masks = LINE_MASKS if row_mode else COL_MASKS 

380 cover_masks = COL_MASKS if row_mode else LINE_MASKS 

381 

382 eligible: list[int] = [] 

383 for u in range(9): 

384 cnt = (cand_set & unit_masks[u]).bit_count() 

385 if 2 <= cnt <= n: 

386 eligible.append(u) 

387 

388 if len(eligible) < n: 

389 continue 

390 

391 for combo in combinations(eligible, n): 

392 base_mask = 0 

393 for u in combo: 

394 base_mask |= cand_set & unit_masks[u] 

395 

396 cover_indices: list[int] = [] 

397 for ci in range(9): 

398 if base_mask & cover_masks[ci]: 

399 cover_indices.append(ci) 

400 

401 if len(cover_indices) != n: 

402 continue 

403 

404 cover_mask = 0 

405 for ci in cover_indices: 

406 cover_mask |= cover_masks[ci] 

407 

408 elim_mask = cand_set & cover_mask & ~base_mask 

409 if not elim_mask: 

410 continue 

411 

412 elim_key = (cand, elim_mask) 

413 if elim_key in seen_elims: 

414 continue 

415 seen_elims.add(elim_key) 

416 

417 results.append(self._make_step( 

418 sol_type, cand, combo, cover_indices, 

419 base_mask, elim_mask, row_mode 

420 )) 

421 

422 return results 

423 

424 def _find_finned_fish_all( 

425 self, sol_type: SolutionType, sashimi: bool 

426 ) -> list[SolutionStep]: 

427 """Return ALL finned/sashimi fish of the given size.""" 

428 n = _SASHIMI_SIZE[sol_type] if sashimi else _FINNED_SIZE[sol_type] 

429 finned_type = sol_type if not sashimi else { 

430 v: k for k, v in _FINNED_TO_SASHIMI.items() 

431 }[sol_type] 

432 grid = self.grid 

433 results: list[SolutionStep] = [] 

434 seen_elims: set[tuple] = set() 

435 

436 for cand in range(1, 10): 

437 cand_set = grid.candidate_sets[cand] 

438 if not cand_set: 

439 continue 

440 

441 for row_mode in (True, False): 

442 unit_masks = LINE_MASKS if row_mode else COL_MASKS 

443 cover_masks = COL_MASKS if row_mode else LINE_MASKS 

444 

445 eligible: list[int] = [] 

446 for u in range(9): 

447 if cand_set & unit_masks[u]: 

448 eligible.append(u) 

449 

450 if len(eligible) < n: 

451 continue 

452 

453 for combo in combinations(eligible, n): 

454 base_mask = 0 

455 for u in combo: 

456 base_mask |= cand_set & unit_masks[u] 

457 

458 cover_indices: list[int] = [] 

459 for ci in range(9): 

460 if base_mask & cover_masks[ci]: 

461 cover_indices.append(ci) 

462 

463 if len(cover_indices) < n or len(cover_indices) > n + 3: 

464 continue 

465 

466 for cover_combo in combinations(cover_indices, n): 

467 cover_mask = 0 

468 for ci in cover_combo: 

469 cover_mask |= cover_masks[ci] 

470 

471 fin_mask = base_mask & ~cover_mask 

472 if not fin_mask: 

473 continue 

474 if fin_mask.bit_count() > 5: 

475 continue 

476 

477 fin_common = _fin_buddies(fin_mask) 

478 elim_mask = cand_set & cover_mask & fin_common & ~base_mask 

479 if not elim_mask: 

480 continue 

481 

482 is_sashimi = False 

483 for u in combo: 

484 body = cand_set & unit_masks[u] & cover_mask 

485 if body.bit_count() <= 1: 

486 is_sashimi = True 

487 break 

488 

489 if is_sashimi != sashimi: 

490 continue 

491 

492 actual_type = ( 

493 _FINNED_TO_SASHIMI[finned_type] 

494 if is_sashimi else finned_type 

495 ) 

496 

497 elim_key = (cand, row_mode, elim_mask, fin_mask) 

498 if elim_key in seen_elims: 

499 continue 

500 seen_elims.add(elim_key) 

501 

502 results.append(self._make_step( 

503 actual_type, cand, combo, list(cover_combo), 

504 base_mask, elim_mask, row_mode, 

505 fin_mask=fin_mask, 

506 )) 

507 

508 return results 

509 

510 # ------------------------------------------------------------------ 

511 # Core algorithm 

512 # ------------------------------------------------------------------ 

513 

514 def _find_basic_fish(self, sol_type: SolutionType) -> SolutionStep | None: 

515 """Search for a basic fish of the given size. 

516 

517 Row-mode: base = rows, cover = cols. 

518 Col-mode: base = cols, cover = rows. 

519 For each candidate digit, try all C(9, n) combinations of base units 

520 where the digit appears 2..n times. If those n base units span exactly 

521 n cover units, any candidates in the cover units outside the base can 

522 be eliminated. 

523 """ 

524 n = _FISH_SIZE[sol_type] 

525 grid = self.grid 

526 

527 for cand in range(1, 10): 

528 cand_set = grid.candidate_sets[cand] 

529 if not cand_set: 

530 continue 

531 

532 for row_mode in (True, False): 

533 unit_masks = LINE_MASKS if row_mode else COL_MASKS 

534 cover_masks = COL_MASKS if row_mode else LINE_MASKS 

535 

536 # Collect candidate base units (those with 2..n occurrences) 

537 eligible: list[int] = [] 

538 for u in range(9): 

539 cnt = (cand_set & unit_masks[u]).bit_count() 

540 if 2 <= cnt <= n: 

541 eligible.append(u) 

542 

543 if len(eligible) < n: 

544 continue 

545 

546 for combo in combinations(eligible, n): 

547 # Union of candidate cells across these n base units 

548 base_mask = 0 

549 for u in combo: 

550 base_mask |= cand_set & unit_masks[u] 

551 

552 # Which perpendicular units do these cells span? 

553 cover_indices: list[int] = [] 

554 for ci in range(9): 

555 if base_mask & cover_masks[ci]: 

556 cover_indices.append(ci) 

557 

558 if len(cover_indices) != n: 

559 continue # not a fish 

560 

561 # Elimination: candidates in cover units but not in base 

562 cover_mask = 0 

563 for ci in cover_indices: 

564 cover_mask |= cover_masks[ci] 

565 

566 elim_mask = cand_set & cover_mask & ~base_mask 

567 if not elim_mask: 

568 continue 

569 

570 return self._make_step( 

571 sol_type, cand, combo, cover_indices, 

572 base_mask, elim_mask, row_mode 

573 ) 

574 

575 return None 

576 

577 def _find_finned_fish( 

578 self, sol_type: SolutionType, sashimi: bool 

579 ) -> SolutionStep | None: 

580 """Search for a finned or sashimi fish of the given size. 

581 

582 A finned fish is like a basic fish but some base cells fall outside 

583 the n cover units — these are 'fins'. All fins must share one block. 

584 Eliminations: candidates in the cover units that are also in the fin 

585 block, but not in any base unit. 

586 

587 Sashimi: same pattern, but at least one base unit has all its cells 

588 as fins (it contributes nothing to the body). 

589 """ 

590 n = _SASHIMI_SIZE[sol_type] if sashimi else _FINNED_SIZE[sol_type] 

591 # The canonical type for step construction is the FINNED variant; 

592 # we decide finned vs sashimi per found fish. 

593 finned_type = sol_type if not sashimi else { 

594 v: k for k, v in _FINNED_TO_SASHIMI.items() 

595 }[sol_type] 

596 grid = self.grid 

597 

598 for cand in range(1, 10): 

599 cand_set = grid.candidate_sets[cand] 

600 if not cand_set: 

601 continue 

602 

603 for row_mode in (True, False): 

604 unit_masks = LINE_MASKS if row_mode else COL_MASKS 

605 cover_masks = COL_MASKS if row_mode else LINE_MASKS 

606 

607 # Eligible base units: any unit with ≥1 occurrence 

608 # (fins can make a unit appear to have too many cells) 

609 eligible: list[int] = [] 

610 for u in range(9): 

611 if cand_set & unit_masks[u]: 

612 eligible.append(u) 

613 

614 if len(eligible) < n: 

615 continue 

616 

617 for combo in combinations(eligible, n): 

618 base_mask = 0 

619 for u in combo: 

620 base_mask |= cand_set & unit_masks[u] 

621 

622 # All cover units hit by the base cells 

623 cover_indices: list[int] = [] 

624 for ci in range(9): 

625 if base_mask & cover_masks[ci]: 

626 cover_indices.append(ci) 

627 

628 # Need at least n covers; skip if far too many (performance) 

629 if len(cover_indices) < n or len(cover_indices) > n + 3: 

630 continue 

631 

632 # Try every n-subset of cover_indices as the main covers 

633 for cover_combo in combinations(cover_indices, n): 

634 cover_mask = 0 

635 for ci in cover_combo: 

636 cover_mask |= cover_masks[ci] 

637 

638 fin_mask = base_mask & ~cover_mask 

639 if not fin_mask: 

640 continue # basic fish, handled elsewhere 

641 if fin_mask.bit_count() > 5: 

642 continue 

643 

644 # Eliminations: cover candidates that see ALL fin cells 

645 fin_common = _fin_buddies(fin_mask) 

646 elim_mask = cand_set & cover_mask & fin_common & ~base_mask 

647 if not elim_mask: 

648 continue 

649 

650 # Sashimi: any base unit has ≤1 body cell (HoDoKu definition) 

651 is_sashimi = False 

652 for u in combo: 

653 body = cand_set & unit_masks[u] & cover_mask 

654 if body.bit_count() <= 1: 

655 is_sashimi = True 

656 break 

657 

658 if is_sashimi != sashimi: 

659 continue 

660 

661 actual_type = ( 

662 _FINNED_TO_SASHIMI[finned_type] 

663 if is_sashimi else finned_type 

664 ) 

665 return self._make_step( 

666 actual_type, cand, combo, list(cover_combo), 

667 base_mask, elim_mask, row_mode, 

668 fin_mask=fin_mask, 

669 ) 

670 

671 return None 

672 

673 # ------------------------------------------------------------------ 

674 # Generalized fish (Franken / Mutant) 

675 # ------------------------------------------------------------------ 

676 

677 def _find_generalized_fish_all( 

678 self, sol_type: SolutionType, *, for_candidate: int = -1 

679 ) -> list[SolutionStep]: 

680 """Find all Franken or Mutant fish of the requested type. 

681 

682 Mirrors Java FishSolver.getFishes() with FRANKEN or MUTANT fish_type. 

683 When for_candidate is 1-9, only that digit is searched (much faster). 

684 """ 

685 fish_cat, n, with_fins = _GENERALIZED_INFO[sol_type] 

686 grid = self.grid 

687 results: list[SolutionStep] = [] 

688 seen_elims: set[tuple] = set() 

689 

690 # MUTANT: only one orientation (lines=True) since all units go to both 

691 # pools regardless of orientation. 

692 # FRANKEN: two orientations to cover both row-base and col-base setups. 

693 orientations = [True] if fish_cat == _CAT_MUTANT else [True, False] 

694 

695 for cand in range(1, 10): 

696 if for_candidate != -1 and cand != for_candidate: 

697 continue 

698 cand_set = grid.candidate_sets[cand] 

699 if not cand_set: 

700 continue 

701 

702 for lines in orientations: 

703 base_pool, cover_pool = _build_unit_pools( 

704 cand_set, fish_cat, lines, n, with_fins 

705 ) 

706 if len(base_pool) < n: 

707 continue 

708 

709 for base_combo in combinations(range(len(base_pool)), n): 

710 # Accumulate base candidates and track endo fins 

711 base_cand = 0 

712 endo_fins = 0 

713 skip = False 

714 for bi in base_combo: 

715 overlap = base_cand & base_pool[bi][0] 

716 if overlap: 

717 if not with_fins: 

718 # Basic fish: no endo fins allowed 

719 skip = True 

720 break 

721 if (endo_fins | overlap).bit_count() > self._max_endo_fins: 

722 skip = True 

723 break 

724 endo_fins |= overlap 

725 base_cand |= base_pool[bi][0] 

726 if skip: 

727 continue 

728 

729 # Unit indices used as base (to exclude from cover) 

730 base_ids = frozenset(base_pool[bi][1] for bi in base_combo) 

731 

732 # Eligible cover units: not a base unit, intersects base_cand 

733 cover_eligible = [ 

734 (mask, idx) for mask, idx in cover_pool 

735 if idx not in base_ids and (mask & base_cand) 

736 ] 

737 if len(cover_eligible) < n: 

738 continue 

739 

740 # Precompute base classification bits (same for all cover combos) 

741 base_bits = 0 

742 for bi in base_combo: 

743 base_bits |= _unit_type_bit(base_pool[bi][1]) 

744 

745 num_cover = len(cover_eligible) 

746 

747 if _accel is not None: 

748 # ---- C-accelerated cover search ---- 

749 ce_masks = [cover_eligible[i][0] for i in range(num_cover)] 

750 for indices, cover_cand, fins, elim in _accel.find_covers( 

751 ce_masks, n, base_cand, cand_set, 

752 1 if with_fins else 0, self._max_fins, endo_fins, 

753 ): 

754 cover_bits = 0 

755 for k in range(n): 

756 cover_bits |= _unit_type_bit(cover_eligible[indices[k]][1]) 

757 actual_cat = _classify_fish(base_bits, cover_bits) 

758 if actual_cat != fish_cat: 

759 continue 

760 elim_key = (cand, elim) 

761 if elim_key in seen_elims: 

762 continue 

763 seen_elims.add(elim_key) 

764 results.append(self._make_general_step( 

765 sol_type, cand, 

766 [base_pool[bi] for bi in base_combo], 

767 [cover_eligible[indices[k]] for k in range(n)], 

768 base_cand, elim, fins, endo_fins, 

769 )) 

770 else: 

771 # ---- Pure Python fallback (DFS with pruning) ---- 

772 ce_masks = [cover_eligible[i][0] for i in range(num_cover)] 

773 _cc = [0] * (n + 1) 

774 _cn = [0] * (n + 1) 

775 _ni = [0] * (n + 1) 

776 _pi = [0] * (n + 1) 

777 level = 1 

778 _ni[1] = 0 

779 while True: 

780 while _ni[level] > num_cover - (n - level + 1): 

781 level -= 1 

782 if level == 0: 

783 break 

784 if level == 0: 

785 break 

786 ci = _ni[level] 

787 _ni[level] = ci + 1 

788 _pi[level] = ci 

789 mask = ce_masks[ci] 

790 prev_cand = _cc[level - 1] 

791 new_cand = prev_cand | mask 

792 overlap = prev_cand & mask 

793 new_cannibal = _cn[level - 1] 

794 if overlap: 

795 new_cannibal |= overlap 

796 if level < n: 

797 if with_fins and not (base_cand & ~new_cand): 

798 continue 

799 _cc[level] = new_cand 

800 _cn[level] = new_cannibal 

801 level += 1 

802 _ni[level] = ci + 1 

803 else: 

804 fins = base_cand & ~new_cand 

805 # Java includes endo fins in the fin set for 

806 # both the finnless/finned decision and the 

807 # fin_buddies elimination check. 

808 all_fins = fins | endo_fins 

809 if not with_fins: 

810 if all_fins: 

811 continue 

812 elim = cand_set & new_cand & ~base_cand 

813 if new_cannibal: 

814 elim |= cand_set & new_cannibal 

815 if not elim: 

816 continue