Substrates

A substrate records what positions exist in a puzzle and what’s at them. One struct per puzzle, four optional layer grids inside, one Material per position.

// core::substrate

/// How a puzzle's grid is sized. Most genres use `Rect`. Sudoku
/// uses `Boxed` so the substrate carries the box partition that
/// constraint emission needs (per-box rectangles).
pub enum Dimensions {
    /// `rows × cols` rectangle. Akari, slither, most genres.
    Rect  { rows: usize, cols: usize },
    /// Sudoku-style: side = `box_w × box_h`, partitioned into
    /// `box_h` rows × `box_w` cols of boxes.
    Boxed { box_w: u8, box_h: u8 },
}

impl Dimensions {
    pub fn rows(&self) -> usize { /* … */ }
    pub fn cols(&self) -> usize { /* … */ }
}

/// The structural shape of a puzzle. Every `Puzzle` carries one
/// reachable via `substrate()`. Direct fields per layer; the
/// populated ones describe which positions exist and what's at each.
pub struct Substrate {
    pub dims: Dimensions,

    /// `None` = the genre doesn't use this layer. `Some(grid)` =
    /// the layer is in use; grid contents give per-position Material.
    pub cells:    Option<Grid<Material>>,   // rows × cols
    pub edges_h:  Option<Grid<Material>>,   // (rows + 1) × cols
    pub edges_v:  Option<Grid<Material>>,   // rows × (cols + 1)
    pub corners:  Option<Grid<Material>>,   // (rows + 1) × (cols + 1)
}

/// What's *at* a position — the substance, structurally.
#[repr(u8)]
pub enum Material {
    /// Decision-target position. The default; what `Grid::new` fills with.
    #[default]
    Floor,
    /// Excluded; blocks LOS rays. Akari walls, Hitori shaded givens.
    Wall,
    /// Excluded; doesn't block LOS. Akari holes, Samurai padded gaps.
    Hole,
    /// Excluded; exists for rendering only. Slitherlink clue cells,
    /// Killer-cage corner labels, Kropki edge dots, Picross hint
    /// rows/cols outside the play grid.
    LabelOnly,
}

Material is the structural classification of a position — fixed when the substrate is built, immutable during play. Four variants, each with a different effect on what the engine and renderer do at that coord:

• Floor is a decision target: the player or solver will commit a mark here. It’s the default value of Material (and what Grid::new fills with), so a fresh grid is fully playable. The vast majority of positions in most genres are Floor.
• Wall is excluded and blocks LOS rays: not a decision target (no mark ever lives here), and rays walked from neighboring cells stop at the wall position. Akari walls, Hitori shaded givens. The renderer paints them as solid blockers.
• Hole is excluded but transparent to LOS: also not a decision target, but rays pass straight through. This is the mechanism by which non-rectangular puzzles fit a flat R × C bounding box — Samurai gap cells, Iraka holes; see below.
• LabelOnly is excluded, transparent to LOS, and exists for rendering: the position is structurally there so the renderer can paint a label / glyph / decoration anchored at it, but the engine never allocates decision state for it. Slitherlink clue cells, Killer-cage corner sums, Kropki edge dots, Picross hint rows/cols. The label value lives in puzzle-level data (e.g. cell_clue(), variant payloads); Material::LabelOnly is just the structural marker.

Material answers “what’s structurally here?”, not “what value lives here?”. A Floor cell can hold any mark in its domain; Wall, Hole, and LabelOnly cells can’t hold any mark at all.

Edges H and V stay separate fields because their dimensions differ and their geometric meaning is orientation-specific (Coord::EdgeH vs Coord::EdgeV); renderer and constraint code dispatches on orientation.

Substrate is uniformly typed across genres — every puzzle holds one, accessed the same way. What varies per genre is which fields are populated and what the contents are. Walls and holes shape what coords exist before any rule fires; the substrate is structurally prior.

Per-coord queries live as inherent methods:

impl Substrate {
    pub fn rows(&self) -> usize;  // forwards to dims.rows()
    pub fn cols(&self) -> usize;  // forwards to dims.cols()

    /// Direct lookup by Layer reference. `None` if the genre
    /// doesn't populate this layer.
    pub fn grid(&self, layer: Layer) -> Option<&Grid<Material>>;

    /// `Material` at `coord`; `Floor` (defensive default) for
    /// unmapped layers.
    pub fn material(&self, coord: Coord) -> Material;
    pub fn set_material(&mut self, coord: Coord, m: Material);

    /// Whether the cell at raw `(r, c)` blocks LOS rays
    /// (`Material::Wall`).
    pub fn blocks_los(&self, r: usize, c: usize) -> bool;

    /// Every `Floor` position across every populated layer — the
    /// decision-target set.
    pub fn coords(&self)    -> impl Iterator<Item = Coord> + '_;
    /// Every populated-layer position regardless of material —
    /// renderer-facing.
    pub fn positions(&self) -> impl Iterator<Item = Coord> + '_;
    /// Iterate `(Layer, &Grid)` for every populated layer.
    pub fn layers(&self)    -> impl Iterator<Item = (Layer, &Grid<Material>)> + '_;

    // ── Material-keyed iterators ──
    /// Iterate every cell whose Material equals `target`. Akari uses
    /// this for "every floor cell" and "every hole cell" sweeps
    /// during constraint emission.
    pub fn cells_by_material(&self, target: Material)
        -> impl Iterator<Item = Coord> + '_;

