Skip to content

About

n-puzzle via beam search

Resources

Stars

0 stars

Watchers

0 watching

Forks

Latest commit

 

History

4 Commits

Folders and files

NameName
Last commit message
Last commit date
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

N-Puzzle Solver

A full-stack N-puzzle solver for board sizes from 3 x 3 through 16 x 16. The project combines a C++ search engine, Pybind11 Python bindings, a FastAPI REST/WebSocket backend, and a React visualization frontend.

N-puzzle solver frontend

Architecture

n-puzzle-solver/
├── engine/                         # C++ puzzle model and search engine
│   ├── include/puzzle/             # Public C++ headers
│   ├── src/                        # Solver, CLI, and Pybind11 bindings
│   ├── CMakeLists.txt              # Builds the Python extension
│   └── Makefile                    # Builds the standalone CLI
├── backend/
│   ├── pyproject.toml              # Python dependencies managed by uv
│   └── server.py                   # FastAPI REST and WebSocket endpoints
└── frontend/
    ├── src/components/             # Board, controls, and telemetry chart
    ├── src/services/               # REST and WebSocket clients
    ├── src/types/puzzle.ts         # Shared frontend message types
    └── vite.config.ts              # Vite configuration and dev proxies

The browser requests a reachable scrambled board from POST /api/scramble. When a search starts, it sends the displayed board and search parameters to WS /ws/solve. The backend runs the native solver outside the asyncio event loop and streams telemetry followed by the complete solution path. The frontend plots the telemetry and animates the returned path.

Features and algorithms

  • Supports puzzle sizes from 3 x 3 to 16 x 16.
  • Checks whether a puzzle is solvable before searching.
  • Uses a hybrid beam-search solver with Manhattan distance and linear-conflict heuristics.
  • Streams search progress and the solution path to the frontend in real time.
  • Provides solution playback, configurable search settings, and custom-image tiles.

Prerequisites

  • A C++ compiler
  • CMake 3.18 or newer and Make
  • Python 3.13 or newer
  • uv
  • Node.js and npm

Run the full application

1. Install the backend dependencies

cd backend
uv sync

2. Build the Pybind11 extension

From the engine directory, configure CMake with the backend virtual environment:

cd ../engine
cmake -B build \
  -DPYTHON_EXECUTABLE=../backend/.venv/bin/python \
  -Dpybind11_DIR=$(../backend/.venv/bin/python -m pybind11 --cmakedir)
cmake --build build

The build writes cpp_puzzle_engine.cpython-*.so into backend/.

3. Start the backend

cd ../backend
uv run python server.py

The API listens on http://127.0.0.1:8000.

4. Start the frontend

In a second terminal:

cd frontend
npm install
npm run dev

Open the URL printed by Vite (normally http://localhost:5173). During development, Vite proxies /api and /ws to the backend on port 8000.

For more frontend details, see frontend/README.md.

Standalone C++ CLI

The CLI creates a deterministically scrambled board and accepts gridSize, beamWidth, and maxPathLength arguments:

cd engine
make
./bin/n_puzzle_solver 8 1000 1000

maxPathLength is applied to each search stage rather than to the combined solution path.

Python usage

Run this from backend/ after building the extension:

import cpp_puzzle_engine

state = cpp_puzzle_engine.PuzzleState(4)
state.scramble(100, 42)
print("Is solvable?", state.is_solvable())


def on_telemetry(stats):
    if stats.localDepth % 5 == 0:
        print(
            f"Local depth: {stats.localDepth} | "
            f"Best h: {stats.bestHeuristic} | "
            f"Frontier: {stats.frontierSize}"
        )


result = cpp_puzzle_engine.solve_beam_search(
    start_state=state,
    beam_width=1000,
    max_path_length=1000,
    callback=on_telemetry,
)

if result.solved:
    print(f"Solved in {result.finalDepth} steps ({result.durationMs:.2f} ms)")
    print(f"Evaluated {result.totalNodesEvaluated} states")
else:
    print("No solution was found within the configured search limits")

About

n-puzzle via beam search

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages