aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib')
-rw-r--r--src/lib/Saving.ts11
-rw-r--r--src/lib/Sudoku.ts80
-rw-r--r--src/lib/bestes.html4
-rw-r--r--src/lib/bestest.js555
-rw-r--r--src/lib/helpers.ts16
-rw-r--r--src/lib/sudoku/solve.ts35
-rw-r--r--src/lib/sudoku/validation.ts57
7 files changed, 701 insertions, 57 deletions
diff --git a/src/lib/Saving.ts b/src/lib/Saving.ts
index 0d71057..8017fd1 100644
--- a/src/lib/Saving.ts
+++ b/src/lib/Saving.ts
@@ -8,18 +8,19 @@ export function save(grid: Grid) {
a.download = "sudoku-save.json";
a.click();
}
-export function readGridFromFile(f: File): Promise<string[][] | null> {
+export function readGridFromFile(f?: File): Promise<string[][] | null> {
return new Promise(res => {
let reader = new FileReader();
reader.onload = e => {
try {
- //@ts-expect-error
- const json = JSON.parse(e.target.result);
- res(json)
+ if (typeof e.target?.result === "string")
+ res(JSON.parse(e.target.result))
+ else
+ res(null)
} catch (error) {
res(null)
}
};
- reader.readAsText(f);
+ f ? reader.readAsText(f) : f;
})
}
diff --git a/src/lib/Sudoku.ts b/src/lib/Sudoku.ts
index 94b972e..879185a 100644
--- a/src/lib/Sudoku.ts
+++ b/src/lib/Sudoku.ts
@@ -1,57 +1,33 @@
-export type Grid = Array<Array<string>>;
-export type Coord = { x: number; y: number };
-
-export function validate(board: Grid) {
- const bads = [] as Coord[];
- for (let i = 0; i < 9; i++) {
- for (let j = 0; j < 9; j++) {
- const value = board[i][j];
- if (value !== '.') {
- if (!validateRow(board, i, j, value) || !validateColumn(board, i, j, value) || !validateBox(board, i, j, value)) {
- bads.push({ x: i, y: j })
- }
- }
- }
- }
- return bads;
-};
-
-function validateRow(board: Grid, row: number, col: number, value: string) {
- for (let j = 0; j < 8; j++) {
- if (j !== col) {
- if (board[row][j] === value) {
- return false;
- }
- }
- }
-
- return true;
-}
-
-function validateColumn(board: Grid, row: number, col: number, value: string) {
- for (let i = 0; i < 8; i++) {
- if (i !== row) {
- if (board[i][col] === value) {
- return false;
- }
- }
- }
+//@ts-expect-error
+import _sudoku from "sudoku-umd";
+//@ts-expect-error
+import _sudoku2_ from "sudoku-solver-js";
- return true;
-}
+const _sudoku2 = new _sudoku2_();
-function validateBox(board: Grid, row: number, col: number, value: string) {
- const startRow = row - (row % 3), startCol = col - (col % 3);
+const sudoku: {
+ solve(arg0: string): string,
+ board_string_to_grid(arg0: string): string[][],
+ board_grid_to_string(arg0: string[][]): string,
+ get_candidates(arg0: string): string[][],
+ print_board(arg0: string): void,
+} = _sudoku;
- for (let i = startRow; i < startRow + 3; i++) {
- for (let j = startCol; j < startCol + 3; j++) {
- if (i !== row && j !== col) {
- if (board[i][j] === value) {
- return false;
- }
- }
- }
- }
+export type Grid = Array<Array<string>>;
+export type NGrid = Array<Array<number>>;
+export type Coord = { x: number; y: number };
+export * from "./sudoku/validation";
- return true;
+export function solve(grid: Grid) {
+ return sudoku.board_string_to_grid(_sudoku2.solve(sudoku.board_grid_to_string(grid)))
}
+// function grid2NGrid(grid: Grid): NGrid {
+// return grid.map(
+// row => row.map(t => t === "." ? 0 : parseInt(t))
+// )
+// }
+// function ngrid2Grid(ngrid: NGrid): Grid {
+// return ngrid.map(
+// row => row.map(t => t === 0 ? "." : t.toString())
+// )
+// }
diff --git a/src/lib/bestes.html b/src/lib/bestes.html
new file mode 100644
index 0000000..e452cef
--- /dev/null
+++ b/src/lib/bestes.html
@@ -0,0 +1,4 @@
+<body>
+ <script src="bestest.js"></script>
+ <script>new Sudoku(document.body)</script>
+</body>
diff --git a/src/lib/bestest.js b/src/lib/bestest.js
new file mode 100644
index 0000000..6ff9196
--- /dev/null
+++ b/src/lib/bestest.js
@@ -0,0 +1,555 @@
+class Sudoku {
+ constructor(container, { controls = true, pauseOnGuess = false } = {}) {
+ this.container = container;
+ this._pauseOnGuess = pauseOnGuess;
+ this.init(controls);
+
+ if (controls) {
+ container.querySelector(".js-examples-select").addEventListener("change", ev => {
+ this.writeBoard(ev.target.value.split(",").map(parseFloat), true);
+ });
+ container.querySelector(".js-examples-select").addEventListener("click", ev => {
+ this.writeBoard(ev.target.value.split(",").map(parseFloat), true);
+ });
+ container.querySelector(".js-solve").addEventListener("click", ev => this.solve());
+ container.querySelector(".js-play").addEventListener("click", ev => this.stepSolve());
+ container.querySelector(".js-pause").addEventListener("click", ev => this.pause());
+ container.querySelector(".js-continue").addEventListener("click", ev => this.continue());
+ container.querySelector(".js-reset").addEventListener("click", ev => this.reset());
+ container.querySelector(".js-clear").addEventListener("click", ev => this.clearBoard());
+ }
+ }
+
+ init(controls = true) {
+ let container = this.container;
+ let html = `\
+ <div class="sudoku">
+ <div class="sudoku-board">
+ ${[...Array(81).keys()].map(i => {
+ let { row, col } = i2rc(i);
+ return `<input class="js-field" maxlength="1" type="text" data-index="${i}" data-row="${row}" data-col="${col}" />`;
+ }).join("")}
+ </div>
+ <div class="controls">
+ ${!controls ? '' : `
+ <select class="js-examples-select">
+ <option selected disabled hidden>Examples</option>
+ ${examples.map(example => `
+ <option value="${example.slice(1).join(",")}">${example[0]}</option>
+ `).join("")}
+ </select>
+ <button class="js-solve">Solve!</button>
+ <button class="js-play">Play</button>
+ <button class="js-pause">Pause</button>
+ <button class="js-continue">Continue</button>
+ <button class="js-reset">Reset</button>
+ <button class="js-clear">Clear</button>`}
+ <div class="stats js-console"></div>
+ </div>
+ </div>`;
+ container.innerHTML = html;
+ let fields = container.querySelectorAll("input.js-field");
+ fields.forEach(input => {
+ input.addEventListener("click", ev => {
+ input.focus();
+ input.select();
+ });
+ input.addEventListener("focus", ev => {
+ let index = +input.dataset.index;
+ log(container, `Allowed digits:
+ ${b2ds(analyze(this.readBoard()).allowed[index]).join(", ")}`);
+ });
+ input.addEventListener("keydown", ev => {
+ let idx = +input.dataset.index;
+ if (ev.keyCode >= 48 && ev.keyCode <= 57) {
+ input.value = String.fromCharCode(ev.keyCode);
+ if (input.value == "0") input.value = "";
+ input.select();
+ ev.preventDefault();
+ } else {
+ let parent = input.parentNode;
+ let next;
+ switch (ev.keyCode) {
+ case 38: // ↑
+ next = idx - 9; break;
+ case 40: // ↓
+ next = idx + 9; break;
+ case 39: // →
+ next = idx + 1; break;
+ case 37: // ←
+ next = idx - 1; break;
+ }
+ if (next != null) {
+ if (next < 0) next += 81;
+ next %= 81;
+ next = parent.querySelector(`input[data-index="${next}"]`);
+ next.focus();
+ next.select();
+ ev.preventDefault();
+ }
+ }
+ });
+ });
+ }
+
+ pause() {
+ clearTimeout(this._playTimer);
+ this.container.classList.add("paused");
+ }
+
+ continue() {
+ this.container.classList.remove("paused");
+ this._playCont();
+ }
+
+ readBoard(init = false) {
+ return [...this.container.querySelectorAll("input.js-field")]
+ .map(el => {
+ if (init) el.classList.toggle("init", el.value);
+ return el.value ? d2b(parseInt(el.value, 10)) : 0;
+ });
+ }
+
+ writeBoard(values, init = false) {
+ let el = this.container;
+ [...el.querySelectorAll("input.js-field")].forEach((el, i) => {
+ el.value = values[i] || "";
+ el.classList.remove("current");
+ if (init) {
+ el.classList.toggle("init", values[i]);
+ }
+ });
+ if (init) {
+ this._initBoard = values;
+ this._reset();
+ }
+ }
+
+ writeBytes(values, init = false) {
+ this.writeBoard(values.map(b2d), init);
+ }
+
+ clearBoard() {
+ let el = this.container;
+ [...el.querySelectorAll("input.js-field")].forEach(el => {
+ el.value = "";
+ el.classList.remove("init");
+ });
+ this._reset();
+ }
+
+ reset() {
+ this.writeBoard(this._initBoard || [], true);
+ }
+
+ _reset() {
+ let el = this.container;
+ clearTimeout(this._playTimer);
+ el.classList.remove("solved", "playing", "paused");
+ log(el, "");
+ }
+
+ solve() {
+ let self = this;
+ let el = self.container;
+ let board = self.readBoard(true);
+ let backtrack = 0;
+ let guesswork = 0;
+ let dcount = 0;
+ let time = Date.now();
+ if (solve()) {
+ stats();
+ self.writeBytes(board);
+ el.classList.add("solved");
+ } else {
+ stats();
+ alert("no solution");
+ }
+ function solve() {
+ let { index, moves, len } = analyze(board);
+ if (index == null) return true;
+ if (len > 1) guesswork++;
+ for (let m = 1; moves; m <<= 1) {
+ if (moves & m) {
+ dcount++;
+ board[index] = m;
+ if (solve()) return true;
+ moves ^= m;
+ }
+ }
+ board[index] = 0;
+ ++backtrack;
+ return false;
+ }
+ function stats() {
+ log(el, `${dcount} digits placed<br>${backtrack} take-backs<br>${guesswork} guesses<br>${Date.now() - time} milliseconds`);
+ }
+ }
+
+ stepSolve() {
+ let self = this;
+ let el = self.container;
+ el.classList.add("playing");
+ let board = self.readBoard(true);
+ let backtrack = 0;
+ let guesswork = 0;
+ let dcount = 0;
+ solve(success => {
+ log(el, `${backtrack} take-backs<br>${guesswork} guesses`);
+ el.classList.remove("playing");
+ if (success) {
+ self.writeBytes(board);
+ el.classList.add("solved");
+ } else {
+ alert("no solution");
+ }
+ });
+ function solve(cb) {
+ let { index, moves, len } = analyze(board);
+ if (index == null) return cb(true);
+ if (self._pauseOnGuess) {
+ el.querySelector(`input[data-index="${index}"]`).classList.add("current");
+ }
+ if (len > 1) {
+ guesswork++;
+ if (self._pauseOnGuess) {
+ self._playCont = () => loop(moves, 1);
+ stats();
+ self.pause();
+ return;
+ }
+ }
+ function loop(moves, m) {
+ if (!moves) {
+ board[index] = 0;
+ ++backtrack;
+ stats();
+ cb(false);
+ } else if (moves & m) {
+ dcount++;
+ stats();
+ board[index] = m;
+ self.writeBytes(board);
+ el.querySelector(`input[data-index="${index}"]`).classList.add("current");
+ self._playTimer = setTimeout(self._playCont = () =>
+ solve(success => success ? cb(true) : loop(moves ^ m, m << 1)), 100);
+ } else loop(moves, m << 1);
+ };
+ loop(moves, 1);
+ }
+ function stats() {
+ log(el, `${dcount} digits placed<br>${backtrack} take-backs<br>${guesswork} guesses`);
+ }
+ }
+}
+
+function i2rc(index) {
+ return { row: index / 9 | 0, col: index % 9 };
+}
+
+function rc2i(row, col) {
+ return row * 9 + col;
+}
+
+function d2b(digit) {
+ return 1 << (digit - 1);
+}
+
+function b2d(byte) {
+ for (var i = 0; byte; byte >>= 1, i++);
+ return i;
+}
+
+function b2ds(byte) {
+ let digits = [];
+ for (let i = 1; byte; byte >>= 1, i++)
+ if (byte & 1) digits.push(i);
+ return digits;
+}
+
+function log(el, txt) {
+ let out = el.querySelector(".js-console");
+ if (out)
+ out.innerHTML = txt;
+}
+
+function getMoves(board, index) {
+ let { row, col } = i2rc(index);
+ let r1 = 3 * (row / 3 | 0);
+ let c1 = 3 * (col / 3 | 0);
+ let moves = 0;
+ for (let r = r1, i = 0; r < r1 + 3; r++) {
+ for (let c = c1; c < c1 + 3; c++, i++) {
+ moves |= board[rc2i(r, c)]
+ | board[rc2i(row, i)]
+ | board[rc2i(i, col)];
+ }
+ }
+ return moves ^ 511;
+}
+
+function unique(allowed, index, value) {
+ let { row, col } = i2rc(index);
+ let r1 = 3 * (row / 3 | 0);
+ let c1 = 3 * (col / 3 | 0);
+ let ir = 9 * row;
+ let ic = col;
+ let uniq_row = true, uniq_col = true, uniq_3x3 = true;
+ for (let r = r1; r < r1 + 3; ++r) {
+ for (let c = c1; c < c1 + 3; ++c, ++ir, ic += 9) {
+ if (uniq_3x3) {
+ let i = rc2i(r, c);
+ if (i != index && allowed[i] & value) uniq_3x3 = false;
+ }
+ if (uniq_row) {
+ if (ir != index && allowed[ir] & value) uniq_row = false;
+ }
+ if (uniq_col) {
+ if (ic != index && allowed[ic] & value) uniq_col = false;
+ }
+ if (!(uniq_3x3 || uniq_row || uniq_col)) return false;
+ }
+ }
+ return uniq_row || uniq_col || uniq_3x3;
+}
+
+function analyze(board) {
+ let allowed = board.map((x, i) => x ? 0 : getMoves(board, i));
+ let bestIndex, bestLen = 100;
+ for (let i = 0; i < 81; i++) if (!board[i]) {
+ let moves = allowed[i];
+ let len = 0;
+ for (let m = 1; moves; m <<= 1) if (moves & m) {
+ ++len;
+ if (unique(allowed, i, m)) {
+ allowed[i] = m;
+ len = 1;
+ break;
+ }
+ moves ^= m;
+ }
+ if (len < bestLen) {
+ bestLen = len;
+ bestIndex = i;
+ if (!bestLen) break;
+ }
+ }
+ return {
+ index: bestIndex,
+ moves: allowed[bestIndex],
+ len: bestLen,
+ allowed: allowed
+ };
+}
+
+const examples = [
+ ["Medium 1",
+ 0, 0, 0, 0, 0, 0, 0, 0, 6,
+ 0, 3, 0, 0, 7, 1, 0, 4, 0,
+ 0, 0, 0, 0, 0, 0, 8, 0, 0,
+
+ 0, 0, 0, 9, 0, 8, 0, 7, 1,
+ 1, 0, 3, 0, 0, 0, 0, 0, 0,
+ 0, 0, 2, 0, 3, 0, 9, 0, 0,
+
+ 5, 0, 7, 0, 0, 6, 0, 0, 0,
+ 2, 0, 0, 0, 0, 0, 7, 0, 0,
+ 0, 0, 1, 8, 0, 0, 0, 0, 2,
+ ],
+ ["Medium 2",
+ 0, 0, 0, 0, 1, 7, 2, 0, 0,
+ 0, 0, 0, 4, 0, 0, 0, 0, 0,
+ 0, 0, 9, 0, 0, 3, 0, 0, 0,
+
+ 4, 0, 0, 7, 8, 0, 5, 0, 0,
+ 0, 2, 5, 0, 0, 0, 8, 0, 0,
+ 0, 0, 0, 6, 0, 0, 0, 0, 0,
+
+ 6, 0, 1, 5, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 6, 0, 3, 0,
+ 2, 0, 0, 0, 0, 1, 7, 0, 4,
+ ],
+ ["Medium 3",
+ 9, 0, 0, 5, 0, 1, 7, 0, 0,
+ 2, 0, 1, 0, 0, 9, 0, 0, 0,
+ 0, 0, 0, 8, 7, 0, 0, 9, 0,
+
+ 0, 8, 0, 0, 6, 4, 0, 7, 0,
+ 0, 0, 0, 0, 0, 0, 2, 1, 0,
+ 0, 0, 0, 0, 9, 0, 0, 0, 0,
+
+ 7, 0, 6, 2, 4, 0, 0, 0, 0,
+ 0, 4, 0, 0, 0, 0, 0, 0, 6,
+ 1, 0, 0, 0, 0, 0, 0, 4, 0,
+ ],
+ ["Medium 4",
+ 0, 0, 0, 0, 3, 0, 5, 7, 0,
+ 0, 0, 2, 0, 0, 8, 0, 0, 0,
+ 6, 0, 0, 0, 0, 0, 0, 0, 0,
+
+ 0, 3, 0, 5, 7, 0, 0, 4, 0,
+ 0, 0, 0, 4, 0, 0, 0, 0, 2,
+ 0, 0, 5, 6, 0, 0, 7, 1, 8,
+
+ 0, 7, 8, 0, 0, 0, 0, 0, 0,
+ 0, 0, 6, 7, 0, 9, 0, 0, 1,
+ 0, 0, 0, 0, 0, 0, 0, 2, 0,
+ ],
+ ["Hard",
+ 8, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 3, 6, 0, 0, 0, 0, 0,
+ 0, 7, 0, 0, 9, 0, 2, 0, 0,
+
+ 0, 5, 0, 0, 0, 7, 0, 0, 0,
+ 0, 0, 0, 0, 4, 5, 7, 0, 0,
+ 0, 0, 0, 1, 0, 0, 0, 3, 0,
+
+ 0, 0, 1, 0, 0, 0, 0, 6, 8,
+ 0, 0, 8, 5, 0, 0, 0, 1, 0,
+ 0, 9, 0, 0, 0, 0, 4, 0, 0,
+ ],
+ ["Harder",
+ 0, 0, 3, 9, 0, 0, 0, 0, 0,
+ 4, 0, 0, 0, 8, 0, 0, 3, 6,
+ 0, 0, 8, 0, 0, 0, 1, 0, 0,
+
+ 0, 4, 0, 0, 6, 0, 0, 7, 3,
+ 8, 0, 0, 0, 0, 0, 0, 1, 0,
+ 0, 0, 0, 0, 0, 2, 0, 0, 0,
+
+ 0, 0, 4, 0, 7, 0, 0, 6, 8,
+ 6, 0, 0, 0, 0, 0, 0, 0, 0,
+ 7, 0, 0, 0, 0, 0, 5, 0, 0,
+ ],
+ ["Really Hard™ — not quite",
+ 0, 0, 0, 8, 0, 1, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 4, 3,
+ 5, 0, 0, 0, 0, 0, 0, 0, 0,
+
+ 0, 0, 0, 0, 7, 0, 8, 0, 0,
+ 0, 0, 0, 0, 0, 0, 1, 0, 0,
+ 0, 2, 0, 0, 3, 0, 0, 0, 0,
+
+ 6, 0, 0, 0, 0, 0, 0, 7, 5,
+ 0, 0, 3, 4, 0, 0, 0, 0, 0,
+ 0, 0, 0, 2, 0, 0, 6, 0, 0,
+ ],
+ ["tmp2",
+ 0, 0, 0, 7, 4, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 5, 0, 0, 0,
+ 0, 1, 0, 0, 0, 0, 0, 0, 5,
+
+ 3, 0, 0, 2, 0, 0, 0, 0, 0,
+ 0, 2, 8, 0, 0, 0, 0, 5, 4,
+ 0, 0, 5, 0, 6, 0, 8, 9, 0,
+
+ 4, 3, 0, 9, 0, 7, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 6,
+ 8, 0, 0, 0, 0, 2, 0, 3, 0,
+ ],
+ ["tmp3",
+ 0, 0, 0, 0, 0, 6, 0, 8, 5,
+ 0, 0, 3, 0, 0, 0, 9, 0, 7,
+ 0, 1, 0, 0, 4, 0, 0, 0, 0,
+
+ 1, 8, 0, 9, 0, 0, 0, 0, 0,
+ 0, 0, 7, 0, 0, 0, 3, 0, 0,
+ 0, 4, 0, 0, 0, 0, 0, 0, 0,
+
+ 8, 0, 0, 7, 6, 0, 0, 3, 0,
+ 0, 0, 0, 0, 0, 1, 0, 0, 9,
+ 0, 0, 0, 0, 9, 4, 2, 0, 0,
+ ],
+ ["tmp4",
+ 0, 0, 0, 0, 0, 0, 5, 2, 8,
+ 4, 7, 0, 0, 1, 0, 0, 0, 0,
+ 0, 0, 3, 8, 0, 0, 0, 0, 0,
+
+ 0, 0, 1, 7, 8, 0, 0, 0, 3,
+ 0, 0, 0, 0, 0, 0, 0, 9, 0,
+ 0, 0, 0, 0, 4, 0, 0, 0, 1,
+
+ 0, 0, 0, 9, 5, 8, 7, 0, 0,
+ 5, 0, 0, 0, 0, 3, 0, 0, 0,
+ 0, 2, 0, 0, 0, 0, 6, 0, 0,
+ ],
+ ["tmp5",
+ 0, 0, 0, 0, 0, 0, 4, 0, 3,
+ 0, 0, 0, 6, 0, 0, 0, 0, 0,
+ 0, 0, 0, 8, 0, 0, 0, 0, 0,
+
+ 0, 0, 0, 9, 0, 0, 0, 8, 0,
+ 0, 2, 0, 0, 0, 0, 0, 9, 0,
+ 0, 7, 0, 0, 1, 0, 0, 0, 0,
+
+ 5, 0, 0, 0, 4, 0, 1, 0, 0,
+ 8, 0, 0, 0, 0, 0, 3, 0, 0,
+ 9, 0, 6, 0, 0, 0, 0, 0, 0,
+ ],
+ ["tmp6",
+ 0, 0, 0, 0, 7, 0, 8, 0, 0,
+ 6, 0, 0, 0, 0, 0, 0, 0, 3,
+ 0, 0, 0, 0, 0, 0, 5, 0, 0,
+
+ 5, 0, 0, 3, 0, 0, 1, 0, 0,
+ 9, 0, 0, 6, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 9, 0, 0, 0,
+
+ 0, 4, 7, 0, 0, 0, 0, 9, 0,
+ 0, 8, 0, 0, 1, 0, 0, 0, 0,
+ 0, 0, 0, 5, 0, 0, 0, 0, 0,
+ ],
+ ["tmp7",
+ 0, 8, 0, 0, 0, 0, 5, 0, 0,
+ 9, 0, 0, 3, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0,
+
+ 0, 5, 0, 0, 4, 0, 8, 0, 0,
+ 0, 0, 0, 7, 0, 0, 0, 3, 0,
+ 6, 1, 0, 0, 0, 0, 0, 0, 0,
+
+ 0, 0, 0, 0, 5, 0, 1, 0, 0,
+ 3, 0, 0, 9, 0, 0, 0, 0, 0,
+ 7, 0, 0, 0, 0, 0, 0, 0, 8,
+ ],
+ ["tmp8",
+ 0, 5, 0, 0, 0, 0, 9, 3, 0,
+ 4, 0, 0, 8, 0, 0, 2, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0,
+
+ 0, 2, 0, 0, 0, 3, 0, 0, 0,
+ 0, 0, 0, 0, 5, 0, 0, 7, 0,
+ 9, 0, 0, 0, 0, 0, 0, 0, 4,
+
+ 7, 0, 6, 4, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 3, 0, 0,
+ 0, 0, 0, 7, 0, 0, 0, 0, 0,
+ ],
+ ["tmp9",
+ 0, 0, 0, 0, 0, 0, 0, 8, 3,
+ 0, 9, 0, 1, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0,
+
+ 0, 0, 0, 0, 3, 5, 1, 0, 0,
+ 8, 0, 0, 0, 7, 0, 0, 0, 0,
+ 0, 6, 0, 0, 0, 0, 9, 0, 0,
+
+ 0, 0, 0, 6, 0, 0, 4, 9, 0,
+ 3, 0, 0, 4, 0, 0, 0, 0, 0,
+ 7, 0, 0, 0, 0, 0, 0, 0, 0,
+ ],
+ ["tmp10",
+ 0, 0, 0, 0, 4, 0, 6, 9, 0,
+ 3, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 5, 0, 0,
+
+ 0, 0, 0, 5, 0, 1, 0, 0, 8,
+ 0, 0, 7, 3, 0, 0, 0, 0, 0,
+ 0, 4, 0, 0, 0, 0, 9, 0, 0,
+
+ 1, 0, 0, 0, 0, 0, 0, 0, 3,
+ 0, 9, 0, 0, 0, 0, 0, 7, 0,
+ 0, 0, 0, 8, 0, 0, 0, 0, 0,
+ ],
+];
+
diff --git a/src/lib/helpers.ts b/src/lib/helpers.ts
new file mode 100644
index 0000000..673c8fb
--- /dev/null
+++ b/src/lib/helpers.ts
@@ -0,0 +1,16 @@
+import type { Coord } from "./Sudoku";
+
+export function getNewCoord(direction: string, curCoords: Coord) {
+ let { x, y } = curCoords;
+ if (direction === "up")
+ x === 0 ? x = 8 : x--;
+ else if (direction === "down")
+ x === 8 ? x = 0 : x++;
+ else if (direction === "right")
+ y === 8 ? y = 0 : y++;
+ else if (direction === "left")
+ y === 0 ? y = 8 : y--;
+ else
+ throw new Error("getNewCoord(): bad direction")
+ return { x, y }
+}
diff --git a/src/lib/sudoku/solve.ts b/src/lib/sudoku/solve.ts
new file mode 100644
index 0000000..eedb576
--- /dev/null
+++ b/src/lib/sudoku/solve.ts
@@ -0,0 +1,35 @@
+function solve() {
+ let board = self.readBoard(true);
+ let backtrack = 0;
+ let guesswork = 0;
+ let dcount = 0;
+ let time = Date.now();
+ if (solve()) {
+ stats();
+ self.writeBytes(board);
+ el.classList.add("solved");
+ } else {
+ stats();
+ alert("no solution");
+ }
+ function solve() {
+ let { index, moves, len } = analyze(board);
+ if (index == null) return true;
+ if (len > 1) guesswork++;
+ for (let m = 1; moves; m <<= 1) {
+ if (moves & m) {
+ dcount++;
+ board[index] = m;
+ if (solve()) return true;
+ moves ^= m;
+ }
+ }
+ board[index] = 0;
+ ++backtrack;
+ return false;
+ }
+ function stats() {
+ log(el, `${dcount} digits placed<br>${backtrack} take-backs<br>${guesswork} guesses<br>${Date.now() - time} milliseconds`);
+ }
+}
+
diff --git a/src/lib/sudoku/validation.ts b/src/lib/sudoku/validation.ts
new file mode 100644
index 0000000..4403a20
--- /dev/null
+++ b/src/lib/sudoku/validation.ts
@@ -0,0 +1,57 @@
+import type { Coord, Grid } from "../Sudoku";
+
+export function validate(board: Grid) {
+ const bads = [] as Coord[];
+ for (let i = 0; i < 9; i++) {
+ for (let j = 0; j < 9; j++) {
+ const value = board[i][j];
+ if (value !== '.') {
+ if (!validateRow(board, i, j, value) || !validateColumn(board, i, j, value) || !validateBox(board, i, j, value)) {
+ bads.push({ x: i, y: j })
+ }
+ }
+ }
+ }
+ return bads;
+};
+
+function validateRow(board: Grid, row: number, col: number, value: string) {
+ for (let j = 0; j < 9; j++) {
+ if (j !== col) {
+ if (board[row][j] === value) {
+ return false;
+ }
+ }
+ }
+
+ return true;
+}
+
+function validateColumn(board: Grid, row: number, col: number, value: string) {
+ for (let i = 0; i < 9; i++) {
+ if (i !== row) {
+ if (board[i][col] === value) {
+ return false;
+ }
+ }
+ }
+
+ return true;
+}
+
+function validateBox(board: Grid, row: number, col: number, value: string) {
+ const startRow = row - (row % 3), startCol = col - (col % 3);
+
+ for (let i = startRow; i < startRow + 3; i++) {
+ for (let j = startCol; j < startCol + 3; j++) {
+ if (i !== row && j !== col) {
+ if (board[i][j] === value) {
+ return false;
+ }
+ }
+ }
+ }
+
+ return true;
+}
+
generated by cgit v1.3.1 (git 2.54.0) at 2026-07-23 07:39:35 +0000