From 44ff6231441024d16fddc2b7cb648539522b04cb Mon Sep 17 00:00:00 2001
From: Maksymilian Jopek <maks@jopek.eu>
Date: Mon, 19 Dec 2022 21:04:23 +0100
Subject: v1.0.0 Added everything that's in the spec

---
 src/lib/sudoku/solve.ts      | 35 +++++++++++++++++++++++++++
 src/lib/sudoku/validation.ts | 57 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 92 insertions(+)
 create mode 100644 src/lib/sudoku/solve.ts
 create mode 100644 src/lib/sudoku/validation.ts

(limited to 'src/lib/sudoku')

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;
+}
+
-- 
cgit v1.3.1