Coverage for src / hodoku / solver / tabling.py: 93%
1364 statements
« prev ^ index » next coverage.py v7.13.5, created at 2026-04-21 08:35 +0000
1"""TablingSolver — Forcing Chain / Forcing Net solver.
3Mirrors Java's TablingSolver. Builds implication tables for every premise
4("candidate N is set/deleted in cell X"), expands them transitively, then
5checks for contradictions and verities.
7Also implements Nice Loop / AIC detection via the tabling framework,
8including support for ALS nodes in grouped chains.
9"""
11from __future__ import annotations
13import copy
14from dataclasses import dataclass
15from typing import TYPE_CHECKING
17from hodoku.core.grid import (
18 ALL_UNIT_MASKS,
19 BLOCK_MASKS,
20 BUDDIES,
21 CELL_CONSTRAINTS,
22 COL_MASKS,
23 CONSTRAINTS,
24 DIGIT_MASKS,
25 LINE_MASKS,
26 Grid,
27)
28from hodoku.core.solution_step import SolutionStep
29from hodoku.core.types import SolutionType
30from hodoku.solver.als import Als, _collect_alses
31from hodoku.solver.chain_utils import (
32 ALS_NODE,
33 GROUP_NODE,
34 NORMAL_NODE,
35 get_als_index,
36 get_candidate,
37 get_cell_index,
38 get_cell_index2,
39 get_cell_index3,
40 get_lower_als_index,
41 get_higher_als_index,
42 get_node_type,
43 is_strong,
44 make_entry,
45 make_entry_als,
46 make_entry_simple,
47)
48from hodoku.solver.table_entry import MAX_TABLE_ENTRY_LENGTH, TableEntry
50if TYPE_CHECKING:
51 from hodoku.config import StepSearchConfig
53# ---------------------------------------------------------------------------
54# Group nodes (used by TablingSolver for Grouped Nice Loop / AIC)
55# ---------------------------------------------------------------------------
58@dataclass
59class _GroupNode:
60 """A group node for digit d: 2–3 cells sharing a block and a row or col."""
61 digit: int
62 cells: int # bitmask of cells in group
63 buddies: int # intersection of BUDDIES of all cells (cells that see ALL group cells)
64 block: int # block index 0–8
65 line: int # row index 0–8, or -1 if not row-aligned
66 col: int # col index 0–8, or -1 if not col-aligned
67 index1: int # first cell index
68 index2: int # second cell index
69 index3: int # third cell index, or -1 for 2-cell groups
72def _make_group_node(digit: int, cells_mask: int, block_idx: int) -> _GroupNode:
73 """Construct a _GroupNode from a bitmask of 2–3 cells."""
74 indices: list[int] = []
75 tmp = cells_mask
76 while tmp:
77 lsb = tmp & -tmp
78 indices.append(lsb.bit_length() - 1)
79 tmp ^= lsb
80 index1, index2 = indices[0], indices[1]
81 index3 = indices[2] if len(indices) > 2 else -1
82 r1, c1, _ = CONSTRAINTS[index1]
83 r2, c2, _ = CONSTRAINTS[index2]
84 line = r1 if r1 == r2 else -1
85 col = c1 if c1 == c2 else -1
86 buddies = BUDDIES[index1] & BUDDIES[index2]
87 if index3 >= 0:
88 buddies &= BUDDIES[index3]
89 return _GroupNode(
90 digit=digit, cells=cells_mask, buddies=buddies,
91 block=block_idx, line=line, col=col,
92 index1=index1, index2=index2, index3=index3,
93 )
96def _collect_group_nodes(grid: Grid) -> list[_GroupNode]:
97 """Return all group nodes for the current grid state.
99 Mirrors GroupNode.getGroupNodes(): rows first, then cols, each crossed
100 with all 9 blocks, for each digit 1–9.
101 """
102 gns: list[_GroupNode] = []
103 # Lines (rows) first
104 for line_idx in range(9):
105 lmask = LINE_MASKS[line_idx]
106 for cand in range(1, 10):
107 cand_in_house = grid.candidate_sets[cand] & lmask
108 if not cand_in_house:
109 continue
110 for block_idx in range(9):
111 tmp = cand_in_house & BLOCK_MASKS[block_idx]
112 if tmp.bit_count() >= 2:
113 gns.append(_make_group_node(cand, tmp, block_idx))
114 # Columns next
115 for col_idx in range(9):
116 cmask = COL_MASKS[col_idx]
117 for cand in range(1, 10):
118 cand_in_house = grid.candidate_sets[cand] & cmask
119 if not cand_in_house:
120 continue
121 for block_idx in range(9):
122 tmp = cand_in_house & BLOCK_MASKS[block_idx]
123 if tmp.bit_count() >= 2:
124 gns.append(_make_group_node(cand, tmp, block_idx))
125 return gns
128# ---------------------------------------------------------------------------
129# Helpers
130# ---------------------------------------------------------------------------
132_ALL_CELLS: int = (1 << 81) - 1
135def _iter_bits(mask: int):
136 """Yield set bit positions in ascending order."""
137 while mask:
138 lsb = mask & -mask
139 yield lsb.bit_length() - 1
140 mask ^= lsb
143def _bit_count(mask: int) -> int:
144 return mask.bit_count()
147def _first_bit(mask: int) -> int:
148 """Return the index of the lowest set bit."""
149 return (mask & -mask).bit_length() - 1
152def _get_all_candidates(grid: Grid, cell: int) -> list[int]:
153 """Return list of candidate digits for a cell (ascending)."""
154 mask = grid.candidates[cell]
155 result: list[int] = []
156 for d in range(1, 10):
157 if mask & DIGIT_MASKS[d]:
158 result.append(d)
159 return result
162# ---------------------------------------------------------------------------
163# TablingSolver
164# ---------------------------------------------------------------------------
166class TablingSolver:
167 """Forcing Chain / Forcing Net solver using Trebor's Tables."""
169 def __init__(self, grid: Grid, search_config: StepSearchConfig | None = None) -> None:
170 self.grid = grid
172 # Main tables: index = cell*10 + cand (cands 1-indexed, so 810 entries)
173 self.on_table: list[TableEntry] = [TableEntry() for _ in range(810)]
174 self.off_table: list[TableEntry] = [TableEntry() for _ in range(810)]
176 # Extended table for group nodes (and later ALS nodes)
177 self.extended_table: list[TableEntry] = []
178 self.extended_table_map: dict[int, int] = {}
179 self.extended_table_index: int = 0
181 # Group nodes cache
182 self.group_nodes: list[_GroupNode] = []
184 # ALS cache (populated by _fill_tables_with_als)
185 self._alses: list[Als] = []
187 # Steps found in current run
188 self.steps: list[SolutionStep] = []
189 self.deletes_map: dict[str, int] = {}
191 # Chain reconstruction workspace
192 self._chain: list[int] = [0] * MAX_TABLE_ENTRY_LENGTH
193 self._chain_index: int = 0
194 self._tmp_chain: list[int] = [0] * MAX_TABLE_ENTRY_LENGTH
195 self._mins: list[list[int]] = [[0] * MAX_TABLE_ENTRY_LENGTH for _ in range(200)]
196 self._min_indexes: list[int] = [0] * 200
197 self._act_min: int = 0
198 self._lasso_set: int = 0 # bitmask
199 self._tmp_chains: list[list[int]] = [[] for _ in range(9)]
200 self._tmp_chains_index: int = 0
202 # Chain cell tracking (for nice loop lasso detection)
203 self._chain_set: int = 0 # 81-bit bitmask of cells in current chain
204 self._build_chain_set: int = 0 # cells in main chain (for min early termination)
206 # Nice loop filter flag
207 self._only_grouped_nice_loops: bool = False
209 # Config values from StepSearchConfig
210 if search_config is not None:
211 self._config_allow_als_in_tabling = search_config.tabling_allow_als_in_chains
212 self._anz_table_look_ahead = search_config.tabling_net_depth
213 self._only_one_chain_per_elimination = search_config.tabling_only_one_chain_per_elimination
214 else:
215 self._config_allow_als_in_tabling = False
216 self._anz_table_look_ahead = 4
217 self._only_one_chain_per_elimination = True
219 # Net mode flag: when True, forces all CHAIN types to NET types
220 self._nets_mode: bool = False
222 # Temporary sets for checks
223 self._global_step = SolutionStep(SolutionType.HIDDEN_SINGLE)
225 # candidatesAllowed: per-digit bitmask of cells where digit is allowed
226 # based solely on placed values (ignoring technique eliminations).
227 # Matches Java's SudokuStepFinder.getCandidatesAllowed().
228 self._candidates_allowed: list[int] = [0] * 10
230 # ------------------------------------------------------------------
231 # Public API
232 # ------------------------------------------------------------------
234 def get_step(self, sol_type: SolutionType) -> SolutionStep | None:
235 """Find the best step of the given type, or None.
237 Handles Nice Loops, AICs, Forcing Chains, and Forcing Nets.
238 Mirrors Java TablingSolver.getStep().
239 """
240 if sol_type in (
241 SolutionType.CONTINUOUS_NICE_LOOP,
242 SolutionType.DISCONTINUOUS_NICE_LOOP,
243 SolutionType.AIC,
244 ):
245 return self._get_nice_loops(with_group_nodes=False, with_als_nodes=False)
246 if sol_type in (
247 SolutionType.GROUPED_CONTINUOUS_NICE_LOOP,
248 SolutionType.GROUPED_DISCONTINUOUS_NICE_LOOP,
249 SolutionType.GROUPED_AIC,
250 ):
251 return self._get_nice_loops(
252 with_group_nodes=True,
253 with_als_nodes=self._config_allow_als_in_tabling,
254 )
255 if sol_type in (
256 SolutionType.FORCING_CHAIN_CONTRADICTION,
257 SolutionType.FORCING_CHAIN_VERITY,
258 ):
259 self.steps.clear()
260 self._get_forcing_chains()
261 if self.steps:
262 self.steps.sort(key=_fc_sort_key)
263 return self.steps[0]
264 return None
265 if sol_type in (
266 SolutionType.FORCING_NET_CONTRADICTION,
267 SolutionType.FORCING_NET_VERITY,
268 ):
269 self.steps.clear()
270 self._get_forcing_nets()
271 if self.steps:
272 self.steps.sort(key=_fc_sort_key)
273 return self.steps[0]
274 return None
275 return None
277 def find_all(self, sol_type: SolutionType) -> list[SolutionStep]:
278 """Return all steps of the given type."""
279 if sol_type in (
280 SolutionType.CONTINUOUS_NICE_LOOP,
281 SolutionType.DISCONTINUOUS_NICE_LOOP,
282 SolutionType.AIC,
283 ):
284 return self.find_all_nice_loops(
285 with_group_nodes=False, with_als_nodes=False,
286 only_grouped=False, target_type=sol_type,
287 )
288 if sol_type in (
289 SolutionType.GROUPED_CONTINUOUS_NICE_LOOP,
290 SolutionType.GROUPED_DISCONTINUOUS_NICE_LOOP,
291 SolutionType.GROUPED_AIC,
292 ):
293 return self.find_all_nice_loops(
294 with_group_nodes=True,
295 with_als_nodes=self._config_allow_als_in_tabling,
296 only_grouped=True, target_type=sol_type,
297 )
298 if sol_type in (
299 SolutionType.FORCING_CHAIN_CONTRADICTION,
300 SolutionType.FORCING_CHAIN_VERITY,
301 ):
302 self.steps.clear()
303 self._get_forcing_chains()
304 return [s for s in self.steps if s.type == sol_type]
305 if sol_type in (
306 SolutionType.FORCING_NET_CONTRADICTION,
307 SolutionType.FORCING_NET_VERITY,
308 ):
309 self.steps.clear()
310 self._get_forcing_nets()
311 return [s for s in self.steps if s.type == sol_type]
312 return []
314 def do_step(self, step: SolutionStep) -> None:
315 """Apply a forcing chain/net step to the grid."""
316 grid = self.grid
317 if step.values:
318 for i, value in enumerate(step.values):
319 grid.set_cell(step.indices[i], value)
320 else:
321 for cand in step.candidates_to_delete:
322 grid.del_candidate(cand.index, cand.value)
324 # ------------------------------------------------------------------
325 # Core algorithm
326 # ------------------------------------------------------------------
328 def _get_nice_loops(
329 self,
330 with_group_nodes: bool,
331 with_als_nodes: bool,
332 ) -> SolutionStep | None:
333 """Find the best nice loop / AIC step.
335 Mirrors Java TablingSolver.getNiceLoops() → doGetNiceLoops().
336 """
337 self.steps.clear()
338 self.deletes_map.clear()
339 self._only_grouped_nice_loops = False
341 self._fill_tables()
342 if with_group_nodes:
343 self._fill_tables_with_group_nodes()
344 if with_als_nodes:
345 self._fill_tables_with_als()
347 self._expand_tables(self.on_table)
348 self._expand_tables(self.off_table)
350 self._check_nice_loops(self.on_table)
351 self._check_nice_loops(self.off_table)
352 self._check_aics(self.off_table)
354 if self.steps:
355 self.steps.sort(key=_tabling_sort_key)
356 return self.steps[0]
357 return None
359 def _get_forcing_chains(self) -> None:
360 """Build tables, expand, and check for forcing chains."""
361 self.deletes_map.clear()
363 # Step 1: Fill tables (chains only — direct implications)
364 self._fill_tables()
366 # Step 2: Add group nodes
367 self._fill_tables_with_group_nodes()
369 # Step 3: Expand tables (transitive closure)
370 self._expand_tables(self.on_table)
371 self._expand_tables(self.off_table)
373 # Step 4: Check for contradictions and verities
374 self._check_forcing_chains()
376 def _get_forcing_nets(self) -> None:
377 """Build tables, expand, and check for forcing nets.
379 Mirrors Java TablingSolver.doGetForcingChains() with chainsOnly=false.
380 Net mode uses grid cloning + look-ahead singles detection to find
381 more implications than chain-only mode.
382 """
383 self.deletes_map.clear()
384 self._nets_mode = True
386 try:
387 self._fill_tables_nets()
388 self._fill_tables_with_group_nodes()
389 if self._config_allow_als_in_tabling:
390 self._fill_tables_with_als()
392 self._expand_tables(self.on_table)
393 self._expand_tables(self.off_table)
395 self._check_forcing_chains()
396 finally:
397 self._nets_mode = False
399 # ------------------------------------------------------------------
400 # Step 1: Fill tables — chains only (direct implications)
401 # ------------------------------------------------------------------
403 def _fill_tables(self) -> None:
404 """Populate on_table and off_table with direct implications.
406 Chains-only path: record only immediate consequences of each premise.
407 """
408 grid = self.grid
410 # Reset all tables
411 for i in range(810):
412 self.on_table[i].reset()
413 self.off_table[i].reset()
414 self.extended_table_map.clear()
415 self.extended_table_index = 0
417 for i in range(81):
418 if grid.values[i] != 0:
419 continue
420 for cand in range(1, 10):
421 if not (grid.candidates[i] & DIGIT_MASKS[cand]):
422 continue
424 ti = i * 10 + cand
425 on_entry = self.on_table[ti]
426 off_entry = self.off_table[ti]
428 # Record the premise itself
429 on_entry.add_entry_simple(i, cand, True)
430 off_entry.add_entry_simple(i, cand, False)
432 # ON premise: all other candidates in the cell → OFF
433 # OFF premise (bivalue): the other candidate → ON
434 cands = _get_all_candidates(grid, i)
435 for other_cand in cands:
436 if other_cand == cand:
437 continue
438 on_entry.add_entry_simple(i, other_cand, False)
439 if len(cands) == 2:
440 off_entry.add_entry_simple(i, other_cand, True)
442 # ON premise: for each house, other cells with cand → OFF
443 # Strong link (free==2): also add ON entry (matches Java exactly)
444 peers_with_cand = grid.candidate_sets[cand] & ~(1 << i)
445 for constr in CELL_CONSTRAINTS[i]:
446 anz_cands = grid.free[constr][cand]
447 if anz_cands < 2:
448 continue
449 peers_in_house = peers_with_cand & ALL_UNIT_MASKS[constr]
450 if not peers_in_house:
451 continue
453 # Weak links: all peers lose cand
454 for cell in _iter_bits(peers_in_house):
455 on_entry.add_entry_simple(cell, cand, False)
457 if anz_cands == 2:
458 # Strong link: if cand is OFF, the other candidate
459 # has to be ON (Java: offTable line 1862, NOT onTable)
460 peer = (peers_in_house & -peers_in_house).bit_length() - 1
461 off_entry.add_entry_simple(peer, cand, True)
463 # ------------------------------------------------------------------
464 # Step 1b: Fill tables — nets (look-ahead)
465 # ------------------------------------------------------------------
467 def _fill_tables_nets(self) -> None:
468 """Populate on_table/off_table using net-mode (look-ahead).
470 Clones the grid, applies each premise, then runs naked/hidden single
471 detection for ANZ_TABLE_LOOK_AHEAD rounds to find deeper implications.
472 Mirrors Java fillTables() with chainsOnly=false.
473 """
474 grid = self.grid
476 # Reset tables
477 for i in range(810):
478 self.on_table[i].reset()
479 self.off_table[i].reset()
480 self.extended_table_map.clear()
481 self.extended_table_index = 0
483 saved_grid = grid.clone()
485 for i in range(81):
486 if saved_grid.values[i] != 0:
487 continue
488 cands = _get_all_candidates(saved_grid, i)
489 for cand in cands:
490 # ON: set the cell
491 grid.set(saved_grid)
492 self._get_table_entry_net(self.on_table[i * 10 + cand],
493 i, cand, True, saved_grid)
494 # OFF: delete the candidate
495 grid.set(saved_grid)
496 self._get_table_entry_net(self.off_table[i * 10 + cand],
497 i, cand, False, saved_grid)
499 grid.set(saved_grid)
501 def _get_table_entry_net(
502 self, entry: TableEntry, cell_index: int, cand: int,
503 is_set: bool, saved_grid: Grid,
504 ) -> None:
505 """Fill a single table entry using net-mode look-ahead.
507 Mirrors Java getTableEntry(): applies premise, then looks ahead
508 for naked/hidden singles.
509 """
510 grid = self.grid
512 if is_set:
513 self._set_cell_net(cell_index, cand, entry, saved_grid,
514 get_ret_indices=False, naked_single=False)
515 else:
516 grid.del_candidate(cell_index, cand)
517 entry.add_entry_simple(cell_index, cand, False)
518 # If cell becomes naked single, set it
519 if grid.candidates[cell_index] and not (
520 grid.candidates[cell_index] & (grid.candidates[cell_index] - 1)
521 ):
522 set_cand = grid.candidates[cell_index].bit_length()
523 self._set_cell_net(cell_index, set_cand, entry, saved_grid,
524 get_ret_indices=False, naked_single=True)
526 # Look-ahead rounds: find naked/hidden singles
527 for _ in range(self._anz_table_look_ahead):
528 singles = self._find_all_singles_net(grid)
529 if not singles:
530 break
531 for s_cell, s_cand, is_naked in singles:
532 self._set_cell_net(s_cell, s_cand, entry, saved_grid,
533 get_ret_indices=True, naked_single=is_naked)
535 def _set_cell_net(
536 self, cell_index: int, cand: int, entry: TableEntry,
537 saved_grid: Grid, get_ret_indices: bool, naked_single: bool,
538 ) -> None:
539 """Set a cell during net-mode table filling and record implications.
541 Mirrors Java setCell(). Records:
542 - ON entry for the set cell
543 - OFF entries for all buddy cells that have the candidate
544 - OFF entries for all other candidates in the cell
545 """
546 grid = self.grid
548 # Find all candidates that will be eliminated by setting this cell
549 # Use original (saved) candidates for the buddy check
550 peers_with_cand = saved_grid.candidate_sets[cand] & BUDDIES[cell_index]
551 peers_with_cand &= ~(1 << cell_index)
553 # Get other candidates in the cell (from current working grid, before set)
554 other_cands = _get_all_candidates(grid, cell_index)
556 # Find retIndices if needed (for look-ahead steps)
557 ri = [0, 0, 0, 0, 0]
558 if get_ret_indices:
559 if naked_single:
560 # Naked single: depends on elimination of all other candidates
561 cell_cands = _get_all_candidates(saved_grid, cell_index)
562 ri_idx = 0
563 for c in cell_cands:
564 if c == cand and ri_idx < 5:
565 continue
566 idx = entry.get_entry_index(cell_index, False, c)
567 if ri_idx < 5:
568 ri[ri_idx] = idx
569 ri_idx += 1
570 else:
571 # Hidden single: depends on elimination of cand from house peers
572 # Find house with smallest number of candidates in current grid
573 # (Java uses sudoku.getFree(), not savedSudoku — must be done
574 # before the cell is set)
575 best_free = 999
576 best_constr = CELL_CONSTRAINTS[cell_index][0]
577 for constr in CELL_CONSTRAINTS[cell_index]:
578 f = grid.free[constr][cand]
579 if f < best_free:
580 best_free = f
581 best_constr = constr
582 # Get all original candidates in that house (excluding self)
583 house_peers = saved_grid.candidate_sets[cand] & ALL_UNIT_MASKS[best_constr]
584 house_peers &= ~(1 << cell_index)
585 ri_idx = 0
586 for cell in _iter_bits(house_peers):
587 if ri_idx >= 5:
588 break
589 idx = entry.get_entry_index(cell, False, cand)
590 ri[ri_idx] = idx
591 ri_idx += 1
593 # Now actually set the cell
594 ret_index = entry.index
595 grid.set_cell(cell_index, cand)
597 # ON entry for the set operation
598 if get_ret_indices:
599 entry.add_entry(cell_index, cand, True,
600 ri1=ri[0], ri2=ri[1], ri3=ri[2],
601 ri4=ri[3], ri5=ri[4])
602 else:
603 entry.add_entry_simple(cell_index, cand, True)
605 # OFF entries for all buddy cells that can see this cell (same candidate)
606 for cell in _iter_bits(peers_with_cand):
607 entry.add_entry_with_ri(cell, cand, False, ret_index)
609 # OFF entries for all other candidates in the cell
610 for c in other_cands:
611 if c != cand:
612 entry.add_entry_with_ri(cell_index, c, False, ret_index)
614 @staticmethod
615 def _find_all_singles_net(grid: Grid) -> list[tuple[int, int, bool]]:
616 """Find all naked and hidden singles in the grid.
618 Returns list of (cell, digit, is_naked_single).
620 Uses the grid's ns_queue/hs_queue to match Java's queue-based
621 discovery order (SimpleSolver.findAllNakedSingles / findAllHiddenSingles).
622 The order matters because singles are applied sequentially and each
623 setCell modifies the grid for subsequent singles.
624 """
625 results: list[tuple[int, int, bool]] = []
627 # Naked singles — iterate nsQueue
628 for cell, digit in grid.ns_queue:
629 if grid.values[cell] == 0:
630 results.append((cell, digit, True))
632 # Hidden singles — iterate hsQueue
633 # Java uses singleFound[] to avoid duplicate cells
634 # Java also removes stale entries from the queue (deleteHiddenSingle)
635 # when free increases from 1→2 or when the cell loses the candidate.
636 # Since Python's deque doesn't remove stale entries, we must verify
637 # the cell still has the candidate before accepting a hidden single.
638 single_found: set[int] = set()
639 for cell, digit in grid.hs_queue:
640 if grid.values[cell] == 0 and cell not in single_found:
641 # Check cell still has the candidate (stale queue guard)
642 if not (grid.candidates[cell] & DIGIT_MASKS[digit]):
643 continue
644 # Verify the constraint still has free==1 for this digit
645 for constr in CELL_CONSTRAINTS[cell]:
646 if grid.free[constr][digit] == 1:
647 results.append((cell, digit, False))
648 single_found.add(cell)
649 break
651 return results
653 # ------------------------------------------------------------------
654 # Step 2: Fill tables with group nodes
655 # ------------------------------------------------------------------
657 def _get_next_extended_table_entry(self, index: int) -> TableEntry:
658 """Ensure extended_table has an entry at ``index``, reset and return it."""
659 while index >= len(self.extended_table):
660 self.extended_table.append(TableEntry())
661 entry = self.extended_table[index]
662 entry.reset()
663 return entry
665 def _fill_tables_with_group_nodes(self) -> None:
666 """Add group node implications to the extended table and cross-link
667 them into on_table / off_table.
669 Mirrors TablingSolver.fillTablesWithGroupNodes() in Java.
670 """
671 grid = self.grid
672 self.group_nodes = _collect_group_nodes(grid)
673 gns = self.group_nodes
675 for i, gn in enumerate(gns):
676 # Create ON entry in extended table
677 on_entry = self._get_next_extended_table_entry(self.extended_table_index)
678 on_entry.add_entry(
679 gn.index1, gn.digit, True,
680 cell_index2=gn.index2, cell_index3=gn.index3,
681 node_type=GROUP_NODE,
682 )
683 self.extended_table_map[on_entry.entries[0]] = self.extended_table_index
684 self.extended_table_index += 1
686 # Create OFF entry in extended table
687 off_entry = self._get_next_extended_table_entry(self.extended_table_index)
688 off_entry.add_entry(
689 gn.index1, gn.digit, False,
690 cell_index2=gn.index2, cell_index3=gn.index3,
691 node_type=GROUP_NODE,
692 )
693 self.extended_table_map[off_entry.entries[0]] = self.extended_table_index
694 self.extended_table_index += 1
696 # Candidates that can see the group node (same digit, in buddies)
697 visible = grid.candidate_sets[gn.digit] & gn.buddies
698 if visible:
699 # GN ON → every visible candidate is OFF
700 # Each visible candidate's onTable gets a GN OFF entry
701 for cell in _iter_bits(visible):
702 on_entry.add_entry_simple(cell, gn.digit, False)
703 tmp = self.on_table[cell * 10 + gn.digit]
704 tmp.add_entry(
705 gn.index1, gn.digit, False,
706 cell_index2=gn.index2, cell_index3=gn.index3,
707 node_type=GROUP_NODE,
708 )
710 # GN OFF → if only one candidate remains in a house,
711 # that candidate is ON
712 # Check block
713 block_visible = visible & BLOCK_MASKS[gn.block]
714 if block_visible and _bit_count(block_visible) == 1:
715 cell = (block_visible & -block_visible).bit_length() - 1
716 off_entry.add_entry_simple(cell, gn.digit, True)
717 tmp = self.off_table[cell * 10 + gn.digit]
718 tmp.add_entry(
719 gn.index1, gn.digit, True,
720 cell_index2=gn.index2, cell_index3=gn.index3,
721 node_type=GROUP_NODE,
722 )
724 # Check line or col
725 if gn.line != -1:
726 line_visible = visible & LINE_MASKS[gn.line]
727 else:
728 line_visible = visible & COL_MASKS[gn.col]
729 if line_visible and _bit_count(line_visible) == 1:
730 cell = (line_visible & -line_visible).bit_length() - 1
731 off_entry.add_entry_simple(cell, gn.digit, True)
732 tmp = self.off_table[cell * 10 + gn.digit]
733 tmp.add_entry(
734 gn.index1, gn.digit, True,
735 cell_index2=gn.index2, cell_index3=gn.index3,
736 node_type=GROUP_NODE,
737 )
739 # Group-node-to-group-node connections
740 line_count = 0
741 line1_index = -1
742 col_count = 0
743 col1_index = -1
744 block_count = 0
745 block1_index = -1
747 for j, gn2 in enumerate(gns):
748 if j == i:
749 continue
750 if gn.digit != gn2.digit:
751 continue
752 # Check for overlap
753 if gn.cells & gn2.cells:
754 continue
756 # Same line → GN ON turns other GN OFF
757 if gn.line != -1 and gn.line == gn2.line:
758 line_count += 1
759 if line_count == 1:
760 line1_index = j
761 on_entry.add_entry(
762 gn2.index1, gn.digit, False,
763 cell_index2=gn2.index2, cell_index3=gn2.index3,
764 node_type=GROUP_NODE,
765 )
767 # Same col
768 if gn.col != -1 and gn.col == gn2.col:
769 col_count += 1
770 if col_count == 1:
771 col1_index = j
772 on_entry.add_entry(
773 gn2.index1, gn.digit, False,
774 cell_index2=gn2.index2, cell_index3=gn2.index3,
775 node_type=GROUP_NODE,
776 )
778 # Same block
779 if gn.block == gn2.block:
780 block_count += 1
781 if block_count == 1:
782 block1_index = j
783 on_entry.add_entry(
784 gn2.index1, gn.digit, False,
785 cell_index2=gn2.index2, cell_index3=gn2.index3,
786 node_type=GROUP_NODE,
787 )
789 # If only one other GN in a house and no additional single
790 # candidates → GN OFF turns other GN ON
791 if line_count == 1:
792 gn2 = gns[line1_index]
793 house_cands = LINE_MASKS[gn.line] & grid.candidate_sets[gn.digit]
794 house_cands &= ~gn.cells
795 house_cands &= ~gn2.cells
796 if not house_cands:
797 off_entry.add_entry(
798 gn2.index1, gn.digit, True,
799 cell_index2=gn2.index2, cell_index3=gn2.index3,
800 node_type=GROUP_NODE,
801 )
803 if col_count == 1:
804 gn2 = gns[col1_index]
805 house_cands = COL_MASKS[gn.col] & grid.candidate_sets[gn.digit]
806 house_cands &= ~gn.cells
807 house_cands &= ~gn2.cells
808 if not house_cands:
809 off_entry.add_entry(
810 gn2.index1, gn.digit, True,
811 cell_index2=gn2.index2, cell_index3=gn2.index3,
812 node_type=GROUP_NODE,
813 )
815 if block_count == 1:
816 gn2 = gns[block1_index]
817 house_cands = BLOCK_MASKS[gn.block] & grid.candidate_sets[gn.digit]
818 house_cands &= ~gn.cells
819 house_cands &= ~gn2.cells
820 if not house_cands:
821 off_entry.add_entry(
822 gn2.index1, gn.digit, True,
823 cell_index2=gn2.index2, cell_index3=gn2.index3,
824 node_type=GROUP_NODE,
825 )
827 # ------------------------------------------------------------------
828 # Step 2b: Fill tables with ALS nodes
829 # ------------------------------------------------------------------
831 def _get_als_table_entry(
832 self, entry_cell: int, als_index: int, cand: int,
833 ) -> TableEntry | None:
834 """Look up an existing ALS table entry in the extended table."""
835 entry = make_entry_als(entry_cell, als_index, cand, False, ALS_NODE)
836 idx = self.extended_table_map.get(entry)
837 if idx is not None:
838 return self.extended_table[idx]
839 return None
841 def _fill_tables_with_als(self) -> None:
842 """Add ALS node implications to the extended table and cross-link
843 them into on_table / off_table.
845 Mirrors TablingSolver.fillTablesWithAls() in Java.
846 """
847 grid = self.grid
848 alses = _collect_alses(grid)
849 # Skip single-cell ALSes (bivalue cells, handled as normal nodes)
850 self._alses = [als for als in alses if als.indices.bit_count() >= 2]
851 alses = self._alses
853 gns = self.group_nodes
855 for i, als in enumerate(alses):
856 for j in range(1, 10):
857 if not als.indices_per_cand[j]:
858 continue
860 # Check if there are possible eliminations for any other digit k
861 als_elims: list[int] = [0] * 10 # [k] = bitmask of eliminable cells
862 eliminations_present = False
863 for k in range(1, 10):
864 if k == j:
865 continue
866 if not als.indices_per_cand[k]:
867 continue
868 # Cells with candidate k that see ALL ALS cells with k
869 als_elims[k] = grid.candidate_sets[k] & als.buddies_per_cand[k]
870 if als_elims[k]:
871 eliminations_present = True
873 if not eliminations_present:
874 continue
876 # Create or find the ALS off-table entry
877 entry_cell = _first_bit(als.indices_per_cand[j])
878 off_entry = self._get_als_table_entry(entry_cell, i, j)
879 if off_entry is None:
880 off_entry = self._get_next_extended_table_entry(
881 self.extended_table_index
882 )
883 off_entry.add_entry(
884 entry_cell, j, False,
885 cell_index2=get_lower_als_index(i),
886 cell_index3=get_higher_als_index(i),
887 node_type=ALS_NODE,
888 )
889 self.extended_table_map[off_entry.entries[0]] = (
890 self.extended_table_index
891 )
892 self.extended_table_index += 1
894 # Put the ALS into onTables of all entry candidates:
895 # find cells with candidate j that see all ALS cells with j
896 trigger_cells = grid.candidate_sets[j] & als.buddies_per_cand[j]
897 als_entry_val = make_entry_als(
898 entry_cell, i, j, False, ALS_NODE
899 )
901 for cell in _iter_bits(trigger_cells):
902 # Add ALS to cell's ON table
903 on_te = self.on_table[cell * 10 + j]
904 on_te.add_entry(
905 entry_cell, j, False,
906 cell_index2=get_lower_als_index(i),
907 cell_index3=get_higher_als_index(i),
908 node_type=ALS_NODE,
909 )
911 # Every group node containing this cell that doesn't
912 # overlap the ALS and sees all ALS cells with j
913 for gn in gns:
914 if gn.digit != j:
915 continue
916 if not (gn.cells & (1 << cell)):
917 continue
918 # Check overlap with ALS
919 if gn.cells & als.indices:
920 continue
921 # All ALS cells with j must be in group node's buddies
922 if (als.indices_per_cand[j] & gn.buddies) != als.indices_per_cand[j]:
923 continue
924 # Look up the group node ON entry in extended table
925 gn_on_val = make_entry(
926 gn.index1, gn.index2, gn.index3,
927 j, True, GROUP_NODE,
928 )
929 gn_ext_idx = self.extended_table_map.get(gn_on_val)
930 if gn_ext_idx is None:
931 continue
932 gn_te = self.extended_table[gn_ext_idx]
933 if als_entry_val in gn_te.indices:
934 continue
935 # Add ALS to group node's ON table
936 gn_te.add_entry(
937 entry_cell, j, False,
938 cell_index2=get_lower_als_index(i),
939 cell_index3=get_higher_als_index(i),
940 node_type=ALS_NODE,
941 )
943 # Record elimination targets in the ALS off-table
944 chain_penalty = als.get_chain_penalty()
945 for k in range(1, 10):
946 if not als_elims[k]:
947 continue
948 for cell in _iter_bits(als_elims[k]):
949 off_entry.add_entry(cell, k, False, penalty=chain_penalty)
950 # If a group node is a subset of the eliminations
951 for gn in gns:
952 if gn.digit != k:
953 continue
954 if (gn.cells & als_elims[k]) != gn.cells:
955 continue
956 off_entry.add_entry(
957 gn.index1, k, False,
958 cell_index2=gn.index2, cell_index3=gn.index3,
959 node_type=GROUP_NODE,
960 penalty=chain_penalty,
961 )
963 # Trigger other non-overlapping ALSes
964 for k_idx, k_als in enumerate(alses):
965 if k_idx == i:
966 continue
967 if als.indices & k_als.indices:
968 continue # overlapping
969 for l in range(1, 10): # noqa: E741
970 if not als_elims[l]:
971 continue
972 if not k_als.indices_per_cand[l]:
973 continue
974 # alsEliminations must contain all k_als cells with l
975 if (k_als.indices_per_cand[l] & als_elims[l]) != k_als.indices_per_cand[l]:
976 continue
977 # Create table for triggered ALS if needed
978 k_entry_cell = _first_bit(k_als.indices_per_cand[l])
979 if self._get_als_table_entry(k_entry_cell, k_idx, l) is None:
980 new_entry = self._get_next_extended_table_entry(
981 self.extended_table_index
982 )
983 new_entry.add_entry(
984 k_entry_cell, l, False,
985 cell_index2=get_lower_als_index(k_idx),
986 cell_index3=get_higher_als_index(k_idx),
987 node_type=ALS_NODE,
988 )
989 self.extended_table_map[new_entry.entries[0]] = (
990 self.extended_table_index
991 )
992 self.extended_table_index += 1
993 # Link from current ALS to triggered ALS
994 off_entry.add_entry(
995 k_entry_cell, l, False,
996 cell_index2=get_lower_als_index(k_idx),
997 cell_index3=get_higher_als_index(k_idx),
998 node_type=ALS_NODE,
999 penalty=chain_penalty,
1000 )
1002 # Forcings: if a buddy cell has only 1 candidate left
1003 for cell in _iter_bits(als.buddies):
1004 if grid.values[cell] != 0:
1005 continue
1006 cand_count = grid.candidates[cell].bit_count()
1007 if cand_count <= 2:
1008 continue
1009 remaining = grid.candidates[cell]
1010 for l in range(1, 10): # noqa: E741
1011 if als_elims[l] and (als_elims[l] & (1 << cell)):
1012 remaining &= ~DIGIT_MASKS[l]
1013 if remaining.bit_count() == 1:
1014 forced_digit = remaining.bit_length()
1015 off_entry.add_entry(
1016 cell, forced_digit, True,
1017 penalty=chain_penalty + 1,
1018 )
1020 # ------------------------------------------------------------------
1021 # Step 3: Expand tables (transitive closure)
1022 # ------------------------------------------------------------------
1024 def _expand_tables(self, table: list[TableEntry]) -> None:
1025 """Expand every entry in *table* by merging implications from source
1026 tables.
1028 Mirrors TablingSolver.expandTables() in Java.
1029 """
1030 on_table = self.on_table
1031 off_table = self.off_table
1032 ext_table = self.extended_table
1033 ext_map = self.extended_table_map
1035 for i in range(len(table)):
1036 dest = table[i]
1037 if dest.index == 0:
1038 continue
1040 # Walk entries (excluding premise at 0)
1041 j = 1
1042 while j < len(dest.entries):
1043 entry_val = dest.entries[j]
1044 if entry_val == 0:
1045 break
1046 if dest.is_full():
1047 break
1049 # Find the source table for this entry
1050 is_from_extended = False
1051 is_from_on = False
1053 if get_node_type(entry_val) != NORMAL_NODE:
1054 # Group/ALS node → look up in extended table
1055 src_idx = ext_map.get(entry_val)
1056 if src_idx is None:
1057 j += 1
1058 continue
1059 src = ext_table[src_idx]
1060 src_table_index = src_idx
1061 is_from_extended = True
1062 else:
1063 src_table_index = dest.get_cell_index(j) * 10 + dest.get_candidate(j)
1064 if dest.is_strong(j):
1065 src = on_table[src_table_index]
1066 is_from_on = True
1067 else:
1068 src = off_table[src_table_index]
1070 if src.index == 0:
1071 j += 1
1072 continue
1074 # Expand: merge non-expanded entries from src into dest
1075 src_base_distance = dest.get_distance(j)
1077 for k in range(1, src.index):
1078 if src.is_expanded(k):
1079 continue
1081 src_distance = src.get_distance(k)
1082 src_entry = src.entries[k]
1084 if src_entry in dest.indices:
1085 # Entry already exists in dest — check if shorter path
1086 org_index = dest.indices[src_entry]
1087 if dest.is_expanded(org_index):
1088 new_dist = src_base_distance + src_distance
1089 old_dist = dest.get_distance(org_index)
1090 if (old_dist > new_dist or
1091 (old_dist == new_dist and
1092 dest.get_node_type(org_index) > src.get_node_type(k))):
1093 # Shorter or simpler path → rewrite
1094 dest.ret_indices[org_index] = _make_ret_index_single(src_table_index)
1095 dest.set_expanded(org_index)
1096 if is_from_extended:
1097 dest.set_extended_table(org_index)
1098 elif is_from_on:
1099 dest.set_on_table(org_index)
1100 dest._set_distance(org_index, new_dist)
1101 else:
1102 # New entry — add it
1103 if get_node_type(src_entry) == NORMAL_NODE:
1104 dest.add_entry_with_ri(
1105 src.get_cell_index(k),
1106 src.get_candidate(k),
1107 src.is_strong(k),
1108 src_table_index,
1109 )
1110 else:
1111 dest.add_entry(
1112 get_cell_index(src_entry),
1113 get_candidate(src_entry),
1114 is_strong(src_entry),
1115 cell_index2=get_cell_index2(src_entry),
1116 cell_index3=get_cell_index3(src_entry),
1117 node_type=get_node_type(src_entry),
1118 ri1=src_table_index,
1119 )
1121 new_idx = dest.index - 1
1122 dest.set_expanded(new_idx)
1123 if is_from_extended:
1124 dest.set_extended_table(new_idx)
1125 elif is_from_on:
1126 dest.set_on_table(new_idx)
1127 dest._set_distance(new_idx, src_base_distance + src_distance)
1129 j += 1
1131 # ------------------------------------------------------------------
1132 # Step 4: Check for contradictions and verities (Stage 4)
1133 # ------------------------------------------------------------------
1135 def _init_candidates_allowed(self) -> None:
1136 """Compute candidatesAllowed — cells where each digit is allowed
1137 based solely on placed values (ignoring technique eliminations).
1139 Matches Java's SudokuStepFinder.initCandidatesAllowed().
1140 """
1141 grid = self.grid
1142 full = _ALL_CELLS
1143 empty_cells = full
1144 for d in range(1, 10):
1145 self._candidates_allowed[d] = full
1146 for i in range(81):
1147 if grid.values[i] != 0:
1148 self._candidates_allowed[grid.values[i]] &= ~BUDDIES[i]
1149 empty_cells &= ~(1 << i)
1150 for d in range(1, 10):
1151 self._candidates_allowed[d] &= empty_cells
1153 def _check_forcing_chains(self) -> None:
1154 """Run all forcing chain/net checks after tables are built."""
1155 self._init_candidates_allowed()
1157 # Contradiction from single chain
1158 for i in range(810):
1159 self._check_one_chain(self.on_table[i])
1160 self._check_one_chain(self.off_table[i])
1162 # Verity from two chains (same cell+cand, ON vs OFF)
1163 for i in range(810):
1164 self._check_two_chains(self.on_table[i], self.off_table[i])
1166 # Verity from all candidates in a cell / house
1167 self._check_all_chains_for_house(None)
1168 self._check_all_chains_for_house(LINE_MASKS)
1169 self._check_all_chains_for_house(COL_MASKS)
1170 self._check_all_chains_for_house(BLOCK_MASKS)
1172 def _check_one_chain(self, entry: TableEntry) -> None:
1173 """Check a single table entry for contradictions.
1175 Six checks mirroring TablingSolver.checkOneChain():
1176 1. Inverse of premise in same table
1177 2. Same candidate set AND deleted in same cell
1178 3. Two different values set in same cell
1179 4. Same value set twice in one house
1180 5. Cell emptied (all candidates deleted)
1181 6. All instances of candidate deleted from house
1182 """
1183 if entry.index == 0:
1184 return
1186 grid = self.grid
1187 premise_cell = entry.get_cell_index(0)
1188 premise_cand = entry.get_candidate(0)
1189 premise_strong = entry.is_strong(0)
1191 # --- Check 1: chain contains inverse of premise ---
1192 if premise_strong:
1193 # ON premise but OFF for same cand in same cell → contradiction
1194 if entry.off_sets[premise_cand] & (1 << premise_cell):
1195 self._global_step.reset()
1196 self._global_step.type = SolutionType.FORCING_CHAIN_CONTRADICTION
1197 self._global_step.add_candidate_to_delete(premise_cell, premise_cand)
1198 self._global_step.entity = 0 # CELL
1199 self._reset_tmp_chains()
1200 self._add_chain(entry, premise_cell, premise_cand, False)
1201 self._replace_or_copy_step()
1202 else:
1203 # OFF premise but ON for same cand in same cell → contradiction
1204 if entry.on_sets[premise_cand] & (1 << premise_cell):
1205 self._global_step.reset()
1206 self._global_step.type = SolutionType.FORCING_CHAIN_CONTRADICTION
1207 self._global_step.add_index(premise_cell)
1208 self._global_step.add_value(premise_cand)
1209 self._global_step.entity = 0
1210 self._reset_tmp_chains()
1211 self._add_chain(entry, premise_cell, premise_cand, True)
1212 self._replace_or_copy_step()
1214 # --- Check 2: same candidate set AND deleted in same cell ---
1215 for i in range(len(entry.on_sets)):
1216 tmp = entry.on_sets[i] & entry.off_sets[i]
1217 if tmp:
1218 self._global_step.reset()
1219 self._global_step.type = SolutionType.FORCING_CHAIN_CONTRADICTION
1220 if premise_strong:
1221 self._global_step.add_candidate_to_delete(premise_cell, premise_cand)
1222 else:
1223 self._global_step.add_index(premise_cell)
1224 self._global_step.add_value(premise_cand)
1225 self._global_step.entity = 0
1226 first_cell = (tmp & -tmp).bit_length() - 1
1227 self._global_step.entity_number = first_cell
1228 self._reset_tmp_chains()
1229 self._add_chain(entry, first_cell, i, False)
1230 self._add_chain(entry, first_cell, i, True)
1231 self._replace_or_copy_step()
1233 # --- Check 3: two different values set in same cell ---
1234 for i in range(1, 10):
1235 for j in range(i + 1, 10):
1236 tmp = entry.on_sets[i] & entry.on_sets[j]
1237 if tmp:
1238 self._global_step.reset()
1239 self._global_step.type = SolutionType.FORCING_CHAIN_CONTRADICTION
1240 if premise_strong:
1241 self._global_step.add_candidate_to_delete(premise_cell, premise_cand)
1242 else:
1243 self._global_step.add_index(premise_cell)
1244 self._global_step.add_value(premise_cand)
1245 self._global_step.entity = 0
1246 first_cell = (tmp & -tmp).bit_length() - 1
1247 self._global_step.entity_number = first_cell
1248 self._reset_tmp_chains()
1249 self._add_chain(entry, first_cell, i, True)
1250 self._add_chain(entry, first_cell, j, True)
1251 self._replace_or_copy_step()
1253 # --- Check 4: same value set twice in one house ---
1254 self._check_house_set(entry, LINE_MASKS, 1) # LINE
1255 self._check_house_set(entry, COL_MASKS, 2) # COL
1256 self._check_house_set(entry, BLOCK_MASKS, 3) # BLOCK
1258 # --- Check 5: cell emptied (all candidates deleted) ---
1259 # For each cell: if all its candidates are in off_sets (and not
1260 # counteracted by on_sets or already-set values), it's emptied.
1261 # Mirrors Java: AND(offSets[i] | ~candidateSets[i]) for i=1..9,
1262 # then remove cells with ON values and already-solved cells.
1263 tmp_all = _ALL_CELLS
1264 for i in range(1, 10):
1265 or_not = entry.off_sets[i] | (_ALL_CELLS & ~grid.candidate_sets[i])
1266 tmp_all &= or_not
1267 for i in range(10):
1268 tmp_all &= ~entry.on_sets[i]
1269 # Remove already-solved cells
1270 solved_mask = 0
1271 for cell in range(81):
1272 if grid.values[cell] != 0:
1273 solved_mask |= 1 << cell
1274 tmp_all &= ~solved_mask
1276 if tmp_all:
1277 for cell in _iter_bits(tmp_all):
1278 self._global_step.reset()
1279 self._global_step.type = SolutionType.FORCING_CHAIN_CONTRADICTION
1280 if premise_strong:
1281 self._global_step.add_candidate_to_delete(premise_cell, premise_cand)
1282 else:
1283 self._global_step.add_index(premise_cell)
1284 self._global_step.add_value(premise_cand)
1285 self._global_step.entity = 0
1286 self._global_step.entity_number = cell
1287 self._reset_tmp_chains()
1288 cands = _get_all_candidates(grid, cell)
1289 for c in cands:
1290 self._add_chain(entry, cell, c, False)
1291 self._replace_or_copy_step()
1293 # --- Check 6: all instances of candidate deleted from house ---
1294 self._check_house_del(entry, LINE_MASKS, 1)
1295 self._check_house_del(entry, COL_MASKS, 2)
1296 self._check_house_del(entry, BLOCK_MASKS, 3)
1298 def _check_house_set(
1299 self, entry: TableEntry, house_masks: tuple[int, ...], entity_type: int,
1300 ) -> None:
1301 """Check if an assumption leads to same value set twice in one house."""
1302 premise_cell = entry.get_cell_index(0)
1303 premise_cand = entry.get_candidate(0)
1304 premise_strong = entry.is_strong(0)
1306 for i in range(1, 10):
1307 for j, h_mask in enumerate(house_masks):
1308 tmp = h_mask & entry.on_sets[i]
1309 if _bit_count(tmp) > 1:
1310 self._global_step.reset()
1311 self._global_step.type = SolutionType.FORCING_CHAIN_CONTRADICTION
1312 if premise_strong:
1313 self._global_step.add_candidate_to_delete(premise_cell, premise_cand)
1314 else:
1315 self._global_step.add_index(premise_cell)
1316 self._global_step.add_value(premise_cand)
1317 self._global_step.entity = entity_type
1318 self._global_step.entity_number = j
1319 self._reset_tmp_chains()
1320 for cell in _iter_bits(tmp):
1321 self._add_chain(entry, cell, i, True)
1322 self._replace_or_copy_step()
1324 def _check_house_del(
1325 self, entry: TableEntry, house_masks: tuple[int, ...], entity_type: int,
1326 ) -> None:
1327 """Check if all instances of a candidate are deleted from a house."""
1328 premise_cell = entry.get_cell_index(0)
1329 premise_cand = entry.get_candidate(0)
1330 premise_strong = entry.is_strong(0)
1332 for i in range(1, 10):
1333 for j, h_mask in enumerate(house_masks):
1334 # Java uses candidatesAllowed (based on placed values only),
1335 # not candidates (which reflects technique eliminations).
1336 tmp = h_mask & self._candidates_allowed[i]
1337 if tmp and (tmp & entry.off_sets[i]) == tmp:
1338 self._global_step.reset()
1339 self._global_step.type = SolutionType.FORCING_CHAIN_CONTRADICTION
1340 if premise_strong:
1341 self._global_step.add_candidate_to_delete(premise_cell, premise_cand)
1342 else:
1343 self._global_step.add_index(premise_cell)
1344 self._global_step.add_value(premise_cand)
1345 self._global_step.entity = entity_type
1346 self._global_step.entity_number = j
1347 self._reset_tmp_chains()
1348 for cell in _iter_bits(tmp):
1349 self._add_chain(entry, cell, i, False)
1350 self._replace_or_copy_step()
1352 def _check_two_chains(self, on: TableEntry, off: TableEntry) -> None:
1353 """Check ON/OFF pair for verities.
1355 If both ON and OFF premises for the same cell/candidate lead to the
1356 same conclusion, that conclusion must be true.
1357 """
1358 if on.index == 0 or off.index == 0:
1359 return
1361 premise_cell = on.get_cell_index(0)
1363 # Check onSets: both lead to same value SET in same cell
1364 for i in range(1, 10):
1365 tmp = on.on_sets[i] & off.on_sets[i] & ~(1 << premise_cell)
1366 if tmp:
1367 for cell in _iter_bits(tmp):
1368 self._global_step.reset()
1369 self._global_step.type = SolutionType.FORCING_CHAIN_VERITY
1370 self._global_step.add_index(cell)
1371 self._global_step.add_value(i)
1372 self._reset_tmp_chains()
1373 self._add_chain(on, cell, i, True)
1374 self._add_chain(off, cell, i, True)
1375 self._replace_or_copy_step()
1377 # Check offSets: both lead to same candidate DELETED from same cell
1378 for i in range(1, 10):
1379 tmp = on.off_sets[i] & off.off_sets[i] & ~(1 << premise_cell)
1380 if tmp:
1381 for cell in _iter_bits(tmp):
1382 self._global_step.reset()
1383 self._global_step.type = SolutionType.FORCING_CHAIN_VERITY
1384 self._global_step.add_candidate_to_delete(cell, i)
1385 self._reset_tmp_chains()
1386 self._add_chain(on, cell, i, False)
1387 self._add_chain(off, cell, i, False)
1388 self._replace_or_copy_step()
1390 def _check_all_chains_for_house(
1391 self,
1392 house_masks: tuple[int, ...] | None,
1393 ) -> None:
1394 """Check all candidates in cells/houses for verities.
1396 If ALL candidates for a cell (or all instances of a digit in a house)
1397 lead to the same conclusion, that conclusion must be true.
1398 """
1399 grid = self.grid
1401 if house_masks is None:
1402 # Check per cell: all candidates in the cell
1403 for i in range(81):
1404 if grid.values[i] != 0:
1405 continue
1406 entry_list: list[TableEntry] = []
1407 cands = _get_all_candidates(grid, i)
1408 for c in cands:
1409 entry_list.append(self.on_table[i * 10 + c])
1410 self._check_entry_list(entry_list)
1411 else:
1412 # Check per house: all cells with candidate j in house i
1413 for i, h_mask in enumerate(house_masks):
1414 for j in range(1, 10):
1415 tmp = h_mask & grid.candidate_sets[j]
1416 if tmp:
1417 entry_list = []
1418 for cell in _iter_bits(tmp):
1419 entry_list.append(self.on_table[cell * 10 + j])
1420 self._check_entry_list(entry_list)
1422 def _check_entry_list(self, entry_list: list[TableEntry]) -> None:
1423 """AND all on_sets/off_sets across entry_list; anything remaining is a verity."""
1424 if not entry_list:
1425 return
1427 # AND all on_sets and off_sets
1428 tmp_on = [0] * 10
1429 tmp_off = [0] * 10
1430 for idx, entry in enumerate(entry_list):
1431 for j in range(1, 10):
1432 if idx == 0:
1433 tmp_on[j] = entry.on_sets[j]
1434 tmp_off[j] = entry.off_sets[j]
1435 else:
1436 tmp_on[j] &= entry.on_sets[j]
1437 tmp_off[j] &= entry.off_sets[j]
1439 for j in range(1, 10):
1440 if tmp_on[j]:
1441 for cell in _iter_bits(tmp_on[j]):
1442 self._global_step.reset()
1443 self._global_step.type = SolutionType.FORCING_CHAIN_VERITY
1444 self._global_step.add_index(cell)
1445 self._global_step.add_value(j)
1446 self._reset_tmp_chains()
1447 for entry in entry_list:
1448 self._add_chain(entry, cell, j, True)
1449 self._replace_or_copy_step()
1451 if tmp_off[j]:
1452 for cell in _iter_bits(tmp_off[j]):
1453 self._global_step.reset()
1454 self._global_step.type = SolutionType.FORCING_CHAIN_VERITY
1455 self._global_step.add_candidate_to_delete(cell, j)
1456 self._reset_tmp_chains()
1457 for entry in entry_list:
1458 self._add_chain(entry, cell, j, False)
1459 self._replace_or_copy_step()
1461 # ------------------------------------------------------------------
1462 # Chain reconstruction
1463 # ------------------------------------------------------------------
1465 def _reset_tmp_chains(self) -> None:
1466 """Reset chain workspace before building chains for a step."""
1467 self._tmp_chains_index = 0
1469 def _build_chain(self, entry: TableEntry, cell_index: int, cand: int, is_set: bool) -> None:
1470 """Build a chain from the implication back to the premise.
1472 Populates self._chain / self._chain_index with entries in reverse
1473 order (from implication back to premise). Also populates self._mins
1474 for net branches.
1476 Mirrors TablingSolver.buildChain() in Java.
1477 """
1478 self._chain_index = 0
1479 chain_entry = make_entry_simple(cell_index, cand, is_set)
1481 # Find the entry in the table
1482 index = -1
1483 for i in range(entry.index):
1484 if entry.entries[i] == chain_entry:
1485 index = i
1486 break
1488 if index == -1:
1489 return
1491 # Reset net data structures
1492 self._act_min = 0
1493 for i in range(len(self._min_indexes)):
1494 self._min_indexes[i] = 0
1496 # Build the main chain — collect cells in _build_chain_set for
1497 # early termination when building net parts (mirrors Java's tmpSetC)
1498 self._build_chain_set = 0
1499 self._chain_index = self._build_chain_inner(
1500 entry, index, self._chain, False
1501 )
1503 # Build net parts — reuse _build_chain_set so mins stop when
1504 # they reach a cell already in the main chain
1505 min_index = 0
1506 while min_index < self._act_min:
1507 entry_val = self._mins[min_index][0]
1508 try:
1509 ei = entry.get_entry_index_by_value(entry_val)
1510 except KeyError:
1511 min_index += 1
1512 continue
1513 self._min_indexes[min_index] = self._build_chain_inner(
1514 entry, ei, self._mins[min_index], True
1515 )
1516 min_index += 1
1518 def _build_chain_inner(
1519 self,
1520 entry: TableEntry,
1521 entry_index: int,
1522 act_chain: list[int],
1523 is_min: bool,
1524 ) -> int:
1525 """Walk retIndices backwards to construct a chain.
1527 Returns the number of entries written to act_chain.
1528 Mirrors the inner buildChain() in Java.
1530 Uses self._build_chain_set (an 81-bit cell bitmask) to track cells
1531 in the main chain. When *is_min* is True the walk stops early as
1532 soon as it reaches a cell that is already in the main chain AND the
1533 exact entry matches an entry in self._chain (mirrors Java's
1534 chainSet pre-selection + linear search).
1535 """
1536 act_chain_index = 0
1537 act_chain[act_chain_index] = entry.entries[entry_index]
1538 act_chain_index += 1
1539 first_entry_index = entry_index
1540 expanded = False
1541 org_entry = entry
1543 while first_entry_index != 0 and act_chain_index < len(act_chain):
1544 if entry.is_expanded(first_entry_index):
1545 # Jump to the source table
1546 src_idx = org_entry.get_ret_index(first_entry_index, 0)
1547 if entry.is_extended_table(first_entry_index):
1548 entry = self.extended_table[src_idx]
1549 elif entry.is_on_table(first_entry_index):
1550 entry = self.on_table[src_idx]
1551 else:
1552 entry = self.off_table[src_idx]
1553 expanded = True
1554 # Find this entry's value in the source table
1555 try:
1556 first_entry_index = entry.get_entry_index_by_value(
1557 org_entry.entries[first_entry_index]
1558 )
1559 except KeyError:
1560 break
1562 tmp_entry_index = first_entry_index
1563 for i in range(5):
1564 ret_idx = entry.get_ret_index(tmp_entry_index, i)
1565 if i == 0:
1566 first_entry_index = ret_idx
1567 if ret_idx < len(entry.entries):
1568 act_chain[act_chain_index] = entry.entries[ret_idx]
1569 act_chain_index += 1
1570 else:
1571 break
1573 if not is_min:
1574 # Main chain: record cell in chain_set
1575 cell_idx = get_cell_index(entry.entries[ret_idx])
1576 self._build_chain_set |= 1 << cell_idx
1577 node_type = get_node_type(entry.entries[ret_idx])
1578 if node_type == GROUP_NODE:
1579 ci2 = get_cell_index2(entry.entries[ret_idx])
1580 if ci2 != -1:
1581 self._build_chain_set |= 1 << ci2
1582 ci3 = get_cell_index3(entry.entries[ret_idx])
1583 if ci3 != -1:
1584 self._build_chain_set |= 1 << ci3
1585 elif node_type == ALS_NODE:
1586 als_idx = get_als_index(entry.entries[ret_idx])
1587 if als_idx < len(self._alses):
1588 self._build_chain_set |= self._alses[als_idx].indices
1589 else:
1590 # Min chain: check if we've reached the main chain
1591 cell_idx = get_cell_index(entry.entries[ret_idx])
1592 if self._build_chain_set & (1 << cell_idx):
1593 # Pre-selection hit — search main chain for exact match
1594 entry_val = entry.entries[ret_idx]
1595 for j in range(self._chain_index):
1596 if self._chain[j] == entry_val:
1597 return act_chain_index
1598 else:
1599 # Net branch (multiple inference)
1600 if ret_idx != 0 and not is_min:
1601 if self._act_min < len(self._mins):
1602 self._mins[self._act_min][0] = entry.entries[ret_idx]
1603 self._min_indexes[self._act_min] = 1
1604 self._act_min += 1
1606 if expanded and first_entry_index == 0:
1607 # Jumped to another table and reached its start → jump back
1608 ret_entry = entry.entries[0]
1609 entry = org_entry
1610 try:
1611 first_entry_index = entry.get_entry_index_by_value(ret_entry)
1612 except KeyError:
1613 break
1614 expanded = False
1616 return act_chain_index
1618 def _add_chain(
1619 self, entry: TableEntry, cell_index: int, cand: int, is_set: bool,
1620 is_nice_loop: bool = False, is_aic: bool = False,
1621 ) -> None:
1622 """Build and add a chain to the global step.
1624 Mirrors TablingSolver.addChain() — builds the chain backwards then
1625 reverses it, checking for lassos along the way.
1627 is_nice_loop: lasso detection allowing start cell at both ends.
1628 is_aic: stricter lasso detection (no return to start cell allowed).
1629 """
1630 if self._tmp_chains_index >= len(self._tmp_chains):
1631 return
1633 self._build_chain(entry, cell_index, cand, is_set)
1635 if self._chain_index == 0:
1636 return
1638 j = 0
1639 if is_nice_loop or is_aic:
1640 lasso_cells: int = 0 # 81-bit bitmask
1641 # For nice loops: first and second chain entries must differ in cell
1642 if is_nice_loop:
1643 c0 = get_cell_index(self._chain[0])
1644 c1 = get_cell_index(self._chain[1]) if self._chain_index > 1 else -1
1645 if c0 == c1:
1646 return
1648 last_cell_index = -1
1649 last_cell_entry = -1
1650 first_cell_index = get_cell_index(self._chain[self._chain_index - 1])
1652 # Reverse the chain and check for lassos
1653 for i in range(self._chain_index - 1, -1, -1):
1654 old_entry = self._chain[i]
1655 new_cell_index = get_cell_index(old_entry)
1657 if is_nice_loop or is_aic:
1658 if lasso_cells & (1 << new_cell_index):
1659 return # lasso detected
1661 # Add last cell to lasso set (skip start cell for nice loops)
1662 if last_cell_index != -1 and (last_cell_index != first_cell_index or is_aic):
1663 lasso_cells |= 1 << last_cell_index
1664 # Group nodes: add all cells
1665 if get_node_type(last_cell_entry) == GROUP_NODE:
1666 ci2 = get_cell_index2(last_cell_entry)
1667 if ci2 != -1:
1668 lasso_cells |= 1 << ci2
1669 ci3 = get_cell_index3(last_cell_entry)
1670 if ci3 != -1:
1671 lasso_cells |= 1 << ci3
1672 elif get_node_type(last_cell_entry) == ALS_NODE:
1673 als_idx = get_als_index(last_cell_entry)
1674 if als_idx < len(self._alses):
1675 lasso_cells |= self._alses[als_idx].indices
1677 last_cell_index = new_cell_index
1678 last_cell_entry = old_entry
1679 self._tmp_chain[j] = old_entry
1680 j += 1
1681 # Check for net branches (mins)
1682 for k in range(self._act_min):
1683 if self._mins[k][self._min_indexes[k] - 1] == old_entry:
1684 for m in range(self._min_indexes[k] - 2, -1, -1):
1685 self._tmp_chain[j] = -self._mins[k][m]
1686 j += 1
1687 self._tmp_chain[j] = -(1 << 31)
1688 j += 1
1690 if j > 0:
1691 chain_data = self._tmp_chain[:j]
1692 if self._tmp_chains_index < len(self._tmp_chains):
1693 self._tmp_chains[self._tmp_chains_index] = list(chain_data)
1694 self._global_step.chains.append(list(chain_data))
1695 self._tmp_chains_index += 1
1697 # Collect chain cells for continuous nice loop elimination checking
1698 if is_nice_loop:
1699 self._chain_set = 0
1700 for ci in range(j):
1701 ev = chain_data[ci]
1702 if ev < 0:
1703 continue # net branch marker
1704 self._chain_set |= 1 << get_cell_index(ev)
1705 nt = get_node_type(ev)
1706 if nt == GROUP_NODE:
1707 ci2 = get_cell_index2(ev)
1708 if ci2 != -1:
1709 self._chain_set |= 1 << ci2
1710 ci3 = get_cell_index3(ev)
1711 if ci3 != -1:
1712 self._chain_set |= 1 << ci3
1713 elif nt == ALS_NODE:
1714 aidx = get_als_index(ev)
1715 if aidx < len(self._alses):
1716 self._chain_set |= self._alses[aidx].indices
1718 # ------------------------------------------------------------------
1719 # Dedup and step management
1720 # ------------------------------------------------------------------
1722 def _adjust_type(self, step: SolutionStep) -> None:
1723 """Upgrade FORCING_CHAIN to FORCING_NET if the step is a net.
1725 Mirrors Java's adjustType() which checks step.isNet() — true when
1726 any chain entry is negative (net branch marker).
1727 """
1728 if step.is_net():
1729 if step.type == SolutionType.FORCING_CHAIN_CONTRADICTION:
1730 step.type = SolutionType.FORCING_NET_CONTRADICTION
1731 elif step.type == SolutionType.FORCING_CHAIN_VERITY:
1732 step.type = SolutionType.FORCING_NET_VERITY
1734 def _replace_or_copy_step(self) -> None:
1735 """Add globalStep to steps list, deduplicating by candidate string.
1737 If a step with the same eliminations/placements already exists and has
1738 shorter chains, keep the old one. Otherwise replace or add.
1739 """
1740 step = self._global_step
1741 self._adjust_type(step)
1743 # In net mode, discard steps that are still CHAIN type (not promoted
1744 # to NET by adjustType). These were already found during chain mode.
1745 # Mirrors Java lines 1007-1011 in replaceOrCopyStep().
1746 if self._nets_mode and step.type in (
1747 SolutionType.FORCING_CHAIN_CONTRADICTION,
1748 SolutionType.FORCING_CHAIN_VERITY,
1749 ):
1750 return
1752 # Determine the dedup key
1753 if step.candidates_to_delete:
1754 del_key = step.get_candidate_string()
1755 elif step.indices:
1756 del_key = step.get_single_candidate_string()
1757 else:
1758 return # no effect
1760 if self._only_one_chain_per_elimination:
1761 old_index = self.deletes_map.get(del_key)
1762 if old_index is not None:
1763 old_step = self.steps[old_index]
1764 if old_step.get_chain_length() > step.get_chain_length():
1765 # New chain is shorter → replace
1766 self.steps[old_index] = copy.deepcopy(step)
1767 return
1769 # New step
1770 self.deletes_map[del_key] = len(self.steps)
1771 self.steps.append(copy.deepcopy(step))
1773 # ------------------------------------------------------------------
1774 # Nice Loop / AIC detection via tabling
1775 # ------------------------------------------------------------------
1777 def find_all_nice_loops(
1778 self,
1779 with_group_nodes: bool = True,
1780 with_als_nodes: bool = False,
1781 only_grouped: bool = True,
1782 target_type: SolutionType | None = None,
1783 ) -> list[SolutionStep]:
1784 """Find all nice loops / AICs using the tabling framework.
1786 Mirrors TablingSolver.getAllNiceLoops() and getAllGroupedNiceLoops()
1787 in Java.
1789 with_group_nodes: include group node entries in tables
1790 only_grouped: if True, only return grouped NL/AIC steps
1791 target_type: filter results to this specific type
1792 """
1793 self.steps.clear()
1794 self.deletes_map.clear()
1795 self._only_grouped_nice_loops = only_grouped
1797 # Fill tables
1798 self._fill_tables()
1799 if with_group_nodes:
1800 self._fill_tables_with_group_nodes()
1801 if with_als_nodes:
1802 self._fill_tables_with_als()
1804 # Expand tables
1805 self._expand_tables(self.on_table)
1806 self._expand_tables(self.off_table)
1808 # Check for nice loops and AICs
1809 self._check_nice_loops(self.on_table)
1810 self._check_nice_loops(self.off_table)
1811 self._check_aics(self.off_table)
1813 self._only_grouped_nice_loops = False
1815 # Filter to target type if specified
1816 if target_type is not None:
1817 return [s for s in self.steps if s.type == target_type]
1819 self.steps.sort(key=_tabling_sort_key)
1820 return list(self.steps)
1822 def _check_nice_loops(self, table: list[TableEntry]) -> None:
1823 """Check all table entries for nice loops.
1825 Mirrors TablingSolver.checkNiceLoops() in Java.
1826 """
1827 for i in range(len(table)):
1828 if table[i].index == 0:
1829 continue
1830 start_index = table[i].get_cell_index(0)
1831 for j in range(1, table[i].index):
1832 if table[i].entries[j] == 0:
1833 break
1834 if (table[i].get_node_type(j) == NORMAL_NODE
1835 and table[i].get_cell_index(j) == start_index):
1836 self._check_nice_loop(table[i], j)
1838 def _check_nice_loop(self, entry: TableEntry, entry_index: int) -> None:
1839 """Check if a loop forms a valid nice loop and determine eliminations.
1841 Mirrors TablingSolver.checkNiceLoop() in Java.
1842 """
1843 if entry.get_distance(entry_index) <= 2:
1844 return
1846 grid = self.grid
1847 self._global_step.reset()
1848 self._global_step.type = SolutionType.DISCONTINUOUS_NICE_LOOP
1849 self._reset_tmp_chains()
1850 self._add_chain(
1851 entry, entry.get_cell_index(entry_index),
1852 entry.get_candidate(entry_index), entry.is_strong(entry_index),
1853 is_nice_loop=True,
1854 )
1855 if not self._global_step.chains:
1856 return
1858 nl_chain = self._global_step.chains[0]
1859 nl_chain_index = len(nl_chain) - 1
1860 nl_chain_length = len(nl_chain)
1862 if get_cell_index(nl_chain[0]) == get_cell_index(nl_chain[1]):
1863 return # first link must leave start cell
1865 first_link_strong = entry.is_strong(1)
1866 last_link_strong = entry.is_strong(entry_index)
1867 start_candidate = entry.get_candidate(0)
1868 end_candidate = entry.get_candidate(entry_index)
1869 start_index = entry.get_cell_index(0)
1871 if not first_link_strong and not last_link_strong and start_candidate == end_candidate:
1872 # Discontinuous: eliminate startCandidate from startIndex
1873 self._global_step.add_candidate_to_delete(start_index, start_candidate)
1875 elif first_link_strong and last_link_strong and start_candidate == end_candidate:
1876 # Discontinuous: eliminate all except startCandidate
1877 for d in range(1, 10):
1878 if grid.candidates[start_index] & DIGIT_MASKS[d] and d != start_candidate:
1879 self._global_step.add_candidate_to_delete(start_index, d)
1881 elif first_link_strong != last_link_strong and start_candidate != end_candidate:
1882 # Discontinuous: eliminate the weak-link candidate
1883 if not first_link_strong:
1884 self._global_step.add_candidate_to_delete(start_index, start_candidate)
1885 else:
1886 self._global_step.add_candidate_to_delete(start_index, end_candidate)
1888 elif ((not first_link_strong and not last_link_strong
1889 and grid.candidates[start_index].bit_count() == 2
1890 and start_candidate != end_candidate)
1891 or (first_link_strong and last_link_strong
1892 and start_candidate != end_candidate)
1893 or (first_link_strong != last_link_strong
1894 and start_candidate == end_candidate)):
1895 # Continuous nice loop
1896 self._global_step.type = SolutionType.CONTINUOUS_NICE_LOOP
1897 self._check_continuous_nl_eliminations(
1898 nl_chain, nl_chain_index, start_index,
1899 start_candidate, end_candidate,
1900 first_link_strong, last_link_strong,
1901 )
1902 else:
1903 return # not a valid loop type
1905 if not self._global_step.candidates_to_delete:
1906 return
1908 # Check for grouped nodes
1909 grouped = any(
1910 get_node_type(nl_chain[i]) != NORMAL_NODE
1911 for i in range(len(nl_chain))
1912 if nl_chain[i] >= 0
1913 )
1914 if grouped:
1915 if self._global_step.type == SolutionType.DISCONTINUOUS_NICE_LOOP:
1916 self._global_step.type = SolutionType.GROUPED_DISCONTINUOUS_NICE_LOOP
1917 elif self._global_step.type == SolutionType.CONTINUOUS_NICE_LOOP:
1918 self._global_step.type = SolutionType.GROUPED_CONTINUOUS_NICE_LOOP
1920 if self._only_grouped_nice_loops and not grouped:
1921 return
1923 # Dedup by elimination set
1924 del_key = self._global_step.get_candidate_string()
1925 if self._only_one_chain_per_elimination:
1926 old_index = self.deletes_map.get(del_key)
1927 if old_index is not None:
1928 if self.steps[old_index].get_chain_length() <= nl_chain_length:
1929 return
1931 self.deletes_map[del_key] = len(self.steps)
1932 self.steps.append(copy.deepcopy(self._global_step))
1934 def _check_continuous_nl_eliminations(
1935 self,
1936 nl_chain: list[int],
1937 nl_chain_index: int,
1938 start_index: int,
1939 start_candidate: int,
1940 end_candidate: int,
1941 first_link_strong: bool,
1942 last_link_strong: bool,
1943 ) -> None:
1944 """Find eliminations for a continuous nice loop.
1946 Mirrors the CNL elimination logic in TablingSolver.checkNiceLoop().
1947 """
1948 grid = self.grid
1949 alses = self._alses
1951 for i in range(nl_chain_index + 1):
1952 ev = nl_chain[i]
1953 if ev < 0:
1954 continue # net branch marker
1956 # Cell with two strong links → eliminate all except strong link cands
1957 if (i == 0 and first_link_strong and last_link_strong) or \
1958 (i > 0 and is_strong(nl_chain[i]) and i <= nl_chain_index - 2
1959 and get_cell_index(nl_chain[i - 1]) != get_cell_index(nl_chain[i])): # noqa: E129
1961 if i == 0 or (
1962 not is_strong(nl_chain[i + 1])
1963 and get_cell_index(nl_chain[i]) == get_cell_index(nl_chain[i + 1])
1964 and is_strong(nl_chain[i + 2])
1965 and get_cell_index(nl_chain[i + 1]) != get_cell_index(nl_chain[i + 2])
1966 ):
1967 if i == 0:
1968 c1, c2 = start_candidate, end_candidate
1969 else:
1970 c1 = get_candidate(nl_chain[i])
1971 c2 = get_candidate(nl_chain[i + 2])
1972 cell = get_cell_index(nl_chain[i])
1973 for d in range(1, 10):
1974 if grid.candidates[cell] & DIGIT_MASKS[d] and d != c1 and d != c2:
1975 self._global_step.add_candidate_to_delete(cell, d)
1977 # Weak link between cells
1978 if i > 0 and not is_strong(nl_chain[i]) \
1979 and get_cell_index(nl_chain[i - 1]) != get_cell_index(nl_chain[i]):
1980 act_cand = get_candidate(nl_chain[i])
1981 # Get buddies for both endpoints of the weak link
1982 buddies_prev = _get_node_buddies(nl_chain[i - 1], act_cand, alses)
1983 buddies_curr = _get_node_buddies(nl_chain[i], act_cand, alses)
1984 common = buddies_prev & buddies_curr
1985 common &= ~self._chain_set
1986 common &= ~(1 << start_index)
1987 common &= grid.candidate_sets[act_cand]
1988 for cell in _iter_bits(common):
1989 self._global_step.add_candidate_to_delete(cell, act_cand)
1991 # ALS node: additional eliminations for non-RC candidates
1992 if get_node_type(nl_chain[i]) == ALS_NODE:
1993 als_idx = get_als_index(nl_chain[i])
1994 if als_idx < len(alses):
1995 als = alses[als_idx]
1996 # Check if the exit is forced (next link is strong)
1997 is_force_exit = (
1998 i < nl_chain_index and is_strong(nl_chain[i + 1])
1999 )
2000 next_cell_index = get_cell_index(nl_chain[i + 1]) if i < nl_chain_index else -1
2001 exit_cands: int = 0 # bitmask of exit candidates
2002 if is_force_exit:
2003 force_cand = get_candidate(nl_chain[i + 1])
2004 exit_cands = grid.candidates[next_cell_index] & ~DIGIT_MASKS[force_cand]
2005 elif i < nl_chain_index:
2006 exit_cands = DIGIT_MASKS[get_candidate(nl_chain[i + 1])]
2008 # Eliminate non-RC, non-exit candidates
2009 for d in range(1, 10):
2010 if DIGIT_MASKS[d] & exit_cands:
2011 continue
2012 if d == act_cand:
2013 continue
2014 if not als.buddies_per_cand[d]:
2015 continue
2016 elim = als.buddies_per_cand[d] & grid.candidate_sets[d]
2017 for cell in _iter_bits(elim):
2018 self._global_step.add_candidate_to_delete(cell, d)
2020 # Force exit: exit candidates eliminate via combined buddies
2021 if is_force_exit:
2022 next_buddies = BUDDIES[next_cell_index]
2023 tmp_exit = exit_cands
2024 while tmp_exit:
2025 lsb = tmp_exit & -tmp_exit
2026 d = lsb.bit_length()
2027 tmp_exit ^= lsb
2028 elim = als.buddies_per_cand[d] & next_buddies
2029 elim &= grid.candidate_sets[d]
2030 for cell in _iter_bits(elim):
2031 self._global_step.add_candidate_to_delete(cell, d)
2033 def _check_aics(self, table: list[TableEntry]) -> None:
2034 """Check off_table entries for AIC patterns.
2036 Mirrors TablingSolver.checkAics() in Java.
2037 AICs start with a strong link (off-table premise leads to ON entries).
2038 """
2039 grid = self.grid
2040 for i in range(len(table)):
2041 if table[i].index == 0:
2042 continue
2043 start_index = table[i].get_cell_index(0)
2044 start_candidate = table[i].get_candidate(0)
2045 start_buddies = BUDDIES[start_index]
2047 for j in range(1, table[i].index):
2048 if table[i].entries[j] == 0:
2049 break
2050 if (table[i].get_node_type(j) != NORMAL_NODE
2051 or not table[i].is_strong(j)
2052 or table[i].get_cell_index(j) == start_index):
2053 continue
2055 end_index = table[i].get_cell_index(j)
2056 end_candidate = table[i].get_candidate(j)
2058 if start_candidate == end_candidate:
2059 # Type 1: same candidate at both ends
2060 common = start_buddies & BUDDIES[end_index]
2061 common &= grid.candidate_sets[start_candidate]
2062 if common and _bit_count(common) >= 2:
2063 self._check_aic(table[i], j)
2064 else:
2065 # Type 2: different candidates, endpoints see each other
2066 if not (start_buddies & (1 << end_index)):
2067 continue
2068 if (grid.candidates[end_index] & DIGIT_MASKS[start_candidate]
2069 and grid.candidates[start_index] & DIGIT_MASKS[end_candidate]):
2070 self._check_aic(table[i], j)
2072 def _check_aic(self, entry: TableEntry, entry_index: int) -> None:
2073 """Build an AIC step and add to results.
2075 Mirrors TablingSolver.checkAic() in Java.
2076 """
2077 if entry.get_distance(entry_index) <= 2:
2078 return
2080 grid = self.grid
2081 self._global_step.reset()
2082 self._global_step.type = SolutionType.AIC
2084 start_candidate = entry.get_candidate(0)
2085 end_candidate = entry.get_candidate(entry_index)
2086 start_index = entry.get_cell_index(0)
2087 end_index = entry.get_cell_index(entry_index)
2089 if start_candidate == end_candidate:
2090 # Type 1: eliminate from cells seeing both endpoints
2091 common = BUDDIES[start_index] & BUDDIES[end_index]
2092 common &= grid.candidate_sets[start_candidate]
2093 if _bit_count(common) > 1:
2094 for cell in _iter_bits(common):
2095 if cell != start_index:
2096 self._global_step.add_candidate_to_delete(cell, start_candidate)
2097 else:
2098 # Type 2: cross-elimination
2099 if grid.candidates[start_index] & DIGIT_MASKS[end_candidate]:
2100 self._global_step.add_candidate_to_delete(start_index, end_candidate)
2101 if grid.candidates[end_index] & DIGIT_MASKS[start_candidate]:
2102 self._global_step.add_candidate_to_delete(end_index, start_candidate)
2104 if not self._global_step.candidates_to_delete:
2105 return
2107 self._reset_tmp_chains()
2108 self._add_chain(
2109 entry, entry.get_cell_index(entry_index),
2110 entry.get_candidate(entry_index), entry.is_strong(entry_index),
2111 is_aic=True,
2112 )
2113 if not self._global_step.chains:
2114 return
2116 chain = self._global_step.chains[0]
2118 grouped = any(
2119 get_node_type(chain[ci]) != NORMAL_NODE
2120 for ci in range(len(chain))
2121 if chain[ci] >= 0
2122 )
2123 if grouped:
2124 if self._global_step.type == SolutionType.AIC:
2125 self._global_step.type = SolutionType.GROUPED_AIC
2127 if self._only_grouped_nice_loops and not grouped:
2128 return
2130 del_key = self._global_step.get_candidate_string()
2131 if self._only_one_chain_per_elimination:
2132 old_index = self.deletes_map.get(del_key)
2133 if old_index is not None:
2134 if self.steps[old_index].get_chain_length() <= len(chain):
2135 return
2137 self.deletes_map[del_key] = len(self.steps)
2138 self.steps.append(copy.deepcopy(self._global_step))
2141# ---------------------------------------------------------------------------
2142# Node buddies helper (matching Chain.getSNodeBuddies in Java)
2143# ---------------------------------------------------------------------------
2145def _get_node_buddies(entry: int, candidate: int, alses: list[Als]) -> int:
2146 """Get the buddy set for a chain node entry.
2148 For normal nodes: buddies of the cell.
2149 For group nodes: intersection of buddies of all cells.
2150 For ALS nodes: buddiesPerCandidat[candidate] for the ALS.
2151 """
2152 nt = get_node_type(entry)
2153 if nt == NORMAL_NODE:
2154 return BUDDIES[get_cell_index(entry)]
2155 elif nt == GROUP_NODE:
2156 result = BUDDIES[get_cell_index(entry)]
2157 ci2 = get_cell_index2(entry)
2158 if ci2 != -1:
2159 result &= BUDDIES[ci2]
2160 ci3 = get_cell_index3(entry)
2161 if ci3 != -1:
2162 result &= BUDDIES[ci3]
2163 return result
2164 elif nt == ALS_NODE:
2165 als_idx = get_als_index(entry)
2166 if als_idx < len(alses):
2167 return alses[als_idx].buddies_per_cand[candidate]
2168 return 0
2171# ---------------------------------------------------------------------------
2172# Sorting key for tabling steps (TablingComparator)
2173# ---------------------------------------------------------------------------
2175def _tabling_sort_cmp(o1: SolutionStep, o2: SolutionStep) -> int:
2176 """Comparator matching Java's SolutionStep.compareTo() exactly.
2178 This is used by Collections.sort(steps) in TablingSolver.getNiceLoops().
2180 Order:
2181 1. Singles (set-cell) before elimination steps
2182 2. More candidates to delete first (descending count)
2183 3. If not equivalent: compare by getIndexSumme (weighted sum of candidates)
2184 4. If equivalent: special fish handling, then chain length, values, indices
2185 """
2186 # Singles first
2187 single1 = _is_single(o1.type)
2188 single2 = _is_single(o2.type)
2189 if single1 and not single2:
2190 return -1
2191 if not single1 and single2:
2192 return 1
2194 # More candidates to delete first (descending)
2195 result = len(o2.candidates_to_delete) - len(o1.candidates_to_delete)
2196 if result != 0:
2197 return result
2199 # Equivalency check
2200 if not _is_equivalent(o1, o2):
2201 sum1 = _get_index_summe(o1.candidates_to_delete)
2202 sum2 = _get_index_summe(o2.candidates_to_delete)
2203 return sum1 - sum2
2205 # SPECIAL: fish steps
2206 if _is_fish(o1.type) and _is_fish(o2.type):
2207 # fish type/size comparison, cannibalism, endo fins, fins, values
2208 ret = _compare_fish_types(o1.type, o2.type)
2209 if ret != 0:
2210 return ret
2211 # Skip cannibalistic/fins/endo_fins comparisons for now (rarely relevant)
2212 if o1.values != o2.values:
2213 return sum(o1.values) - sum(o2.values)
2214 return 0
2216 # Chain length (ascending — shorter is better)
2217 chain_diff = o1.get_chain_length() - o2.get_chain_length()
2218 if chain_diff != 0:
2219 return chain_diff
2221 # Values comparison — Java uses isEqualInteger (set equality)
2222 if not _same_integers(o1.values, o2.values):
2223 return sum(o1.values) - sum(o2.values)
2225 # Indices comparison — Java uses isEqualInteger (set equality)
2226 if not _same_integers(o1.indices, o2.indices):
2227 # Java: indices.size() - o.indices.size() (ascending)
2228 if len(o1.indices) != len(o2.indices):
2229 return len(o1.indices) - len(o2.indices)
2230 # Java: sum2 - sum1 (descending)
2231 return sum(o2.indices) - sum(o1.indices)
2233 # Final tiebreaker: type comparison
2234 # Java: return type.compare(o.getType()) which uses step config index
2235 return _compare_types(o1.type, o2.type)
2238def _is_single(t: SolutionType) -> bool:
2239 """Check if a SolutionType is a single (placement) type."""
2240 name = t.name
2241 return name in ('FULL_HOUSE', 'HIDDEN_SINGLE', 'NAKED_SINGLE')
2244def _is_equivalent(o1: SolutionStep, o2: SolutionStep) -> bool:
2245 """Check if two steps are equivalent (same type and same effects).
2247 Mirrors Java SolutionStep.isEquivalent().
2248 """
2249 t1, t2 = o1.type, o2.type
2250 if _is_fish(t1) and _is_fish(t2):
2251 return True
2252 if _is_kraken_fish(t1) and _is_kraken_fish(t2):
2253 return True
2254 if t1 != t2:
2255 return False
2256 if o1.candidates_to_delete:
2257 return _same_candidates(o1.candidates_to_delete, o2.candidates_to_delete)
2258 # Java uses isEqualInteger which is set equality (order-independent)
2259 return _same_integers(o1.indices, o2.indices)
2262def _same_candidates(a: list, b: list) -> bool:
2263 """Check if two candidate lists have the same (index, value) pairs.
2265 Uses set-equality (order-independent) to match Java's isEqualCandidate().
2266 """
2267 if len(a) != len(b):
2268 return False
2269 # O(n^2) set comparison matching Java exactly
2270 for c1 in a:
2271 found = False
2272 for c2 in b:
2273 if c1.index == c2.index and c1.value == c2.value:
2274 found = True
2275 break
2276 if not found:
2277 return False
2278 return True
2281def _same_integers(a: list[int], b: list[int]) -> bool:
2282 """Set-equality check for integer lists, matching Java's isEqualInteger().
2284 Order-independent: [1, 2] == [2, 1].
2285 """
2286 if len(a) != len(b):
2287 return False
2288 for v in a:
2289 if v not in b:
2290 return False
2291 return True
2294def _compare_types(t1: SolutionType, t2: SolutionType) -> int:
2295 """Compare types by solver step config index.
2297 Mirrors Java SolutionType.compare() for non-fish types.
2298 """
2299 from hodoku.core.scoring import STEP_CONFIG
2300 c1 = STEP_CONFIG.get(t1)
2301 c2 = STEP_CONFIG.get(t2)
2302 idx1 = c1.index if c1 else 0
2303 idx2 = c2.index if c2 else 0
2304 return idx1 - idx2
2307def _compare_candidates_sorted(o1: SolutionStep, o2: SolutionStep) -> int:
2308 """Compare candidate-to-delete lists element-by-element, using sorted order.
2310 Both lists are sorted by (index, value) before comparison, making the
2311 result independent of the order in which candidates were discovered.
2312 """
2313 s1 = sorted(o1.candidates_to_delete, key=lambda c: (c.index, c.value))
2314 s2 = sorted(o2.candidates_to_delete, key=lambda c: (c.index, c.value))
2315 if len(s1) != len(s2):
2316 return len(s2) - len(s1)
2317 for c1, c2 in zip(s1, s2):
2318 result = (c1.index * 10 + c1.value) - (c2.index * 10 + c2.value)
2319 if result != 0:
2320 return result
2321 return 0
2324def _get_index_summe(candidates: list) -> int:
2325 """Weighted sum of candidate indices, matching Java's getIndexSumme().
2327 Java's getCandidateString() sorts candidatesToDelete by (value, index) via
2328 Collections.sort before compareTo/getIndexSumme is ever called. So the
2329 weighted sum is computed over the *sorted* list, not insertion order.
2331 Uses increasing offset: first candidate weight=1, next=81, then=161, etc.
2332 """
2333 total = 0
2334 offset = 1
2335 for c in sorted(candidates, key=lambda c: (c.value, c.index)):
2336 total += c.index * offset + c.value
2337 offset += 80
2338 return total
2341def _is_fish(t: SolutionType) -> bool:
2342 """Check if a SolutionType is a fish type."""
2343 name = t.name
2344 return any(f in name for f in (
2345 'SWORDFISH', 'JELLYFISH', 'SQUIRMBAG', 'WHALE', 'LEVIATHAN',
2346 'X_WING',
2347 )) and 'KRAKEN' not in name
2350def _is_kraken_fish(t: SolutionType) -> bool:
2351 """Check if a SolutionType is a Kraken fish type."""
2352 return 'KRAKEN' in t.name
2355def _compare_fish_types(t1: SolutionType, t2: SolutionType) -> int:
2356 """Compare fish types by ordinal value."""
2357 # Use name-based ordering as a proxy for ordinal
2358 return 0 # Within equivalent fish, further comparison handled above
2361def _fc_sort_cmp(o1: SolutionStep, o2: SolutionStep) -> int:
2362 """Comparator matching Java's TablingComparator exactly.
2364 Used for forcing chains/nets (NOT nice loops).
2365 """
2366 has1 = len(o1.indices) > 0
2367 has2 = len(o2.indices) > 0
2369 if has1 and not has2:
2370 return -1
2371 if not has1 and has2:
2372 return 1
2374 if has1:
2375 # set cell — more cells first
2376 result = len(o2.indices) - len(o1.indices)
2377 if result != 0:
2378 return result
2379 if not _is_equivalent(o1, o2):
2380 sum1 = sum(o1.indices)
2381 sum2 = sum(o2.indices)
2382 return 1 if sum1 == sum2 else (sum1 - sum2)
2383 result = o1.get_chain_length() - o2.get_chain_length()
2384 if result != 0:
2385 return result
2386 else:
2387 result = len(o2.candidates_to_delete) - len(o1.candidates_to_delete)
2388 if result != 0:
2389 return result
2390 if not _is_equivalent(o1, o2):
2391 result = _compare_candidates_to_delete(o1, o2)
2392 if result != 0:
2393 return result
2394 result = o1.get_chain_length() - o2.get_chain_length()
2395 if result != 0:
2396 return result
2397 return 0
2400def _compare_candidates_to_delete(o1: SolutionStep, o2: SolutionStep) -> int:
2401 """Compare candidates element-by-element using index*10+value.
2403 Mirrors Java SolutionStep.compareCandidatesToDelete(). In Java, the
2404 candidatesToDelete lists are already sorted by (value, index) due to the
2405 getCandidateString() side effect, so we sort before comparing.
2406 """
2407 c1s = sorted(o1.candidates_to_delete, key=lambda c: (c.value, c.index))
2408 c2s = sorted(o2.candidates_to_delete, key=lambda c: (c.value, c.index))
2409 if len(c1s) != len(c2s):
2410 return len(c2s) - len(c1s)
2411 for c1, c2 in zip(c1s, c2s):
2412 result = (c1.index * 10 + c1.value) - (c2.index * 10 + c2.value)
2413 if result != 0:
2414 return result
2415 return 0
2418import functools # noqa: E402
2419_tabling_sort_key = functools.cmp_to_key(_tabling_sort_cmp)
2420_fc_sort_key = functools.cmp_to_key(_fc_sort_cmp)
2423def _chain_length(step: SolutionStep) -> int:
2424 """Total chain length across all chains in the step."""
2425 total = 0
2426 for chain in step.chains:
2427 total += len(chain)
2428 return total
2431# ---------------------------------------------------------------------------
2432# Helper for expand_tables — single-index retIndex
2433# ---------------------------------------------------------------------------
2435def _make_ret_index_single(index: int) -> int:
2436 """Create a retIndex with only index1 set (no other predecessors)."""
2437 if index > 4096:
2438 index = 0
2439 return index