aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/App.svelte268
-rw-r--r--src/app.css36
-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
9 files changed, 977 insertions, 85 deletions
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 @@
<script lang="ts">
+ import { getNewCoord } from "./lib/helpers";
+
import { readGridFromFile, save } from "./lib/Saving";
- import { validate, type Coord } from "./lib/Sudoku";
+ import { solve, validate, type Coord } from "./lib/Sudoku";
let selTile: HTMLDivElement | EventTarget;
+ let isImmu = false;
+ let selTileCoords: Coord = { x: -1, y: -1 };
let fileInput: HTMLInputElement;
const getSelTile = () => selTile as HTMLDivElement;
- const getCoord = (): Coord => ({
- x: parseInt(getSelTile().dataset.i),
- y: parseInt(getSelTile().dataset.j),
- });
let grid = [] as string[][]; //new Array(9).fill(new Array(9).fill("."));
+ let solvedGrid = [] as string[][]; //new Array(9).fill(new Array(9).fill("."));
let immutableTiles = [] as Coord[]; //new Array(9).fill(new Array(9).fill("."));
const tiles = [] as HTMLDivElement[][]; //new Array(9).fill(new Array(9).fill("."));
+ const doneNums = [] as HTMLDivElement[]; //new Array(9).fill(new Array(9).fill("."));
+ const doneNumsCount = [] as number[]; //new Array(9).fill(new Array(9).fill("."));
+ let hintTime = false;
+ let eraseTime = false;
+
for (let i = 0; i < 9; i++) {
grid.push([]);
tiles.push([]);
+ doneNumsCount.push(0);
for (let j = 0; j < 9; j++) {
grid[i].push(".");
- tiles[i].push(null);
+ // tiles[i].push(null);
}
}
function keyDownHandler(e: KeyboardEvent) {
const foundImmu = immutableTiles.find(
- (el) => el.x === getCoord().x && el.y === getCoord().y
+ (el) => el.x === selTileCoords.x && el.y === selTileCoords.y
);
- console.log(immutableTiles);
- console.log(foundImmu);
- if (foundImmu) return;
+ if (foundImmu) isImmu = true;
+
+ let key = e.key;
+ key = key === "j" ? "ArrowDown" : key;
+ key = key === "k" ? "ArrowUp" : key;
+ key = key === "h" ? "ArrowLeft" : key;
+ key = key === "l" ? "ArrowRight" : key;
+ const t = key.split("Arrow")[1]?.toLowerCase();
+ if (["right", "left", "up", "down"].includes(t) && selTile) {
+ setSelTile(null, getNewCoord(t, selTileCoords));
+ }
+ if (isImmu) return;
- if (e.key === "Backspace") {
- setSelTile(".");
+ let num: string | number = parseInt(e.key);
+ if (e.key === "Backspace" || e.key === "d" || eraseTime) {
+ setGrid(".", selTileCoords);
+ num = ".";
}
- const num = parseInt(e.key);
- if (Number.isNaN(num) || selTile == null || num === 0) return;
- setSelTile(num);
+ if (Number.isNaN(num) || selTile == null || num === 0 || eraseTime) return;
+ if (hintTime) {
+ setHint(num);
+ return;
+ }
+
+ setGrid(num.toString(), selTileCoords);
for (const tile of tiles.flat()) {
tile.classList.remove("err");
tile.classList.remove("good");
@@ -45,16 +67,29 @@
tiles[bad.x][bad.y].classList.add("err");
}
}
- // function showTile(val: string) {
- // return val === "." ? "" : val;
- // }
- function setSelTile(val: string | number) {
- grid[getCoord().x][getCoord().y] = val.toString();
- // getSelTile().innerText = val === "." ? "" : val.toString();
+ function setSelTile(
+ nst: HTMLDivElement | EventTarget | null,
+ x: number | Coord,
+ y?: number
+ ) {
+ if (selTile) getSelTile().classList.remove("selected");
+ if (typeof x === "object") {
+ y = x.y;
+ x = x.x;
+ }
+ if (y == undefined) throw new Error("y is undefinedly!");
+
+ if (nst) selTile = nst;
+ else selTile = tiles[x][y];
+ selTileCoords = { x, y };
+ if (eraseTime) setGrid(".", selTileCoords);
+ getSelTile().classList.add("selected");
}
async function load() {
- const maybeGrid = await readGridFromFile(fileInput.files[0]);
+ const fs = fileInput.files;
+ const maybeGrid = await readGridFromFile(fs ? fs[0] : undefined);
+ fileInput.value = "";
if (!maybeGrid) {
alert("Error while loading file");
return;
@@ -66,14 +101,63 @@
tiles[i][j].classList.add("const");
}
}
+ if (validate(maybeGrid).length > 0) {
+ alert("Can not load grid, not valid");
+ return;
+ }
grid = maybeGrid;
- fileInput.value = null;
+ solvedGrid = solve(grid);
+ }
+
+ function setGrid(val: string, ax: number | Coord, ay?: number) {
+ let x = -1,
+ y = -1;
+ if (typeof ax === "object") [x, y] = [ax.x, ax.y];
+ else if (ay != null) [x, y] = [ax, ay];
+ else throw new Error("setGrid() didnt get any good arguments");
+
+ const oldNum = grid[x][y];
+ grid[x][y] = val;
+
+ if (oldNum !== ".") doneNumsCount[parseInt(oldNum) - 1]--;
+ if (val !== ".") doneNumsCount[parseInt(val) - 1]++;
+ // else getSelTile().classList.remove("wrong", "good", "err");
+
+ if (solvedGrid.length > 0) {
+ if (grid[x][y] !== solvedGrid[x][y]) getSelTile().classList.add("wrong");
+ else getSelTile().classList.add("good");
+ }
+ // if (typeof x === "object") grid[x.x][x.y] = val;
+ // else if (y != null) grid[x][y] = val;
+ // else throw new Error("setGrid() didnt get any good arguments");
+ }
+ function setHint(num: number | string) {
+ const t = getSelTile();
+ // debugger;
+ const c = t.querySelector(`.hint-${num}`);
+ if (!c) return;
+ const cih = c.innerHTML;
+ if (cih === "") c.innerHTML = num.toString();
+ else c.innerHTML = "";
+ }
+
+ function solveGrid() {
+ if (validate(grid).length > 0) {
+ alert("Grid is not valid, can not solve");
+ return;
+ }
+ grid = solve(grid);
+ for (let i = 0; i < doneNumsCount.length; i++) doneNumsCount[i] = 9;
}
</script>
<!-- <svelte:body on:keydown|preventDefault|stopPropagation={keyDownHandler} /> -->
<svelte:body on:keydown={keyDownHandler} />
<main>
+ <div class="left">
+ <input type="file" on:change={load} bind:this={fileInput} />
+ <button on:click={() => save(grid)}>Save</button>
+ </div>
<div class="grid">
{#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}
+ <span class="hint hint-1" />
+ <span class="hint hint-2" />
+ <span class="hint hint-3" />
+ <span class="hint hint-4" />
+ <span class="hint hint-5" />
+ <span class="hint hint-6" />
+ <span class="hint hint-7" />
+ <span class="hint hint-8" />
+ <span class="hint hint-9" />
</div>
{/each}
{/each}
</div>
- <button on:click={() => save(grid)}>Save</button>
- <input type="file" on:change={load} bind:this={fileInput} />
+ <div class="right" class:err={false}>
+ <button class="btn-solve" on:click={solveGrid}>Solve</button>
+ <div>
+ <label>
+ Hint:
+ <input type="checkbox" bind:checked={hintTime} />
+ </label>
+ <label>
+ Erase:
+ <input type="checkbox" bind:checked={eraseTime} />
+ </label>
+ <div class="small-grid">
+ {#each { length: 9 } as _, i}
+ <div bind:this={doneNums[i]} class:done={doneNumsCount[i] === 9}>
+ {i + 1}
+ </div>
+ {/each}
+ </div>
+ </div>
+ </div>
</main>
<style>
+ main {
+ display: flex;
+ flex-direction: row;
+ flex-wrap: wrap;
+ }
+ @media screen and (max-width: 1144px) {
+ main {
+ flex-direction: column;
+ }
+ .left {
+ min-height: 10rem;
+ align-items: center !important;
+ }
+ .right {
+ padding-top: 2rem;
+ }
+ }
+ .left {
+ display: flex;
+ justify-content: center;
+ align-items: flex-start;
+ gap: 2rem;
+ flex-direction: column;
+ padding-right: 3rem;
+ }
.grid {
display: grid;
grid-template-columns: repeat(9, 1fr);
@@ -111,6 +247,48 @@
gap: 0;
box-sizing: border-box;
user-select: none;
+ position: relative;
+ }
+ .hint {
+ font-size: 0.6rem;
+ position: absolute;
+ }
+ .right {
+ display: flex;
+ flex-direction: column;
+ justify-content: center;
+ align-items: center;
+ padding-left: 3rem;
+ gap: 2rem;
+ }
+ .right > div {
+ display: flex;
+ flex-direction: column;
+ }
+ .btn-solve {
+ background-color: #ff000000;
+ border: 3px solid white;
+ color: white;
+ font-size: 1.5rem;
+ }
+ .small-grid {
+ display: grid;
+ grid-template-columns: repeat(3, 1fr);
+ gap: 1rem;
+ margin-top: 2rem;
+ }
+ .small-grid > div {
+ display: flex;
+ justify-content: center;
+ align-items: center;
+ font-size: 2rem;
+ width: 2rem;
+ line-height: 2rem;
+ padding: 0.8rem;
+ background-color: #aaaaaa;
+ }
+ .small-grid > div.done {
+ background-color: #00aaaa;
}
.tile:nth-child(odd) {
background-color: lightgrey;
@@ -124,10 +302,44 @@
.br {
border-right: 3px solid black;
}
- :global(.err) {
- background-color: rgba(150, 0, 0, 0.6) !important;
+ .err:nth-child(n) {
+ background-color: rgba(150, 0, 0, 0.6);
}
:global(.const) {
color: rebeccapurple;
}
+ :global(.wrong) {
+ color: #dd0000;
+ }
+ :global(.good) {
+ color: #00dd00;
+ }
+ @keyframes blink-animation {
+ 0% {
+ background-color: revert;
+ }
+ 50% {
+ background-color: pink;
+ }
+ 100% {
+ background-color: revert;
+ }
+ }
+ :global(.selected) {
+ animation: blink-animation 5s ease-in-out infinite;
+ }
+ @media print {
+ .left,
+ .right {
+ display: none;
+ }
+ .tile {
+ width: 5rem;
+ /* border: 1px solid black; */
+ print-color-adjust: exact;
+ }
+ :global(.selected) {
+ animation: none;
+ }
+ }
</style>
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<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 06:22:46 +0000