See the demo at https://go.ncsu.edu/sudoku.
Generalized CSP (constraint satisfaction problem) solver in Python 3.13+. The repository also includes a full-stack Sudoku web app: FastAPI backend, Vue 3 + TypeScript frontend, Docker Compose orchestration, and Nginx reverse proxy.
docker compose upBackend on :8000, frontend on :3000.
The backend uses
uv for package management; the frontend uses npm.
cd backend
uv sync
uv run uvicorn csp_solver.api.main:app --reload --port 8000cd frontend
npm install
npm run devdocker compose -f docker-compose.prod.yml upNginx reverse proxy on :80. Configure environment via .env (see .env.example).
The core CSP class (backend/src/csp_solver/solver/csp.py) accepts three configuration
options: pruning_type, variable_ordering, and max_solutions.
Pruning strategy for backtracking search:
FORWARD_CHECKING- Forward checking.
AC3- Maintaining arc consistency (MAC), variant 3.
AC_FC- AC + forward checking hybrid; low-order variant of AC-1.
NO_PRUNING- No pruning.
These pruning strategies are only applicable given a backtracking solver: if one's using the min-conflicts hill-climbing solver, no pruning at any stage is done.
Variable selection heuristic during search:
NO_ORDERING- Chronological ordering used.
FAIL_FIRST- Implementation of the DVO "fail-first" scheme (MRV heuristic).
max_solutions caps the number of solutions returned. Defaults to 1.
Once the CSP object is created, a set of variables, domains, and constraints must be added to it before solving.
Here's an example of implementing map coloring using our API (shortened for readability).
variables = [
"Western Australia",
"Northern Territory",
"South Australia",
"Queensland",
"New South Wales",
"Victoria",
"Tasmania",
]
domain = ["red", "green", "blue"]
csp = CSP(pruning_type, variable_ordering, max_solutions)
csp.add_variables(domain, *variables)
csp.add_constraint(
map_coloring_constraint("Western Australia", "Northern Territory")
)
csp.add_constraint(map_coloring_constraint("Western Australia", "South Australia"))
csp.add_constraint(map_coloring_constraint("South Australia", "Northern Territory"))
csp.add_constraint(map_coloring_constraint("Queensland", "Northern Territory"))
csp.add_constraint(map_coloring_constraint("Queensland", "South Australia"))
csp.add_constraint(map_coloring_constraint("Queensland", "New South Wales"))
csp.add_constraint(map_coloring_constraint("New South Wales", "South Australia"))
csp.add_constraint(map_coloring_constraint("Victoria", "South Australia"))
csp.add_constraint(map_coloring_constraint("Victoria", "New South Wales"))Constraints use one extra convention: a constraint factory returns a tuple of a checker function and the variables associated with that checker.
Example:
def lambda_constraint(func: Callable[[Any], bool], *variables):
def check(current_solution: Solution):
current_values = get_current_solution_values(variables, current_solution)
if len(variables) == len(current_values):
return func(*current_values)
else:
return True
return check, list(variables)The inner function, check, consumes the current solution and returns a boolean. If the
constraint is not yet fully assigned, it returns True so search can continue.
The outer function returns check and the constrained variable list:
csp.add_constraint(map_coloring_constraint("Victoria", "New South Wales"))Futoshiki and Sudoku are implemented atop the CSP engine:
futoshiki.py: command-line solver, reads puzzle from input file (grid values + inequality constraints).sudoku.py: board generation with difficulty calibration, uniqueness enforcement, and pre-computed solution banks.
The backend is FastAPI; the frontend is Vue 3 + TypeScript with a hand-drawn SVG rendering stack. UI features:
- Path-based line boil on the grid (4 pre-computed variants cycled at ~6.7fps)
- Custom SVG glyphs with draw-in and hover wiggle
- Rough.js decorative elements (vine border, doodle accents)
- Stroke-dashoffset draw-ins (~800ms with seeded jitter)
- Theme-aware celestial wobble effects
- Live filter/boil tuner
Core boil and path primitives come from
@mkbabb/pencil-boil. Sudoku-specific grid
path generation remains local in frontend/src/lib/gridPaths.ts.
Library animation internals are documented in
pencil-boil/README.md.
The Sudoku API exposes three routes:
| Method | Path | Purpose |
|---|---|---|
| GET | /api/v1/board/random/{size}/{difficulty} |
Generate random board |
| POST | /api/v1/board/solve |
Solve input board |
| GET | /api/v1/health |
Health check |
The CSP solver supports arbitrary subgrid sizes. Due to rendering and compute constraints, the UI currently exposes subgrid sizes 2, 3, and 4 (4×4, 9×9, and 16×16).
Size 3 is the default path. A set of 100 seed boards is used to generate size-3 boards. Pre-computed solution banks exist for sizes 2 through 5.
Board generation uses two strategies. The fast path, used when pre-computed templates exist, selects a random template and applies a random Sudoku symmetry transform: digit permutation, row/column permutation within bands and stacks, band/stack permutation, and transposition. For N=3, this symmetry group yields ~1.22 billion distinct grids per base template. Generation on this path is O(M²) per transform application—no search required.
When templates are unavailable, the solver falls back to generate-and-reduce: generate a
complete solution, remove cells with uniqueness verification, and calibrate difficulty
by backtrack count. Templates reside in
backend/src/csp_solver/data/sudoku_puzzles/{N}/{difficulty}/. The offline generation
script is backend/scripts/generate_templates.py.
Difficulty is calibrated by the solver's backtrack count:
- Easy: 0 backtracks (solvable by constraint propagation alone)
- Medium: < 50 backtracks
- Hard: > 100 backtracks