N-Puzzle (Rust)

Elegant, fast, and thoughtfully engineered N-Puzzle solvers in Rust. The repository contains two focused crates that share the same spirit—clarity, performance, and great developer ergonomics—while targeting different scopes.

• mandatory: A* solver with solid heuristics and a friendly TUI wizard
• bonus: Everything in mandatory plus extra search modes (Uniform-cost, Greedy)

Project layout

• mandatory/ — crate name npuzzle
• bonus/ — crate name npuzzle-bonus

Both crates include:

• An interactive mode designed for smooth exploration
• A generate subcommand to create solvable sample inputs in inputs/
• Heuristics: Manhattan, Manhattan + Linear Conflict (default), Misplaced tiles
• Optional summary output and a Markdown report at target/npuzzle_report.md

Crates at a glance

• mandatory (crate: npuzzle)

• Core: A* search with rigorously chosen heuristics
• Experience: Friendly interactive wizard, readable colored output
• Deliverable: A compact, reliable solver that showcases informed search done right

• bonus (crate: npuzzle-bonus)

• Exploration: Compare search strategies side-by-side (A*, Uniform-cost, Greedy)
• Insight: Designed for experiments, profiling, and "why this path?" reasoning
• Everything from mandatory with the breadth to study trade-offs

What makes it solid

• Search built for insight: clear separation of grid, heuristic, a_star, and solver modules. Each piece does one job well.
• Heuristics that matter:
  • Manhattan distance
  • Manhattan + Linear Conflict (default for balance of speed and admissibility)
  • Misplaced tiles (didactic baseline)
• Deterministic input generation: reproducible, guaranteed-solvable instances for 3×3, 4×4, and 5×5 in inputs/.
• Thoughtful reporting: a concise Markdown report is written to target/npuzzle_report.md with timing, memory, expansions, and the move sequence.
• Ergonomic UX: an interactive wizard that guides you from choosing an input to selecting a heuristic or search mode.
• Rust-first performance: tight release settings, zero-unsafe code, and rustc-hash for fast closed-set lookups.

Algorithms and design

• State model: canonical goal layout and robust parity checks ensure solvability guarantees for generated puzzles.
• Priority-queue search: A* uses f(n) = g(n) + h(n) with careful tie-breaking to reduce churn in open sets.
• Memory efficiency: compact nodes, stable hashing, and measured peak memory in reports for practical comparisons.
• Bonus strategy matrix: Uniform-cost (pure g), Greedy (pure h), and A* (g+h) make the trade-space tangible—optimality vs. expansion vs. speed.

Inputs and outputs

• Inputs: text files under inputs/ (and any custom file you provide). The interactive flow will list what it finds and accept manual paths.
• Outputs: a human-friendly summary on screen and a Markdown report at target/npuzzle_report.md for durable artifacts and sharing.

Why two crates?

• mandatory captures the essence: a sharp A* implementation with high-signal defaults and minimal ceremony.
• bonus opens the lab doors: flip a search mode, swap heuristics, and learn by comparing—without compromising on code quality.

Quality bar

• Strict compile settings, clippy on warnings-as-errors, and tuned release profiles ensure consistency and speed.
• Clear module boundaries invite reading the code—a_star.rs, heuristic.rs, grid.rs, and solver.rs are intentionally approachable.

If you’re here to study search, this codebase is a friendly place to start; if you’re here to ship, it’s already fast.