    // ── Geometry helpers ──
    pub fn edges_of_cell(&self, r: usize, c: usize) -> [Coord; 4];
    pub fn edges_of_vertex(&self, r: usize, c: usize) -> Vec<Coord>;
    pub fn vertices_of_cell(&self, r: usize, c: usize) -> [Coord; 4];
    pub fn vertices_of_edge(&self, edge: Coord) -> [Coord; 2];
    pub fn cells_of_edge(&self, edge: Coord) -> Vec<Coord>;
    pub fn cells_of_vertex(&self, r: usize, c: usize) -> Vec<Coord>;

    /// Iterate every vertex paired with its incident edges. Slither
    /// uses this for the per-vertex `DegreeIn{0, 2}` constraint emit.
    pub fn vertices_with_edges(&self)
        -> impl Iterator<Item = (Coord, Vec<Coord>)> + '_;

    /// Walk maximal `Floor` segments along `axis`. Walls flush the
    /// current segment; non-floor materials other than `Wall` (Hole,
    /// LabelOnly) are transparent. Akari uses this for the
    /// per-row / per-col `AtMost(Bulb, 1)` segment constraints.
    pub fn for_each_floor_segment(
        &self,
        axis: Axis,
        on_segment: impl FnMut(Vec<Coord>),
    );
}

pub enum Axis { Horizontal, Vertical }

Per-genre allocations

Genres build their substrate via Genre::default_substrate(dims), returning whatever shape is canonical for that genre:

// Akari 7×7 — every cell starts as Floor; constructor calls
// set_wall / set_hole / add_clue to install the puzzle's walls,
// holes, and clue values.
Substrate {
    dims: Dimensions::Rect { rows: 7, cols: 7 },
    cells: Some(Grid::filled(7, 7, Material::Floor)),
    edges_h: None, edges_v: None, corners: None,
}

// Sudoku 9×9 — Boxed dims so build_constraints can read box_w/box_h.
Substrate {
    dims: Dimensions::Boxed { box_w: 3, box_h: 3 },
    cells: Some(Grid::filled(9, 9, Material::Floor)),
    edges_h: None, edges_v: None, corners: None,
}

// Slitherlink 5×5 — cells (clue containers, all LabelOnly) + edges
// (every edge a decision target).
Substrate {
    dims: Dimensions::Rect { rows: 5, cols: 5 },
    cells:   Some(Grid::filled(5, 5, Material::LabelOnly)),
    edges_h: Some(Grid::filled(6, 5, Material::Floor)),
    edges_v: Some(Grid::filled(5, 6, Material::Floor)),
    corners: None,
}

// Samurai 21×21 — cells with 72 Hole positions for the gap regions.
Substrate {
    dims: Dimensions::Rect { rows: 21, cols: 21 },
    cells: Some(grid_with_padding_holes()),
    edges_h: None, edges_v: None, corners: None,
}

The “all Floor” grids cost a byte per position — 81 bytes for sudoku, trivial. Dense storage is correct because Floor is the dominant state; the previous HashMap-of-walls representation was a sparseness optimization for a non-sparse situation.

Non-rectangular shapes via Material::Hole

Hole is the mechanism by which non-rectangular puzzles fit the flat R × C model. Pad the bounding rectangle, mark the gaps as Material::Hole, and the substrate machinery treats them correctly: not in coords(), not painted as decision cells, LOS rays pass straight through.

This handles every “multiple sub-grids in a bigger rectangle” topology in the puzz.link / canonical roster:

• Samurai Sudoku — five 9×9s arranged in an X, fitted into a 21×21 bounding box with 72 padded gap cells.
• Gattai-8 — eight 9×9s edge-to-edge, larger bounding box, gaps where rows or cols don’t line up.
• Shogun — a 5×5 of 9×9s (45×45 bounding), regular grid of gaps.
• Sumo — four 9×9s overlapping at a center 9×9.

In every case, the cells-appearing-in-multiple-regions pattern that already powers Sudoku’s 27 standard regions just keeps working: the overlap zones are coords that appear in two sub-grids’ constraint regions (one row from sub-grid A, one row from sub-grid B), and the propagator handles the shared-cell case naturally — no special multi-grid coordinate machinery, no new Layout type.

What this doesn’t cover: genuinely non-rectangular topologies — hex grids, polar grids, Möbius strips, toruses. Those need new Layer variants (a hypothetical Layer::HexCells) and a different geometric vocabulary in RegionShape. Until then, flat R × C plus Hole covers every multi-grid puzzle on the current catalog without architectural concessions.

Future genres

Heyawake rooms, Hashi islands, Killer cages, Star Battle anchors — all deferred to the constraint list. A Heyawake room is a Region referenced by every constraint targeting it; the room layout ships as the region’s coord set. Hashi islands are Pin-style constraints anchoring bridge endpoints; the island position is just a Floor cell that happens to have constraints rooted at it.

Material::LabelOnly covers the recurring “structurally exists, holds a label, never decides” pattern across Sudoku variants and Picross-family genres:

• Killer Sudoku — corner positions in the Corners layer carry cage-sum labels. Material::LabelOnly at the cage’s anchor corner; the sum value lives in the variant payload.
• Kropki Sudoku — edge positions in EdgesH / EdgesV host white/black dots between adjacent cells. The edges layer is all LabelOnly (no edge marks); dot kind comes from the variant payload.
• Sandwich / Little Killer / Quadruple clues — extra rows or columns of LabelOnly corner/edge anchors outside the cell grid.
• Picross — the bounding box pads the cell grid with hint rows on top and hint columns on the left; those padding cells are LabelOnly, holding the hint sequences. The actual play grid is Floor cells in the bottom-right rectangle.

Extending Material further is reserved for genuinely new structural categories (a hypothetical “portal” cell that warps LOS, a “tinted” non-blocker that affects scoring) that no current or near-future genre needs.