The solver

The techniques, moves, pricing parameters and the Solver class. Generated from the comments in the headers by Doxygen and tools/gen_cpp_reference.py; public members only.

solver.hpp

csrc/solver.hpp

Two-phase logical solver: technique ids, moves, pricing parameters and the Solver class (solver.cpp and the technique files).

struct Cover

source

Fields

• kind int
• shape double
• u int

struct Move

source

One move: the feature tuple (tech, base_shape, cover, extra, meta) plus placement / eliminations.

cover and elims live in the owning buffer.

Fields

• tech int
• shape double
• cov_off int
• cov_n int
• extra int
• has_meta bool
• meta int[8] — cells groups digits links hidden arith relation notes
• spread double
• meta_synth bool — meta[] filled by describe() for export only (the technique is priced by B)
• has_desc bool — desc[] is filled
• desc double[8] — structural descriptors (desc.cpp): log branches, log depth, search, uniqueness, counting, contradiction, held, coverage exported, not priced
• scan double — desc.cpp: patterns of this kind a human scans at the state (raw count behind desc[2])
• enumv double — log1p(max consistent assignments of the SUM rule instances the move touches)
• pc int
• pv int — placement
• el_off int
• el_n int
• nk int
• na int
• nb int — nb: second group / cage (-1 = none)
• d double
• xm pm_long[XM_N]
• code int
• tab_live pm_long — table-backed move: live tuples of the justifying table (case-analysis burden)
• pat_off int
• pat_n int — pattern cells (cells justifying the move) in MoveBuf::pats
• load float[8] — cognitive loads (human mode), see Solver::cog_loads; LOAD_N entries
• has_load bool
• ex_off int
• ex_n int — explanation records in MoveBuf::ex: [tag, len, data...]...

struct MoveBuf

source

Name	What it does
clear

Fields

• moves std::vector< Move >
• covers std::vector< Cover >
• elims std::vector< uint32_t > — c*32 + v
• pats std::vector< int > — pattern cells
• ex std::vector< int > — explanation records

void clear()

source

No comment.

struct Params

source

Name	What it does
size	board-size factor ((D - 1) / 8)^alpha scaling the prices
difficulty	price of a move: the technique's base cost with shape, size and covers (or the structural meta model)

Fields

