# sudoku-solver Solves a 9×9 Sudoku by recursive backtracking, entirely in the browser. Live: *Originally written in PHP. In 2026 it was rewritten in JavaScript; the PHP version is on the [feature/php](https://github.com/tiennm99/sudoku-solver/tree/feature/php) branch.* ## Running it ```sh npm install npm run dev # http://localhost:8080 ``` ```sh npm run build # static site into dist/ npm run preview ``` ## How it works The solver walks the grid cell by cell. On a blank it tries 1–9, keeps any digit no peer already holds, and recurses; if the rest of the grid cannot be completed it puts the cell back and tries the next digit. A cell's *peers* are the other cells in its row, column, and 3×3 box — one definition in [`src/lib/sudoku/grid.js`](src/lib/sudoku/grid.js) that both the solver and the conflict highlighter read, so the two can never disagree about what a clash is. ### The givens are checked before the search starts Backtracking only validates digits it places itself; it skips over cells that were already filled. So a puzzle whose givens contradict each other — the same digit twice in one row, say — could otherwise come back reported as *solved*, with the contradiction still sitting in it. `solve()` therefore rejects a grid that already has conflicts rather than searching it. The PHP version had this hole; there is a test pinning it shut. ## Puzzle text format The grid round-trips through the 81-character form the original command-line version read: one character per cell, row by row, `0` for a blank. It is under "Puzzle as text" in the UI. ``` 530070000600195000098000060800060003400803001700020006060000280000419005000080079 ``` ## Tests ```sh npm test npm run lint ``` 21 tests cover parsing and formatting, peer computation, conflict detection, and the solver — including that it leaves the caller's grid untouched, preserves every given, refuses contradictory givens, and returns `null` when a puzzle genuinely has no completion. ## Layout ``` src/lib/sudoku/ grid model and solver — no DOM, directly testable src/views/ Svelte components vite/ dev and production configs ``` Plain JavaScript with JSDoc types, Svelte 5, Vite. Deployed to GitHub Pages by [`.github/workflows/deploy.yml`](.github/workflows/deploy.yml) on every push to `main`, gated on lint and tests. ## Credits The backtracking approach follows the worked examples the PHP version cited: [Rosetta Code's Sudoku task](https://rosettacode.org/wiki/Sudoku) and [a gist by thebinarypenguin](https://gist.github.com/thebinarypenguin/4d45ffe87096e508800b5d11544bf2fa). ## License Apache-2.0 — see [LICENSE](LICENSE).