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, ], ];