Sudoku, in nine colors

Solve any standard 9×9 Sudoku using exact graph coloring, and watch the actual search.

Try the live solver · Download the video · How it works

81 vertices. 810 edges. Nine colors. No stored answer grids or third-party Sudoku solver.

The browser app runs entirely on your device. Enter your own clues, paste a puzzle, or try the bundled examples. It checks for a second solution, distinguishes conflicting clues from an impossible puzzle, and lets you replay assignments, dead ends, and backtracking.

Use it

Open the live demo. Enter digits in the grid, or expand Paste a puzzle and enter 81 digits or nine rows. Use 0 or . for blanks, then press Solve.

• Show solution displays the computed answer. Copy solution copies nine rows.
• Play trace, the step arrows, the timeline, and playback speed let you inspect the search.
• Download trace exports the puzzle, graph, answer, search statistics, and recorded events as JSON.
• Reset to clues removes the result; Clear starts an empty board.
• Search settings controls uniqueness checking and the time limit. Cancel search stops the worker.

You can also download this repository and open web/index.html directly in a modern browser. No build, account, API key, or Python installation is needed for the browser app. To serve it locally:

git clone https://github.com/ChetasLua/sudoku-graph-coloring.git
cd sudoku-graph-coloring
python3 app.py --open

The local server needs Python 3.10+ and no extra packages. On macOS, Open Sudoku.command starts it as well.

What “any Sudoku” means

Arbitrary standard 9×9 puzzles with 3×3 boxes are accepted; the input is never matched against an answer database. Exact backtracking is complete if allowed to finish. Conflicting clues are rejected, a search with no solution is reported as impossible only after all branches are exhausted, and two solutions prove ambiguity.

Difficult or underconstrained inputs can take substantial search. The browser defaults to 30 seconds; choose a longer limit or No time limit if needed. A timeout reports an incomplete search, or a valid first solution with uniqueness still unknown. Diagonal, killer, irregular, and other Sudoku variants are not supported.

To bound memory, the browser records at most the first 20,000 events. This does not stop the search. A truncated replay is explicitly labeled, and Show solution displays the separately computed answer. Exported JSON includes trace_complete: false; omitted events are never invented. Playback speed may skip displaying intermediate frames; the recorded events remain available through the timeline and JSON export.

The graph coloring technique

1. Make each Sudoku cell a vertex: 81 vertices.
2. Connect cells that share a row, column, or 3×3 box: 810 undirected edges, with 20 neighbors per vertex.
3. Treat digits 1–9 as colors. Givens precolor the graph and cannot change.
4. Choose an uncolored vertex with the most distinct colors among its neighbors (DSATUR). Ties favor the cell nearest the previous selection, then the lowest cell index.
5. Try each legal color in ascending order. Backtrack if a branch cannot be completed.
6. A complete proper 9-coloring is a valid Sudoku solution. Continue searching for a second coloring to check uniqueness.

The browser implementation is in web/solver.js. A Web Worker runs that exact function so search does not freeze the interface. The original Python implementation in solver.py generated the video. Tests compare their solutions and entire first-solution traces, and a separate verifier checks the moves against Sudoku constraints.

Mathematical background: NetworkX Sudoku graph guide.

Python CLI

python3 solver.py --puzzle-file puzzles/demo.txt --out qa/my-trace.json
python3 solver.py --puzzle-file puzzles/backtracking.txt --out qa/backtracking.json
python3 solver.py --puzzle "530070000600195000098000060800060003400803001700020006060000280000419005000080079"
python3 verify.py qa/my-trace.json

--first-only skips uniqueness checking; --timeout 120 allows a longer search. The original Python recorder stops at 100,000 recorded events or its time limit (20 seconds by default) and reports the limit explicitly. Use the browser engine for search that continues beyond its recording limit. Python exits with code 0 when a solution is found and 2 for invalid, incomplete, or unsatisfiable input; inspect unique in the JSON when uniqueness matters.

The original video

web/assets/sudoku-graph-coloring.mp4 is included in this repository: 2560×1440, 16:9, 60 fps, 16 seconds, silent, without titles, captions, or a watermark. Watch it in the live demo or download the MP4.

The animation replays the Python solver’s computed states with readable timing. 16 seconds is the playback length, not the computation time. The recorded puzzle takes 51 assignments without backtracking; the separate backtracking example exposes failed branches and undo events. After solving, graph vertices regroup by color for the final composition. This changes the layout only, preserving vertex identities, edges, and colors. The final number reveal is also presentation.

The video is our own rendered animation, inspired by TheMathFlow’s graph-theory animation. No footage from the reference is included.

Verify the evidence

Python 3.10+ and Node.js 22+ are sufficient for the code tests; no third-party packages are required:

python3 -m unittest -v
python3 verify.py evidence/solver-trace.json
python3 scripts/check_evidence.py

Tests cover the video puzzle, genuine backtracking, impossible and ambiguous puzzles, already completed grids, malformed and conflicting clues, timeouts, limited recording, and twelve digit/row/column/transpose transformations. verify.py does not import either solver: it independently constructs all 27 Sudoku units, reconstructs every edge, replays the trace, and checks the final grid. A separate bitmask search checks solution multiplicity.

The shipped evidence/video-state-audit.json records 8,262 successful cell/node color checks across all 51 solver states in the decoded MP4. Checksums in MANIFEST.sha256 tie the original Python source, trace, and video together. That pixel audit is specific to this video; it is not a claim that every possible puzzle has been tested.

Render or audit the film

Rendering is optional; the browser solver has no rendering dependencies.

python3 -m venv .venv
# Activate .venv using your shell, then:
python3 -m pip install -r requirements-render.txt
python3 make_video.py all
python3 audit_video.py --manifest qa/film-manifest.json

The rebuilt MP4 goes into work/, leaving the published video unchanged. --output path/to/movie.mp4 changes its destination. --font path/to/font.ttf chooses a local font; the default uses Avenir Next when available and system sans-serif otherwise. Fonts can change the pixels, but not the solver trace. No font files are bundled.

To recheck the shipped video rather than a new render:

python3 audit_video.py

The pixel audit samples every assignment in the bundled monotone example. The independent trace verifier also supports backtracking. Changing puzzles/demo.txt makes the renderer compute a new trace; longer traces produce longer animations. The renderer is intended for short illustrative puzzles.

Project map

Path	Purpose
web/	Self-contained browser app, exact JS solver, and video
solver.py	Original Python graph-coloring solver and CLI
verify.py	Independent Sudoku/graph/trace validation
test_solver.py, test_browser_solver.py	Behavioral tests and cross-language parity
make_video.py, audit_video.py	Film renderer and decoded-pixel audit
evidence/	Original trace, film manifest, and verification reports
scripts/	Static-site build, CLI test adapter, and evidence checks
.github/workflows/	Tests and GitHub Pages deployment

Contributing and license

Bug reports and pull requests are welcome. Include the input puzzle and expected behavior when reporting solver issues. Run python3 -m unittest -v before proposing a change. Keep solver decisions separate from animation timing, and preserve honest incomplete/ambiguous statuses.

MIT licensed, including the original code and video in this repository. Optional dependencies retain their own licenses.