🥮 mooncakes.io

    moonpeg

    Bounded peg-solitaire solving, reverse generation and replay verification

    peg-solitaire
    puzzle
    solver
    bitset
    Download zip
    Author
    Version
    0.1.0
    License
    MIT
    Repository
    Last updated
    13 hours ago
    Downloads
    3

    #MoonPeg

    Pure MoonBit peg-solitaire solving, inverse puzzle generation and replayable certificates.

    MoonPeg turns ASCII boards into checked geometric jumps, bounded search results and solutions you can replay. For puzzle editors, teaching tools and offline generation pipelines—not a general graph library or full game UI.

    oo.  -- jump 0 -->  ..o

    #Features

    • Immutable UInt64 occupancy: o peg, . empty hole, # absent; at most 8x8/64 holes.
    • Orthogonal/triangular lattices; English 33-hole and triangular presets.
    • Checked forward/inverse moves, exact/any-single goals, full transcript replay.
    • Bounded deterministic DFS, dead-state cache and goal-preserving geometric symmetry.
    • Separate GF(2) position-class and jump-component necessary reachability diagnostics.
    • Shared-budget opening hints; seeded inverse generation with forward certificates.
    • Portable coordinate steps, JSON v1 facade and bounded file/stdin Node CLI.

    #Install and run locally

    Prerequisites: MoonBit; Node.js 22+ for CLI/oracle; Python 3.8+ for engineering scripts. Native execution additionally needs a C compiler. Install MoonBit from its official download page. Verified baseline: moonc v0.10.4+2cc641edf, moon 0.1.20260713; CI pins it. This is a public GitHub source package, not a published MoonCakes package: use a source checkout or path dependency; do not assume moon add will find it before manual publication.

    Clone the public source, then run from its root:

    git clone https://github.com/kekeshuo/moonpeg.git
cd moonpeg

    moon check --deny-warn
moon test
moon run examples/solve --target wasm-gc
moon build --target js --release
node scripts/moonpeg.cjs examples/requests/triangle.json
node scripts/examples.cjs

    The tutorial solves the 15-hole triangle in 13 jumps (115 expanded nodes on the recorded baseline), verifies every transition, then generates and verifies a nine-peg puzzle. node scripts/moonpeg.cjs --help describes file/stdin usage and exit codes.

    #Integrate before publication

    Use a local dependency in a separate consumer's moon.mod.json:

    {"name":"local/my_puzzle","deps":{"kekeshuo/moonpeg":{"path":"../moonpeg"}}}

    Import "kekeshuo/moonpeg" @peg in its moon.pkg. Call from a raising function/test:

    let (board, start) = @peg.parse_board("oo.")
    match board.solve(start, AnySingle, 100).outcome {
      Solved(moves) => assert_true(board.verify_solution(start, moves, AnySingle))
      Unsolvable => abort("no solution")
      Exhausted => abort("unknown: increase budget")
    }

    python scripts/consumer-test.py verifies a separate unpublished path-dependency consumer. Generated APIs: core, protocol. Compiling usage: tutorial source.

    #Contracts

    AreaContract
    BoardsWidth/height 1..8; ASCII; LF/CRLF, optional final LF; no bare CR
    MovesOrthogonal axes; triangular adds (1,1). Deterministic zero-based IDs
    GoalsAny singleton or exact nonempty occupancy on the same topology
    Search0..1000000 expanded non-goal nodes; goal checks/cache hits are free
    ResultsSolved includes a replayable path; Unsolvable means exhaustive proof; Exhausted means unknown
    GenerationUp to holes-minus-goal-pegs inverse jumps; may stop early; no uniformity/difficulty claim
    CertificatesAt most 63 jumps; illegal step gives a zero-based transcript diagnostic
    TransportJSON: 16384 code units/depth 16; CLI: 65536 UTF-8 bytes; no lossy UInt64 payloads

    Board operations validate occupancies. Topology is opaque; returned collections are copies. Positions do not carry board identity: do not reuse bits with different topology. Diagnostics and DFS are separate; an empty obstruction list is not a solvability proof. Search is worst-case exponential and synchronous; node budgets are not time limits. No full English-board solvability, optimality/difficulty or exhaustive ecosystem-novelty claim.

    #Verify

    python scripts/verify.py
