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/
├── 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.
- 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.
- A C++ compiler
- CMake 3.18 or newer and Make
- Python 3.13 or newer
uv- Node.js and npm
cd backend
uv syncFrom 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 buildThe build writes cpp_puzzle_engine.cpython-*.so into backend/.
cd ../backend
uv run python server.pyThe API listens on http://127.0.0.1:8000.
In a second terminal:
cd frontend
npm install
npm run devOpen 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.
The CLI creates a deterministically scrambled board and accepts gridSize, beamWidth, and maxPathLength arguments:
cd engine
make
./bin/n_puzzle_solver 8 1000 1000maxPathLength is applied to each search stage rather than to the combined solution path.
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")