mirror of
https://github.com/tiennm99/sudoku-solver.git
synced 2026-10-14 06:18:04 +00:00
84 lines
2.7 KiB
Markdown
84 lines
2.7 KiB
Markdown
# sudoku-solver
|
||
|
||
Solves a 9×9 Sudoku by recursive backtracking, entirely in the browser.
|
||
|
||
Live: <https://tiennm99.github.io/sudoku-solver/>
|
||
|
||
*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).
|