csp_solver/puzzles/
class.rs

1//! The puzzle-family generator contract.
2//!
3//! Sudoku and futoshiki generate by the *same* three beats — seed a full
4//! solution, place clue furniture, then uniqueness-checked hole-dig — and
5//! diverge only where [`PuzzleClass`] names seams. The trait is the intersection
6//! their two generators already satisfy, drawn so one generic dealer can drive
7//! both; T4-W13's `generate_by_digging<C: PuzzleClass>` is that dealer, and a
8//! third family (Thermo/Killer/KenKen) ships as one impl of this trait plus a
9//! payload builder, no new generator.
10
11pub use crate::puzzles::sudoku::rng::SimpleRng;
12
13/// The generator contract a puzzle family satisfies so one generic hole-digging
14/// dealer deals them all.
15///
16/// Divergence between families is expressed as associated types and methods —
17/// the clue furniture a board carries ([`Clue`](Self::Clue)), the puzzle the
18/// caller receives ([`Puzzle`](Self::Puzzle)), and the family CSP a candidate
19/// board solves against ([`solve_candidate`](Self::solve_candidate)) — never as
20/// config flags. Every method is a per-family seam; a boolean toggle would be a
21/// seam this trait missed.
22pub trait PuzzleClass {
23    /// Clue furniture beyond the board's givens: an inequality caret `(a, b)`
24    /// meaning `board[a] > board[b]` (futoshiki), nothing at all (`()`, sudoku),
25    /// a cage (W13).
26    type Clue;
27
28    /// The dealt puzzle as the caller receives it: the dense board alone
29    /// (sudoku) or the board paired with its clue furniture (futoshiki).
30    type Puzzle;
31
32    /// Seed a complete, valid solution grid — dense, `0`-free — by fixing a
33    /// shuffled first row and solving the rest through the crate solver (never a
34    /// bespoke square builder). Its length is the board's cell count, which
35    /// drives the dig.
36    fn seed_solution(&self, rng: &mut SimpleRng) -> Vec<u32>;
37
38    /// Place clue furniture over the seed `solution`. Sudoku places none (empty);
39    /// futoshiki picks orthogonally-adjacent pairs the seed already satisfies, so
40    /// the seed stays a valid start and every clue renders as a boundary caret.
41    fn place_clues(&self, solution: &[u32], rng: &mut SimpleRng) -> Vec<Self::Clue>;
42
43    /// Solve a candidate `board` (`0` = blank) under this family's constraints
44    /// plus `clues`, returning up to `max_solutions` solutions — the base-CSP
45    /// seam the seed solve and the dig's `max_solutions: 2` uniqueness check both
46    /// call. Each family builds its own CSP behind this, so the `Csp`/`VarId`/
47    /// domain machinery stays implementation detail.
48    fn solve_candidate(
49        &self,
50        board: &[u32],
51        clues: &[Self::Clue],
52        max_solutions: usize,
53    ) -> Vec<Vec<u32>>;
54
55    /// Holes to dig for this instance's difficulty, given the seed board's
56    /// `board_len`. Sudoku's clue-count bands and futoshiki's keep-density both
57    /// resolve here.
58    fn target_holes(&self, board_len: usize) -> usize;
59
60    /// Assemble the dealt puzzle from the dug `board` and its `clues`.
61    fn assemble(&self, board: Vec<u32>, clues: Vec<Self::Clue>) -> Self::Puzzle;
62}
63
64/// The generic hole-digging dealer, driven entirely through [`PuzzleClass`] —
65/// the three shared beats every family generates by: seed a full solution, place
66/// clue furniture, then dig blanks while a `max_solutions: 2` re-solve keeps the
67/// board unique (a removal that admits a second solution is reverted). One
68/// seeded `rng` threads seed → clues → dig.
69///
70/// This is the shape `tests/puzzle_class.rs` proved reproduces the shipped
71/// `generate_board_seeded` / `generate_futoshiki_*_seeded` generators
72/// byte-for-byte — the RS acceptance that the trait is the true intersection.
73/// T4-W13's Thermo/Killer/KenKen deal through it, adding no new generator.
74pub fn generate_by_digging<C: PuzzleClass>(class: &C, rng: &mut SimpleRng) -> C::Puzzle {
75    let solution = class.seed_solution(rng);
76    let clues = class.place_clues(&solution, rng);
77    let target = class.target_holes(solution.len());
78
79    let mut board = solution.clone();
80    let mut indices: Vec<usize> = (0..solution.len()).collect();
81    rng.shuffle(&mut indices);
82
83    let mut holes = 0usize;
84    for &idx in &indices {
85        if holes >= target {
86            break;
87        }
88        let saved = board[idx];
89        board[idx] = 0;
90        if class.solve_candidate(&board, &clues, 2).len() == 1 {
91            holes += 1;
92        } else {
93            board[idx] = saved;
94        }
95    }
96
97    class.assemble(board, clues)
98}
csp_solver/puzzles/class.rs

csp_solver/puzzles/
class.rs