• B double[N_TECH]
• K std::vector< double >
• gamma double
• alpha double
• theta std::vector< double > — meta_theta (empty = per-technique B path)
• theta_full std::vector< double > — params meta_theta_full: 18-19 weights pricing every technique (empty = off)
• locality double — params locality: route choice by price x exp(locality x log2(1 + distance to the previous step)); 0 = off
• theta_enum double — params meta_theta_enum (D5): weight on Move::enumv inside the meta_theta_full price
• tech_obsc std::vector< double > — params tech_obscurity: per-technique log-price offset = cultural familiarity / obscurity (a property of the technique, measured from human outcomes); indexed by tech code
• theta_interact std::vector< double > — params meta_theta_interact 3 weights on log depth x log cells, log depth x links, log depth x log branches (added to the meta_theta_full sum)
• has_theta bool
• theta_ac double
• guess_k double — guessing / trial prices: Guess d = B[Guess] * size * (1 + guess_k * expected refutation work); a wrong candidate that survives basic propagation costs its steps + guess_deep * empty cells; Trial / ShortTrial d *= 1 + trial_k * (rounds - 1)
• trial_k double
• colour_chain_k double — ColourAlgebra chain multiplier (0 = off)
• k_tab double
• snyder bool — params notes_mode = "snyder": Snyder marks before full candidates
• snyder_max int — params snyder_max: Snyder marks for digits confined to <= 2 (default) or <= 3 cells of a box
• case_light int — params case_light: CaseAnalysis cases also run light techniques (intersections, pairs)
• case_rounds int
• case_cands int — params case_rounds (default 0 = off until a refit prices descriptors; 3 = on), case_cands
• dc_lines bool — params dc_lines: DigitCount uses line rules' must-contain digits
• mental_floor bool — params mental_floor: mental moves priced >= their written counterpart
• theta_full_v2 bool — params theta_full_v2: meta_theta_full uses log1p(links); the mental floor's written counterpart also sets coverage (desc[7]) = 1
• notes_lazy bool — params notes_lazy: candidates are written only for the cells a notes step uses
• sets_first bool — params route = "sets_first": chains / ALS tiers after the set-arithmetic tiers
• band_budget pm_long — BandLogic node budget per state (0 = off)
• band_k double — BandLogic: d *= 1 + band_k * log(cases) (refutation case count / search nodes)
• ri_budget pm_long — RuleIntersection node budget per state (0 = off) // table moves: d *= 1 + k_tab * log(live tuples)
• guess_deep int — meta interaction: arith x log(cells) (params "meta_theta_arith_cells")
• meta_max_tech int — meta-theta applies to technique codes below this (params "meta_max_tech")
• meta_excl bool[N_TECH] — ... and not to these codes (params "meta_exclude": B pricing)
• tech_offset double[N_TECH] — optional: meta-path difficulty *= exp(offset[tech])
• has_offset bool[N_TECH]
• human bool — human mode (params["human_mode"]): every family competes in the race (no tier gating within the direct / notes phase); difficulty *= exp(sum_j k_j * max(0, load_j - budget_j))
• cap_pow double — 0: beyond the cap d = cap + (d - cap)^cap_pow (steeper than log1p; 1 = uncapped)
• cap_tau double — soft guess cap: d > cap -> cap + tau * log1p((d - cap) / tau); 0 = hard cap
• hbudget double[8]
• hk double[8]
• fc_level int — forcing chains: highest level searched by the solver (-1 off, 0 static, 1 dynamic, 2 nested), last notes tier usable inside branches, max options per level; price d *= exp(fc_depth * level) * k^fc_branch * (1 + log1p(propagation steps))
• fc_ceiling int
• band_escalate int
• band_escalate_max int
• band_wide_factor int — params band_wide_factor: wide-region pass budget = this x band_budget
• colour_partial int — params colour_partial: partial structural colouring when the symbol puzzle is not unique
• band_outies int — params band_outies: derived house sums may subtract pieces' outie cells
• band_wide_rules int — params band_wide_rules: largest subset of sticking-out rules per wide region (2 or 3)
• band_wide_max int — params band_wide_max: at most this many wide regions (the smallest)
• band_wide_cells int — params band_wide_cells: escalation regions with rules taken whole, <= this many cells (0 = off) // params band_escalate (budget factor, <= 1 = off), band_escalate_max (per solve)
• fc_fallback pm_long — params forcing_fallback: work budget (branch steps per solve; default 5e4) for dynamic / nested
• refute_rounds int — forcing tried when a step would otherwise guess (0 = off) params refute_rounds: 1 = refute_profile counts propagation rounds (all singles of a round placed together: independent of cell order), 0 = placements (experiment, B1c)
• fish_max_n int — params fish_max_n: largest finned fish listed (the band path lists Medium with 2: larger finned fish are Hard, so they can't be picked there)
• exhaust_fallback int — params exhaust_fallback: 1 = where a step would guess (GUESS disabled), refute one candidate by full search instead (tech TRIAL, 'Trial and error', band Extreme)
• fc_fallback_s double — params forcing_fallback_s: wall-time safety per solve (checked between calls; the deterministic work budget is meant to bind first)
• fc_kmax int[3]
• fc_depth double
• fc_branch double
• gurth bool — Gurth's symmetry theorem (coordinate symmetries: not transform-invariant)
• fc_work double — budget: branches x (cells + 8 x rules); above it a level is skipped

double size(int D) const

source

board-size factor ((D - 1) / 8)^alpha scaling the prices

double difficulty(const Move &m, const Cover *covers, int D) const

source

price of a move: the technique's base cost with shape, size and covers (or the structural meta model)

struct StepRec

source

Fields

• alt_off int
• alt_n int
• chosen int
• mode int — 0 direct, 1 notes
• n_empty int
• erasures int
• notes_written int
• n_cands pm_long — candidates left in the empty cells before the step (engine view; Andrew Stuart's C)
• move Move — cov/el offsets index into SolveResult pools

struct SolveResult

source

Fields

• steps std::vector< StepRec >
• alts std::vector< Move > — features only (cov offsets into covers)
• covers std::vector< Cover >
• elims std::vector< uint32_t >
• solved bool
• pats std::vector< int >
• ex std::vector< int > — pattern cells / explanation records of the chosen moves
• stats std::map< std::string, Stat > — SolveOptions::stats: per strategy / direct stage.

struct SolveResult::Stat

source

Fields

• ms double
• calls pm_long
• hits pm_long

struct Strategy

source

Strategy interface: a strategy appends every instance it finds to the move buffer.

Tiers group strategies; the first tier yielding a move wins and the minimum-difficulty move of that tier is applied. New generic strategies (fish over arbitrary AllDiff families, AIC over a link graph, ALS, sum constraints...) plug in here without touching the solve loop.

Name	What it does
~Strategy
name
collect

~Strategy()=default

source

No comment.

const char * name() const =0

source

No comment.

void collect(Solver &s, MoveBuf &out)=0

source

No comment.

struct Flags

source

the disabled techniques.

While a strategy's moves are listed for the listing cache (state_moves), every flag the strategy reads is recorded, so its cached moves are reused only where those flags are the same (listing_cache.cpp)

Name	What it does
assign	resets to n flags, all x
size	number of flags
operator[]
set

Fields

• v std::vector< char >
• rec std::vector< char > *

void assign(size_t n, char x)

source

resets to n flags, all x

size_t size() const

source

number of flags

char operator[](size_t i) const

source

No comment.

void set(size_t i, char x)

source

No comment.

struct SolveOptions

source

Fields

• max_steps int
• allow_direct bool
• disabled std::vector< int >
• skip std::vector< int > — techniques whose strategies are not run in the notes tiers (state_moves(skip=...)): unlike disabled, the flags every other strategy reads stay as they are, so the moves listed are exactly the full listing's minus theirs
• solution std::vector< int > — empty = brute force for Guess
• assume_unique bool — allow uniqueness techniques (UR, BUG+1)
• all_tiers bool — emit the moves of every technique family at each state (audit)
• all_tiers_cap int — ... at most this many per technique (cheapest first; 0 = all)
• explain bool — add state-dependent explanation records to the chosen moves
• stats bool — per-strategy time / calls / hits (SolveResult::stats)
• prune_tiers bool — skip a tier's expensive case-split strategies when a move found earlier in the tier is already cheaper than anything they can price at (same chosen move; fewer alternatives). Off for featurize. off by default: it drops priced alternatives (predict_time sums over them)
• colours std::vector< int > — human colouring (cell -> colour id, -1 none): a colour = "same digit" hypothesis seeding ColourAlgebra; with a solution it is used only where consistent with it, otherwise it is soft (moves flagged)

class Solver

source

Name	What it does
Solver
solve	solves from the givens, one human step at a time, recording the steps and alternatives in out
collect_strategy	s->collect, through the listing cache when lcache is set
direct_moves	mental: 0 off, 2 relations/lines, 3 + subsets
direct_locks	fills lock tables; returns "locks" truthiness
innies	rule-of-45 regions: the last cell of an innie / outie (no notes), or candidates the region sum rules out…
notes_singles	naked and hidden singles over the notes; one move per placement
locked	pointing and claiming: a digit confined to a line (or box) inside a house leaves the rest of that line (box)
cage_combo	sum-cage combinations: candidates no combination of the cage allows are eliminated
pairarc	arc consistency over relation pairs (kropki, difference ...): drops candidates without a partner
relation_pointing	a digit confined to cells of a house that all relate to one cell: it loses what the relation forbids
subsets	naked and hidden subsets of size k (pairs, triples, quads) in houses; adds the eliminations
fish	basic fish of size k (2 X-Wing, 3 Swordfish) over houses; adds the eliminations
xywing	XY-Wing (XYZ-Wing when xyz): pivot with two wings; adds the digit eliminated from cells seeing the wings.
coloring	simple colouring of one digit's conjugate-pair chains: colour wraps and traps; adds the eliminations
trial	bivalue cell whose candidate breaks under basic propagation (trial and error); eliminates that candidate
guess	last resort: places the solution digit of the cell with fewest candidates, priced as the human cost of…
exhaust	where guessing is off: refutes one wrong candidate by full search (recorded as Trial and error)
nary_combination	n-ary constraints
combo_lock	n-ary combination locks: a digit in every consistent assignment, or forced into a rule by a house
nary_direct	no-notes read of a rule with one empty cell whose digit the arithmetic / set rule forces
innie_sum	consistency over rule-of-45 regions too big for the innie/outie sets, as derived sum constraints
compute_mental	builds the no-notes mental view (digits each cell can hold, relation / line bounds, mental subsets) up to…
gfish	generalized fish (any complete groups as base/cover sets): size n, finless (Jellyfish; X-Wing/Swordfish stay…
aic	alternating inference chains over the generic link graph, chain length (links) in [lo, hi]; includes…
unique_rect	uniqueness (only with opt.assume_unique)
bug_plus1	BUG+1: one tri-value cell in an otherwise bivalue grid takes the digit that is odd in its houses.
rule_intersect	two rules / houses taken together: digit combinations over their joint cells; adds the eliminations
sum_algebra	interval algebra over house totals, cages and segments in a band or stack; adds the eliminations
band_logic	a band's lines, boxes and rules taken together as a sub-puzzle; eliminations that hold in all its fillings
describe	structural descriptors (desc.cpp)
written_marks	candidates of c that are written down
desc_stats	refreshes the per-state statistics (candidate counts, bivalue cells ...) used by the move descriptors
struct_colours	structural colouring (symbol per cell, empty = none), computed once per solve
colour_disambiguate	every colour is one digit: digits no consistent permutation gives a colour leave its cells
bug_plus2	BUG+2: tri-value cells T1, T2 in an otherwise bivalue grid; eliminates what all surviving cases share.
extended_ur	extended unique rectangle (2 rows x 3 boxes, six cells): the sixth cell cannot take x, y or z
als_xz	almost locked sets over any AllDiff group
als_xywing	ALS-XY-Wing: pivot ALS linked by restricted commons to two wing ALS; adds the common-digit eliminations.
death_blossom	death blossom: a stem cell whose every candidate has an ALS petal; adds the digit all petals share
als_aic	alternating inference chains through almost locked sets, up to hi links; adds eliminations and placements
short_trial	bounded case split (human "what if"): returns rounds to contradiction, 0 = none
human_case	bounded human case analysis (refutation, cell and house forcing within a few rule rounds)
combo_positions	cage combinations cap how many of a digit set the cage holds in a house; the rest lies outside it
clique_house	cells that pairwise differ (knight's move, relations) treated as a virtual house: naked sets and singles
line_sets	renban-type lines meeting a house use disjoint digit sets there; digits no joint choice allows leave
line_clues	a line with two or more outside clues (sandwich, x-sum, skyscraper) enumerated as one unit
weighted_sums	integer combinations of sum facts down to 1-3 weighted cells, which are enumerated
mental_chains	short chains (<= 5 links) on the no-notes mental view, paying off as a single
case_split
prop_rounds	basic propagation in place for up to max_rounds rounds; returns the round of the first contradiction (0 =…
explain_chosen	explanation records of the chosen move that need the solver state (singles' reasons, trial branches);…
either_way	both options of a two-way choice followed a few rounds; what both agree on holds (direct_view: placements…
line_classes	arc consistency on digit classes (low / high, odd / even) along lines; removes whole classes
digit_count	a digit counted over k base units and k cover units: exactly k copies, so it leaves the covers' other cells
equal_digits	two cells forced to hold the same unknown digit (abstract colouring): each keeps the other's candidates
line_scan	local scan of a long line: consistency over each window of 3 consecutive cells
medusa	3D Medusa: colouring over strong links of several digits; wraps and traps give eliminations
multi_colouring	multi-colouring: two single-digit colour clusters interacting; adds the eliminations
colour_algebra	cells that share an unknown digit (colour classes) combined with the rules; direct_view: on the mental view
label_shadow	cells carrying the same unknown digit label (a permutation of digits) restrict each other's candidates
table_live	number of rows of a table constraint consistent with the placed digits and candidates
n_wing	WXYZ / VWXYZ wings (bent sets): the digit Z leaves cells seeing every Z of the set.
sue_de_coq	Sue de Coq: a box-line intersection with a line set and a box set covering its digits exactly; adds…
aligned_pair	aligned pair exclusion: value pairs of two cells that would empty a common peer; adds the leftovers
fireworks	Fireworks: three digits confined to three cells (corner, one in its row, one in its column); others go.
chute_remote_pairs	remote pairs along a chute (band / stack) with the same bivalue pair; adds the eliminations
pattern_overlay	pattern overlay: per-digit templates over the rows; candidates in no template (or all) are eliminated (placed)
gurth	Gurth's symmetrical placement: a grid symmetry forces digits (uniqueness; opt-in by params)
sum_bound	min / max (triangular number) bounds of sums, cages and arrows; eliminates digits beyond the bounds
class_count	odd / even (and thirds) counting in houses and sum parity; eliminates digits of a full class
class_colour	class colouring: low / high or odd / even links between cells, sides fixed by known cells or house counts
clue_facts	facts read off the clues alone (relations on an empty grid; with line shape): fires once as one step
domino	relation dominoes: a digit every allowed pair uses leaves common houses; two dominoes locking four digits
forcing	forcing chains (forcing.cpp)
nishio	Nishio: follows one digit from an assumed cell; a house left without a place refutes the assumption.
what_if	human "what if": a two-way choice followed with light logic; what both cases agree on holds
mental_notes	notes logic done in the head on the no-notes view (rule combinations, intersections, pairs): a single
fallback_open	true while the forcing fallback has work budget left (boards up to 9x9)
forcing_fallback	last resort before a guess: band logic with a larger budget, then dynamic / nested forcing; true if moves…
fc_propagate	propagates the hypothetical state at level; returns 0 or 1 + the iteration of the first contradiction
fc_branch
gac_prop	nary_moves.cpp
pspread	structural spread of a cell pattern: complete groups touched / (2 sqrt(n) + 1) (canonical; invariant under…
compute_labels	refreshes the invariant cell labels (colour refinement) for the current state
node_label	invariant label of candidate v at cell c, from the labels of the cells that share its houses
canon_dedupe	keeps the cheapest move per placement and per (technique, elimination set)
place	places v at c, clearing it from the peers; returns the number of candidates erased
grid_valid	true if every cell is filled legally and every rule holds
state_moves	every move available at the current state (direct and notes families; tiers ungated), priced; at most…
init_state	resets the state to the givens (all candidates, then the givens placed)
refute_profile	generic refutation profile (refute.cpp): technique-free difficulty
basic_propagate	basic propagation to a fixpoint (singles, relations, rule consistency); false on contradiction
trial_depth	placements until a contradiction, -1 if none within cap
k_prepare	precomputes the houses and their overlaps the knowledge ladder uses
k_step	-1 contradiction, 0 nothing, 1 progress
pick_puzzle	the puzzle actually solved: p.implied (derived houses, leftovers) unless IMPLIED is disabled

Fields

• p const Puzzle &
• P const Params &
• opt SolveOptions
• disabled Flags
• any_disabled bool
• skipped std::vector< char > — opt.skip as flags
• lcache bool — state_moves: notes-tier strategies go through the listing cache
• lcache_params uint64_t — hash of the params the listing was asked with (part of the cache key)
• lcache_solve bool — the listing cache is used inside solve() (the direct blocks bypass it there)
• vals std::vector< uint8_t >
• cand std::vector< uint32_t >
• placed_g std::vector< uint32_t >
• is_given std::vector< char > — cell was a given (avoidable rectangles)
• mex_rel std::vector< uint32_t > — relation arc consistency over house-restricted digits, inequality bounds (chains / mutually distinct predecessors), line consistency; then mental naked subsets (size 2-3). Exclusions beyond the house view: mex_rel / mex_ment.
• mex_ment std::vector< uint32_t >
• md std::vector< uint32_t >
• rs_type std::vector< uint8_t >
• rs_depth std::vector< uint8_t >
• rs_size std::vector< uint8_t > — per cell*32+digit
• rs_line std::vector< int16_t >
• mental_version pm_long
• mental_level int
• written_override std::vector< uint32_t >
• cand_override std::vector< uint32_t > — state_moves(cand=...): per cell, the candidates still open at this state // state_moves(written=...): per cell, the candidates written down
• desc_mode int — notation context of describe(): 0 no notes written, 1 notes, -1 unknown (state_moves: by technique)
• ds_version pm_long
• ds_valid bool
• ds_cands int
• ds_bivalue int
• ds_empty int
• ds_inter int
• ds_open std::vector< int >
• ds_lines std::vector< int >
• ds_subsets double[5]
• struct_cls std::vector< int > — structural colouring (struct_colours): symbol per cell, empty = none
• struct_done bool
• band_regions std::vector< BandRegion >
• band_built bool
• band_regions_wide std::vector< BandRegion > — escalation-only regions (rules taken whole)
• band_built_wide bool
• marked std::vector< char > — notes_lazy: cells whose candidates have been written
• band_wide_now bool — escalation pass over the wide regions
• band_budget_now pm_long — 0: band_logic runs once with this budget (fallback escalation)
• band_escalations int — escalations used in this solve
• band_total pm_long — all BandLogic search nodes in this solve (hard bound 32 x band_budget)
• band_spent pm_long — search nodes used by BandLogic in this solve (fruitless calls, capped at 8 x band_budget)
• band_cache std::map< std::vector< uint32_t >, std::vector< std::array< pm_long, 3 > > > — exact: (region, region state) -> eliminations (cell*32+digit) with their refutation level / cases
• band_sols std::vector< std::vector< std::vector< uint8_t > > > — per region: fillings found (region cells), reused as supports
• band_cache_wide std::map< std::vector< uint32_t >, std::vector< std::array< pm_long, 3 > > >
• band_sols_wide std::vector< std::vector< std::vector< uint8_t > > >
• ri_cache std::map< std::vector< uint32_t >, std::pair< std::vector< uint32_t >, pm_long > > — exact: (pair, union state) -> elims, nodes
• fc_ceiling_now int
• fc_kmax_now int
• fc_tech_now int
• fc_step_cap int
• fc_view int
• fc_level_now int — forcing fallback: level allowed for this call (overrides params forcing_level)
• fc_steps_total pm_long — branch propagation steps of forcing() calls (fallback work budget)
• fc_abort_at pm_long — forcing() gives up (fc_aborted) once fc_steps_total passes this (-1 = never)
• fc_aborted bool
• fb_spent pm_long — fallback work used in this solve
• fb_secs double — fallback wall time used in this solve (safety only, checked between calls)
• version pm_long — bumped whenever the state changes (chain cache key)
• split_memo std::unordered_map< uint64_t, SplitMemo > — case_split results by exact state + assumption
• prop_gac std::unordered_map< const void *, PropGac > — prop_rounds: last consistency result per rule
• dc_cache std::vector< DcCache > — DigitCount results per digit, keyed on the digit plane + base units.
• canon bool
• cell_label std::vector< uint64_t > — invariant cell / candidate labels of the current state (colour refinement)
• label_version pm_long
• prop_cap int — basic_propagate stops (no contradiction) once it has made more placements than this
• gac_ref const std::vector< uint32_t > * — a consistent state: rules none of whose cells differ from it are skipped
• refK int — knowledge ladder: 0 singles+relations+GAC, 1 + locked candidates + pairs,
• k_nbr std::vector< std::vector< int > > — 2 + triples (over all houses); houses sharing >= 2 cells
• k_in std::vector< std::vector< char > > — house membership per cell
• k_ok std::vector< char > — houses the ladder may use (refK >= 10: standard geometry only)

Solver(const Puzzle &p, const Params &P, const SolveOptions &o)

source

No comment.

void solve(const std::vector< std::pair< int, int > > &givens, SolveResult &out)

source

solves from the givens, one human step at a time, recording the steps and alternatives in out

void collect_strategy(Strategy &s, MoveBuf &b)

source

s->collect, through the listing cache when lcache is set

void direct_moves(MoveBuf &out, bool use_locks, int mental=0)

source

mental: 0 off, 2 relations/lines, 3 + subsets

bool direct_locks()

source

fills lock tables; returns "locks" truthiness

void innies(MoveBuf &out, bool notes)

source

rule-of-45 regions: the last cell of an innie / outie (no notes), or candidates the region sum rules out (notes)

void notes_singles(MoveBuf &out)

source

naked and hidden singles over the notes; one move per placement

void locked(MoveBuf &out)

source

pointing and claiming: a digit confined to a line (or box) inside a house leaves the rest of that line (box)

void cage_combo(MoveBuf &out)

source

sum-cage combinations: candidates no combination of the cage allows are eliminated

void pairarc(MoveBuf &out)

source

arc consistency over relation pairs (kropki, difference ...): drops candidates without a partner

void relation_pointing(MoveBuf &out)

source

a digit confined to cells of a house that all relate to one cell: it loses what the relation forbids

void subsets(MoveBuf &out, int k)

source

naked and hidden subsets of size k (pairs, triples, quads) in houses; adds the eliminations

void fish(MoveBuf &out, int k)

source

basic fish of size k (2 X-Wing, 3 Swordfish) over houses; adds the eliminations

void xywing(MoveBuf &out, bool xyz)

source

XY-Wing (XYZ-Wing when xyz): pivot with two wings; adds the digit eliminated from cells seeing the wings.

void coloring(MoveBuf &out)

source

simple colouring of one digit's conjugate-pair chains: colour wraps and traps; adds the eliminations

void trial(MoveBuf &out)

source

bivalue cell whose candidate breaks under basic propagation (trial and error); eliminates that candidate

bool guess(MoveBuf &out)

source

last resort: places the solution digit of the cell with fewest candidates, priced as the human cost of guessing

bool exhaust(MoveBuf &out)

source

where guessing is off: refutes one wrong candidate by full search (recorded as Trial and error)

void nary_combination(MoveBuf &out, int part=0)

source

n-ary constraints

part 0: all but set equivalences, 1: only those, 2: all

void combo_lock(MoveBuf &out)

source

n-ary combination locks: a digit in every consistent assignment, or forced into a rule by a house

void nary_direct(MoveBuf &out)

source

no-notes read of a rule with one empty cell whose digit the arithmetic / set rule forces

void innie_sum(MoveBuf &out)

source

consistency over rule-of-45 regions too big for the innie/outie sets, as derived sum constraints

bool compute_mental(int level)

source

builds the no-notes mental view (digits each cell can hold, relation / line bounds, mental subsets) up to level

void gfish(MoveBuf &out, int n, bool finless, bool finned)

source

generalized fish (any complete groups as base/cover sets): size n, finless (Jellyfish; X-Wing/Swordfish stay with the reference techniques) and/or finned/sashimi; mutant shapes only for size 2

void aic(MoveBuf &out, int lo, int hi)

source

alternating inference chains over the generic link graph, chain length (links) in [lo, hi]; includes discontinuous nice loops (placements)

void unique_rect(MoveBuf &out)

source

uniqueness (only with opt.assume_unique)

void bug_plus1(MoveBuf &out)

source

BUG+1: one tri-value cell in an otherwise bivalue grid takes the digit that is odd in its houses.

void rule_intersect(MoveBuf &out)

source

two rules / houses taken together: digit combinations over their joint cells; adds the eliminations

void sum_algebra(MoveBuf &out)

source

interval algebra over house totals, cages and segments in a band or stack; adds the eliminations

void band_logic(MoveBuf &out)

source

a band's lines, boxes and rules taken together as a sub-puzzle; eliminations that hold in all its fillings

void describe(Move &m, const MoveBuf &b)

source

structural descriptors (desc.cpp)

uint32_t written_marks(int c, int mode) const

source

candidates of c that are written down

void desc_stats()

source

refreshes the per-state statistics (candidate counts, bivalue cells ...) used by the move descriptors

const std::vector< int > & struct_colours()

source

structural colouring (symbol per cell, empty = none), computed once per solve

void colour_disambiguate(MoveBuf &out)

source

every colour is one digit: digits no consistent permutation gives a colour leave its cells

void bug_plus2(MoveBuf &out, int T1, int T2, int G0)

source

BUG+2: tri-value cells T1, T2 in an otherwise bivalue grid; eliminates what all surviving cases share.

void extended_ur(MoveBuf &out)

source

extended unique rectangle (2 rows x 3 boxes, six cells): the sixth cell cannot take x, y or z

void als_xz(MoveBuf &out)

source

almost locked sets over any AllDiff group

void als_xywing(MoveBuf &out)

source

ALS-XY-Wing: pivot ALS linked by restricted commons to two wing ALS; adds the common-digit eliminations.

void death_blossom(MoveBuf &out)

source

death blossom: a stem cell whose every candidate has an ALS petal; adds the digit all petals share

void als_aic(MoveBuf &out, int hi)

source

alternating inference chains through almost locked sets, up to hi links; adds eliminations and placements

void short_trial(MoveBuf &out)

source

bounded case split (human "what if"): returns rounds to contradiction, 0 = none

void human_case(MoveBuf &out)

source

bounded human case analysis (refutation, cell and house forcing within a few rule rounds)

void combo_positions(MoveBuf &out)

source

cage combinations cap how many of a digit set the cage holds in a house; the rest lies outside it

void clique_house(MoveBuf &out)

source

cells that pairwise differ (knight's move, relations) treated as a virtual house: naked sets and singles

void line_sets(MoveBuf &out)

source

renban-type lines meeting a house use disjoint digit sets there; digits no joint choice allows leave

void line_clues(MoveBuf &out)

source

a line with two or more outside clues (sandwich, x-sum, skyscraper) enumerated as one unit

void weighted_sums(MoveBuf &out)

source

integer combinations of sum facts down to 1-3 weighted cells, which are enumerated

void mental_chains(MoveBuf &out)

source

short chains (<= 5 links) on the no-notes mental view, paying off as a single

int case_split(int c, int v, int max_rounds, int &placed, std::vector< uint8_t > *ov=nullptr, std::vector< uint32_t > *oc=nullptr, std::vector< int > *log=nullptr)

source

No comment.

int prop_rounds(int max_rounds, int &placed, std::vector< int > *log=nullptr)

source

basic propagation in place for up to max_rounds rounds; returns the round of the first contradiction (0 = none)

int explain_chosen(const Move &m, const MoveBuf &b, std::vector< int > &ex)

source

explanation records of the chosen move that need the solver state (singles' reasons, trial branches); appended to ex, returns the number of ints added

void either_way(MoveBuf &out, bool direct_view)

source

both options of a two-way choice followed a few rounds; what both agree on holds (direct_view: placements only)

void line_classes(MoveBuf &out)

source

arc consistency on digit classes (low / high, odd / even) along lines; removes whole classes

void digit_count(MoveBuf &out)

source

a digit counted over k base units and k cover units: exactly k copies, so it leaves the covers' other cells

void equal_digits(MoveBuf &out)

source

two cells forced to hold the same unknown digit (abstract colouring): each keeps the other's candidates

void line_scan(MoveBuf &out)

source

local scan of a long line: consistency over each window of 3 consecutive cells

void medusa(MoveBuf &out)

source

3D Medusa: colouring over strong links of several digits; wraps and traps give eliminations

void multi_colouring(MoveBuf &out)

source

multi-colouring: two single-digit colour clusters interacting; adds the eliminations

void colour_algebra(MoveBuf &out, bool direct_view=false)

source

cells that share an unknown digit (colour classes) combined with the rules; direct_view: on the mental view

void label_shadow(MoveBuf &out)

source

cells carrying the same unknown digit label (a permutation of digits) restrict each other's candidates

pm_long table_live(const NConstraint &k) const

source

number of rows of a table constraint consistent with the placed digits and candidates

void n_wing(MoveBuf &out)

source

WXYZ / VWXYZ wings (bent sets): the digit Z leaves cells seeing every Z of the set.

void sue_de_coq(MoveBuf &out)

source

Sue de Coq: a box-line intersection with a line set and a box set covering its digits exactly; adds eliminations.

void aligned_pair(MoveBuf &out)

source

aligned pair exclusion: value pairs of two cells that would empty a common peer; adds the leftovers

void fireworks(MoveBuf &out)

source

Fireworks: three digits confined to three cells (corner, one in its row, one in its column); others go.

void chute_remote_pairs(MoveBuf &out)

source

remote pairs along a chute (band / stack) with the same bivalue pair; adds the eliminations

void pattern_overlay(MoveBuf &out)

source

pattern overlay: per-digit templates over the rows; candidates in no template (or all) are eliminated (placed)

void gurth(MoveBuf &out)

source

Gurth's symmetrical placement: a grid symmetry forces digits (uniqueness; opt-in by params)

void sum_bound(MoveBuf &out)

source

min / max (triangular number) bounds of sums, cages and arrows; eliminates digits beyond the bounds

void class_count(MoveBuf &out)

source

odd / even (and thirds) counting in houses and sum parity; eliminates digits of a full class

void class_colour(MoveBuf &out)

source

class colouring: low / high or odd / even links between cells, sides fixed by known cells or house counts

void clue_facts(MoveBuf &out)

source

facts read off the clues alone (relations on an empty grid; with line shape): fires once as one step

void domino(MoveBuf &out)

source

relation dominoes: a digit every allowed pair uses leaves common houses; two dominoes locking four digits

void forcing(MoveBuf &out, int level, bool nested=false)

source

forcing chains (forcing.cpp)

void nishio(MoveBuf &out)

source

Nishio: follows one digit from an assumed cell; a house left without a place refutes the assumption.

void what_if(MoveBuf &out, bool direct_view)

source

human "what if": a two-way choice followed with light logic; what both cases agree on holds

void mental_notes(MoveBuf &out)

source

notes logic done in the head on the no-notes view (rule combinations, intersections, pairs): a single

bool fallback_open() const

source

true while the forcing fallback has work budget left (boards up to 9x9)

bool forcing_fallback(MoveBuf &fb)

source

last resort before a guess: band logic with a larger budget, then dynamic / nested forcing; true if moves found

int fc_propagate(int level, int &steps, std::vector< int > *log=nullptr)

source

propagates the hypothetical state at level; returns 0 or 1 + the iteration of the first contradiction

int fc_branch(int c, int v, int level, int &steps, std::vector< uint8_t > *ov=nullptr, std::vector< uint32_t > *oc=nullptr, std::vector< int > *log=nullptr)

source

No comment.

void gac_prop(const NConstraint &k, const uint32_t *dom, pm_long budget, GacOut &out)

source

nary_moves.cpp

double pspread(const std::vector< int > &cells) const

source

structural spread of a cell pattern: complete groups touched / (2 sqrt(n) + 1) (canonical; invariant under puzzle automorphisms) or the coordinate gyration ratio (reference behaviour)

void compute_labels()

source

refreshes the invariant cell labels (colour refinement) for the current state

uint64_t node_label(int c, int v)

source

invariant label of candidate v at cell c, from the labels of the cells that share its houses

void canon_dedupe(MoveBuf &b)

source

keeps the cheapest move per placement and per (technique, elimination set)

int place(int c, int v)

source

places v at c, clearing it from the peers; returns the number of candidates erased

bool grid_valid() const

source

true if every cell is filled legally and every rule holds

void state_moves(const std::vector< std::pair< int, int > > &givens, MoveBuf &b, int limit_per_tech)

source

every move available at the current state (direct and notes families; tiers ungated), priced; at most limit_per_tech per technique (0 = all)

every cell filled consistently with every rule

void init_state(const std::vector< std::pair< int, int > > &givens)

source

resets the state to the givens (all candidates, then the givens placed)

void refute_profile(const std::vector< std::pair< int, int > > &givens, const std::vector< int > &sol, int max_stuck, std::vector< std::array< int, 5 > > &out)

source

generic refutation profile (refute.cpp): technique-free difficulty

bool basic_propagate(int &placed)

source

basic propagation to a fixpoint (singles, relations, rule consistency); false on contradiction

int trial_depth(int c, int v, int cap=1<< 30)

source

placements until a contradiction, -1 if none within cap

void k_prepare()

source

precomputes the houses and their overlaps the knowledge ladder uses

int k_step()

source

-1 contradiction, 0 nothing, 1 progress

static const Puzzle & pick_puzzle(const Puzzle &pz, const SolveOptions &o)

source

the puzzle actually solved: p.implied (derived houses, leftovers) unless IMPLIED is disabled

struct Solver::BandRegion

source

Fields

• lines std::vector< int >
• boxes std::vector< int >
• rules std::vector< int >
• cages std::vector< int >
• cells std::vector< int >
• supers std::vector< int > — regions holding all of this one's houses, rules and cages
• pos std::vector< int > — cell -> index in the sub-puzzle (-1 outside)
• sub std::shared_ptr< Puzzle >

struct Solver::DcCache

source

Fields

• valid bool
• key std::vector< uint64_t >
• buf MoveBuf

struct Solver::SplitMemo

source

Fields

• vals std::vector< uint8_t >
• cand std::vector< uint32_t >
• c0 int
• v0 int
• rounds int
• result int
• placed int
• ov std::vector< uint8_t >
• oc std::vector< uint32_t >

struct Solver::PropGac

source

Fields

• valid bool
• dom std::vector< uint32_t >
• out GacOut

struct Solver::Src

source

Fields

• kind int
• shape double
• mask uint32_t

struct Solver::HSrc

source

Fields

• key uint64_t
• kind int
• shape double
• local uint32_t

struct Solver::LockEntry

source

Fields

• ident uint64_t
• shape double
• mask uint32_t
• tgt int — index into lock_tgt (W words each)

struct Solver::GacCache

source

Fields

• valid bool
• dom std::vector< uint32_t >
• out GacOut

struct Solver::GacKey

source

Name	What it does
operator==

Fields

• k const NConstraint *
• v int
• mask uint64_t

bool operator==(const GacKey &o) const

source

No comment.

struct Solver::GacKeyHash

source

Name	What it does
operator()

size_t operator()(const GacKey &x) const

source

No comment.

struct Solver::ALS

source

Fields

• cells std::vector< uint64_t > — W words.
• list std::vector< int >
• cand uint32_t
• group int