# Explicitly record unverified native runtime when no C compiler is installed:
python scripts/verify.py --skip-native-runtime

    Local results: 43 tests on each of wasm-gc, wasm and js; native strict check passed, but native build/test/demo are unverified locally. Independent oracle: 20096 board/goal cases, 1164 solutions independently replayed, 15606 necessary-obstruction checks. Eight request fixtures and 11 CLI process cases pass. Hosted acceptance run passed all four targets, including native build, 43 tests and the executable tutorial, on Ubuntu 24.04. This hosted result does not imply a local Windows native test. See testing, release verification and the historical local checkpoint.

    #Documentation

    Tutorial · JSON · Architecture · Duplication research · Scope · AI disclosure · Notices · Security · Contributing · Changelog

    Original implementation under MIT; runtime dependencies are MoonBit core only. Public source · CI runs · GitHub releases. No MoonCakes publication or competition acceptance is claimed. Participant information and the competition application stay outside this repository; the application is not yet final.

    PegError

    source
    pub suberror PegError {
      InvalidBoard(String)
      InvalidPosition
      InvalidGoal
      InvalidBudget
      InvalidTranscript(Int)
      InvalidMove(Int)
    } derive(Eq, 
    Debug    )

    Errors are stable codes with context. No user input is used as an index before validation.

    Board

    source
    pub struct Board {
      width : Int
      height : Int
      cells : Array[Cell]
      mask : UInt64
      jumps : Array[Jump]
      lattice : Lattice
    } derive(
    Debug    )

    Board topology is opaque; returned collections are copies.

    Board::canonical

    source
    fn Board::canonical(self : Board, p : Position, goal : Goal) -> Position raise PegError

    Canonicalization is goal-dependent, so a corner goal is never swapped to another corner.

    Board::class_compatible

    source
    fn Board::class_compatible(self : Board, start : Position, goal : Goal) -> Bool raise PegError

    Board::component_compatible

    source
    fn Board::component_compatible(self : Board, start : Position, goal : Goal) -> Bool raise PegError

    Board::components

    source
    fn Board::components(self : Board) -> Array[Array[Int]]

    An occupied component cannot become empty by peg removal; an empty one cannot gain a peg.

    Board::decode_steps

    source
    fn Board::decode_steps(self : Board, steps : Array[Step]) -> Array[Int] raise PegError

    Board::dimensions

    source
    fn Board::dimensions(self : Board) -> (Int, Int)

    Board::encode_steps

    source
    fn Board::encode_steps(self : Board, moves : Array[Int]) -> Array[Step] raise PegError

    Convert only valid directed board jumps. Occupancy is checked during replay.

    Board::generate

    source
    fn Board::generate(self : Board, goal : Position, depth : Int, seed : UInt) -> Generated raise PegError

    Wrapping UInt arithmetic is intentional for the portable deterministic PRNG.

    Board::goal_at

    source
    fn Board::goal_at(self : Board, x : Int, y : Int) -> Goal raise PegError

    Construct an exact singleton goal using public grid coordinates.

    Board::hints

    source
    fn Board::hints(self : Board, start : Position, goal : Goal, budget : Int) -> Array[Hint] raise PegError

    including the opening move. Later openings receive only unspent budget.

    Board::holes

    source
    fn Board::holes(self : Board) -> Array[Cell]

    Board::index

    source
    fn Board::index(self : Board, x : Int, y : Int) -> Int?

    Board::is_goal

    source
    fn Board::is_goal(self : Board, p : Position, goal : Goal) -> Bool raise PegError

    Board::is_terminal

    source
    fn Board::is_terminal(self : Board, p : Position) -> Bool raise PegError

    Board::jumps

    source
    fn Board::jumps(self : Board) -> Array[Jump]

    Board::lattice

    source
    fn Board::lattice(self : Board) -> Lattice

    Board::legal_moves

    source
    fn Board::legal_moves(self : Board, pos : Position) -> Array[Int] raise PegError

    Board::obstructions

    source
    fn Board::obstructions(self : Board, start : Position, goal : Goal) -> Array[String] raise PegError

    A list of independently sound obstructions. Empty means unknown, NOT solvable.

    Board::play

    source
    fn Board::play(self : Board, pos : Position, move_id : Int) -> Position raise PegError

    Invalid moves never modify their input position.

    Board::position_class

    source
    fn Board::position_class(self : Board, p : Position) -> UInt64 raise PegError

    Board::render

    source
    fn Board::render(self : Board, pos : Position) -> String raise PegError

    Board::replay

    source
    fn Board::replay(self : Board, start : Position, moves : Array[Int]) -> Array[Position] raise PegError

    Includes initial position. Error index is zero based; input is not mutated.

    Board::reverse_moves

    source
    fn Board::reverse_moves(self : Board, pos : Position) -> Array[Int] raise PegError

    Board::size

    source
    fn Board::size(self : Board) -> Int

    Board::solve

    source
    fn Board::solve(self : Board, start : Position, goal : Goal, budget : Int, memoize? : Bool, symmetry? : Bool) -> SearchReport raise PegError

    A goal at the starting position succeeds even with zero budget.

    Board::symmetry_count

    source
    fn Board::symmetry_count(self : Board, goal : Goal) -> Int raise PegError

    Board::unplay

    source
    fn Board::unplay(self : Board, pos : Position, move_id : Int) -> Position raise PegError

    Board::validate

    source
    fn Board::validate(self : Board, pos : Position) -> Unit raise PegError

    Board::validate_goal

    source
    fn Board::validate_goal(self : Board, goal : Goal) -> Unit raise PegError

    Board::verify_solution

    source
    fn Board::verify_solution(self : Board, start : Position, moves : Array[Int], goal : Goal) -> Bool raise PegError

    The whole transcript must be legal and reach the requested goal.

    Board::verify_steps

    source
    fn Board::verify_steps(self : Board, start : Position, goal : Goal, steps : Array[Step]) -> Bool raise PegError

    Cell

    source
    pub(all) struct Cell {
      x : Int
      y : Int
    } derive(Eq, 
    Debug    )

    A hole coordinate. x and y are zero based.

    Generated

    source
    pub(all) struct Generated {
      start : Position
      goal : Position
      solution : Array[Int]
      reached_depth : Bool
    } derive(Eq, 
    Debug    )

    Generated puzzles always carry a forward solution; target depth is a request, not a guarantee.

    Goal

    source
    pub(all) enum Goal {
      AnySingle
      Exact(Position)
    } derive(Eq, 
    Debug    )

    Exact targets must be nonempty, in-bounds occupancies.

    Hint

    source
    pub(all) struct Hint {
      move_id : Int
      report : SearchReport
    } derive(Eq, 
    Debug    )

    Each legal opening is classified independently under its share of one total node budget.

    Jump

    source
    pub(all) struct Jump {
      from : Int
      over : Int
      to : Int
    } derive(Eq, 
    Debug    )

    Jump indices refer to holes, not grid offsets.

    Lattice

    source
    pub(all) enum Lattice {
      Orthogonal
      Triangular
    } derive(Eq, 
    Debug    )

    Triangular coordinates use the axial directions (1,0), (0,1), (1,1) and negatives.

    Outcome

    source
    pub(all) enum Outcome {
      Solved(Array[Int])
      Unsolvable
      Exhausted
    } derive(Eq, 
    Debug    )

    Exhausted is an unknown result, never evidence of impossibility.

    Position

    source
    pub(all) struct Position {
      bits : UInt64
    } derive(Eq, Hash, 
    Debug    )

    An immutable occupancy bitset; indices follow row-major order over holes only.

    Position::count

    source
    fn Position::count(self : Position) -> Int

    SearchReport

    source
    pub(all) struct SearchReport {
      outcome : Outcome
      visited : Int
      cache_hits : Int
    } derive(Eq, 
    Debug    )

    Step

    source
    pub(all) struct Step {
      from : Cell
      to : Cell
    } derive(Eq, 
    Debug    )

    Portable move coordinates, independent of internal move numbering.

    english_board

    source
    fn english_board() -> (Board, Position) raise PegError

    Classic 33-hole English cross, with an empty center.

    parse_board

    source
    fn parse_board(text : String, lattice? : Lattice) -> (Board, Position) raise PegError

    Rectangular ASCII: o=peg, .=empty hole, #=absent. Optional final LF, CRLF accepted.

    triangle_board

    source
    fn triangle_board(side : Int, vacancy : Int) -> (Board, Position) raise PegError

    Triangular preset of side 2..8; vacancy is a row-major hole index.

    version

    source
    fn version() -> String

    Source Files

    Powered by MoonBit

    Site sourceReport issuePackagesBuild queueSkillsStatistics

    © 2026 mooncakes.io