From 44ff6231441024d16fddc2b7cb648539522b04cb Mon Sep 17 00:00:00 2001 From: Maksymilian Jopek Date: Mon, 19 Dec 2022 21:04:23 +0100 Subject: v1.0.0 Added everything that's in the spec --- package.json | 1 + pnpm-lock.yaml | 6 + src/App.svelte | 268 ++++++++++++++++++--- src/app.css | 36 +++ src/lib/Saving.ts | 11 +- src/lib/Sudoku.ts | 80 +++---- src/lib/bestes.html | 4 + src/lib/bestest.js | 555 +++++++++++++++++++++++++++++++++++++++++++ src/lib/helpers.ts | 16 ++ src/lib/sudoku/solve.ts | 35 +++ src/lib/sudoku/validation.ts | 57 +++++ tsconfig.json | 22 +- vite.config.ts | 11 +- 13 files changed, 1014 insertions(+), 88 deletions(-) create mode 100644 src/lib/bestes.html create mode 100644 src/lib/bestest.js create mode 100644 src/lib/helpers.ts create mode 100644 src/lib/sudoku/solve.ts create mode 100644 src/lib/sudoku/validation.ts diff --git a/package.json b/package.json index ffd44de..a27e44d 100644 --- a/package.json +++ b/package.json @@ -20,6 +20,7 @@ "vite": "^3.2.3" }, "dependencies": { + "sudoku-solver-js": "^0.1.4", "sudoku-umd": "^1.0.1" } } \ No newline at end of file diff --git a/pnpm-lock.yaml b/pnpm-lock.yaml index 413d476..074aca5 100644 --- a/pnpm-lock.yaml +++ b/pnpm-lock.yaml @@ -3,6 +3,7 @@ lockfileVersion: 5.4 specifiers: '@sveltejs/vite-plugin-svelte': ^1.1.0 '@tsconfig/svelte': ^3.0.0 + sudoku-solver-js: ^0.1.4 sudoku-umd: ^1.0.1 svelte: ^3.52.0 svelte-check: ^2.9.2 @@ -12,6 +13,7 @@ specifiers: vite: ^3.2.3 dependencies: + sudoku-solver-js: 0.1.4 sudoku-umd: 1.0.1 devDependencies: @@ -738,6 +740,10 @@ packages: min-indent: 1.0.1 dev: true + /sudoku-solver-js/0.1.4: + resolution: {integrity: sha512-KdxMYfz2M4Y/VNOPHHGuyD40VpYnj89NSonNYzQNDxl6zz9CfGbTI7eVAINEB1mvN+zp5G1+78yHlPmDWZUaCA==} + dev: false + /sudoku-umd/1.0.1: resolution: {integrity: sha512-LnvC4MA54EXRSEiwIs7I+4orht02nFAUgjorPe3vaCZY5I+t13s/xarqu5yoB2z6V3heZ9zV6eaxtSQlGtnQ/g==} dev: false diff --git a/src/App.svelte b/src/App.svelte index 3a1a685..104a981 100644 --- a/src/App.svelte +++ b/src/App.svelte @@ -1,41 +1,63 @@

+ + +

{#each grid as row, i} {#each row as tile, j} @@ -81,22 +165,74 @@ class="tile" class:br={j % 3 === 2 && j !== 8} class:bb={i % 3 === 2 && i !== 8} - on:click|self={(e) => (selTile = e.target)} + on:click|self={(e) => setSelTile(e.target, i, j)} data-i={i} data-j={j} bind:this={tiles[i][j]} on:keypress={null} > {tile === "." ? "" : tile} + + + + + + + + +

{/each} {/each} - - +

+ +

+ + Hint: + + + + Erase: + + +

+ {#each { length: 9 } as _, i} +

+ {i + 1} +

+ {/each} +

diff --git a/src/app.css b/src/app.css index ba0f5e7..515442b 100644 --- a/src/app.css +++ b/src/app.css @@ -9,3 +9,39 @@ body { background-color: darksalmon; } +.hint-1 { + top: 0; + left: 0; +} +.hint-2 { + top: 21.25%; + left: 0; +} +.hint-3 { + top: 42.5%; + left: 0; +} +.hint-4 { + top: 63.75%; + left: 0; +} +.hint-5 { + top: 85%; + left: 0; +} +.hint-6 { + top: 0; + left: 90%; +} +.hint-7 { + top: 25%; + left: 90%; +} +.hint-8 { + top: 50%; + left: 90%; +} +.hint-9 { + top: 75%; + left: 90%; +} 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 { +export function readGridFromFile(f?: File): Promise { 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>; -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>; +export type NGrid = Array>; +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 @@ + + + + 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 = `\ +

+ ${[...Array(81).keys()].map(i => { + let { row, col } = i2rc(i); + return ``; + }).join("")} +

+ ${!controls ? '' : ` + + + + + + + `} +

`; + 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
${backtrack} take-backs
${guesswork} guesses
${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
${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
${backtrack} take-backs
${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
${backtrack} take-backs
${guesswork} guesses
${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; +} + diff --git a/tsconfig.json b/tsconfig.json index c4e1c5f..0c4ac5a 100644 --- a/tsconfig.json +++ b/tsconfig.json @@ -5,6 +5,15 @@ "useDefineForClassFields": true, "module": "ESNext", "resolveJsonModule": true, + "noImplicitAny": true, + "noImplicitThis": true, + "noImplicitReturns": true, + "noUnusedLocals": true, + "noUnusedParameters": true, + "strictNullChecks": true, + "strictFunctionTypes": true, + "strictPropertyInitialization": true, + "alwaysStrict": true, /** * Typecheck JS in `.svelte` and `.js` files by default. * Disable checkJs if you'd like to use dynamic types in JS. @@ -15,6 +24,15 @@ "checkJs": true, "isolatedModules": true }, - "include": ["src/**/*.d.ts", "src/**/*.ts", "src/**/*.js", "src/**/*.svelte"], - "references": [{ "path": "./tsconfig.node.json" }] + "include": [ + "src/**/*.d.ts", + "src/**/*.ts", + "src/**/*.js", + "src/**/*.svelte" + ], + "references": [ + { + "path": "./tsconfig.node.json" + } + ] } diff --git a/vite.config.ts b/vite.config.ts index 401b4d4..d421768 100644 --- a/vite.config.ts +++ b/vite.config.ts @@ -3,5 +3,14 @@ import { svelte } from '@sveltejs/vite-plugin-svelte' // https://vitejs.dev/config/ export default defineConfig({ - plugins: [svelte()] + plugins: [svelte({ + onwarn: (warning, handler) => { + const { code } = warning; + if (code === "css-unused-selector") + return; + + handler(warning); + }, + } + )] }) -- cgit v1.3.1