csp-solver 0.6.0

Generic constraint satisfaction problem solver with backtracking, AC-3 constraint propagation, and ordering heuristics.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

//! The puzzle-family generator contract.
//!
//! Sudoku and futoshiki generate by the *same* three beats — seed a full
//! solution, place clue furniture, then uniqueness-checked hole-dig — and
//! diverge only where [`PuzzleClass`] names seams. The trait is the intersection
//! their two generators already satisfy, drawn so one generic dealer can drive
//! both; T4-W13's `generate_by_digging<C: PuzzleClass>` is that dealer, and a
//! third family (Thermo/Killer/KenKen) ships as one impl of this trait plus a
//! payload builder, no new generator.

pub use crate::puzzles::sudoku::rng::SimpleRng;

/// The generator contract a puzzle family satisfies so one generic hole-digging
/// dealer deals them all.
///
/// Divergence between families is expressed as associated types and methods —
/// the clue furniture a board carries ([`Clue`](Self::Clue)), the puzzle the
/// caller receives ([`Puzzle`](Self::Puzzle)), and the family CSP a candidate
/// board solves against ([`solve_candidate`](Self::solve_candidate)) — never as
/// config flags. Every method is a per-family seam; a boolean toggle would be a
/// seam this trait missed.
pub trait PuzzleClass {
    /// Clue furniture beyond the board's givens: an inequality caret `(a, b)`
    /// meaning `board[a] > board[b]` (futoshiki), nothing at all (`()`, sudoku),
    /// a cage (W13).
    type Clue;

    /// The dealt puzzle as the caller receives it: the dense board alone
    /// (sudoku) or the board paired with its clue furniture (futoshiki).
    type Puzzle;

    /// Seed a complete, valid solution grid — dense, `0`-free — by fixing a
    /// shuffled first row and solving the rest through the crate solver (never a
    /// bespoke square builder). Its length is the board's cell count, which
    /// drives the dig.
    fn seed_solution(&self, rng: &mut SimpleRng) -> Vec<u32>;

    /// Place clue furniture over the seed `solution`. Sudoku places none (empty);
    /// futoshiki picks orthogonally-adjacent pairs the seed already satisfies, so
    /// the seed stays a valid start and every clue renders as a boundary caret.
    fn place_clues(&self, solution: &[u32], rng: &mut SimpleRng) -> Vec<Self::Clue>;

    /// Solve a candidate `board` (`0` = blank) under this family's constraints
    /// plus `clues`, returning up to `max_solutions` solutions — the base-CSP
    /// seam the seed solve and the dig's `max_solutions: 2` uniqueness check both
    /// call. Each family builds its own CSP behind this, so the `Csp`/`VarId`/
    /// domain machinery stays implementation detail.
    fn solve_candidate(
        &self,
        board: &[u32],
        clues: &[Self::Clue],
        max_solutions: usize,
    ) -> Vec<Vec<u32>>;

    /// Holes to dig for this instance's difficulty, given the seed board's
    /// `board_len`. Sudoku's clue-count bands and futoshiki's keep-density both
    /// resolve here.
    fn target_holes(&self, board_len: usize) -> usize;

    /// Assemble the dealt puzzle from the dug `board` and its `clues`.
    fn assemble(&self, board: Vec<u32>, clues: Vec<Self::Clue>) -> Self::Puzzle;
}

/// The generic hole-digging dealer, driven entirely through [`PuzzleClass`] —
/// the three shared beats every family generates by: seed a full solution, place
/// clue furniture, then dig blanks while a `max_solutions: 2` re-solve keeps the
/// board unique (a removal that admits a second solution is reverted). One
/// seeded `rng` threads seed → clues → dig.
///
/// This is the shape `tests/puzzle_class.rs` proved reproduces the shipped
/// `generate_board_seeded` / `generate_futoshiki_*_seeded` generators
/// byte-for-byte — the RS acceptance that the trait is the true intersection.
/// T4-W13's Thermo/Killer/KenKen deal through it, adding no new generator.
pub fn generate_by_digging<C: PuzzleClass>(class: &C, rng: &mut SimpleRng) -> C::Puzzle {
    let solution = class.seed_solution(rng);
    let clues = class.place_clues(&solution, rng);
    let target = class.target_holes(solution.len());

    let mut board = solution.clone();
    let mut indices: Vec<usize> = (0..solution.len()).collect();
    rng.shuffle(&mut indices);

    let mut holes = 0usize;
    for &idx in &indices {
        if holes >= target {
            break;
        }
        let saved = board[idx];
        board[idx] = 0;
        if class.solve_candidate(&board, &clues, 2).len() == 1 {
            holes += 1;
        } else {
            board[idx] = saved;
        }
    }

    class.assemble(board, clues)
}