Skip to content

Instantly share code, notes, and snippets.

@birowo

birowo/index.html

Created July 9, 2018 02:14
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save birowo/1b1de4625ec3dc7b72f550a873e38ba5 to your computer and use it in GitHub Desktop.
Save birowo/1b1de4625ec3dc7b72f550a873e38ba5 to your computer and use it in GitHub Desktop.
Download ZIP
SuSo - the happy sudoku solver — live at https://zenmumbler.net/suso/
Raw
index.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>SuSo</title>
<style>
content {
display: flex;
justify-content: flex-start;
align-items: flex-start;
}
section.grid {
flex: 1;
max-width: 25em;
}
section.stuff {
flex: 1;
}
table {
border-collapse: collapse;
}
table, tr {
padding: 0;
margin: 0;
}
td {
font-size: 18px;
text-align: center;
border: 1px solid #ccc;
width: 2em;
height: 2em;
padding: 0;
margin: 0;
}
td:nth-child(3), td:nth-child(6) {
border-right-color: #888;
}
tr:nth-child(3) td, tr:nth-child(6) td {
border-bottom-color: #888;
}
</style>
</head>
<body>
<content>
<section class="grid">
<table>
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
</table>
</section>
<section class="stuff">
<p>
<label>Select Puzzle
<select>
<option value="template">Empty</option>
<option value="easy">Easy</option>
<option value="hard" selected>Hard</option>
</select>
</label>
</p>
<p>
<button id="basic">Solve Basic</button> <button id="optim">Solve Optimized</button> <span></span>
</p>
</section>
</content>
<script src="suso.js"></script>
<script src="suso2.js"></script>
<script>
// @ts-check
const _ = 0;
const puzzles = {
template: [
_, _, _, _, _, _, _, _, _,
_, _, _, _, _, _, _, _, _,
_, _, _, _, _, _, _, _, _,
_, _, _, _, _, _, _, _, _,
_, _, _, _, _, _, _, _, _,
_, _, _, _, _, _, _, _, _,
_, _, _, _, _, _, _, _, _,
_, _, _, _, _, _, _, _, _,
_, _, _, _, _, _, _, _, _
],
easy: [
_, _, _, 6, _, _, _, 1, _,
_, 6, 9, 1, _, 3, _, _, _,
4, _, _, _, _, _, _, _, _,
5, _, _, 3, _, _, _, _, _,
7, _, 2, _, _, _, 6, _, 9,
_, _, _, _, 8, 9, _, _, 4,
2, 3, _, _, _, _, _, _, _,
_, _, 8, 9, 2, _, _, _, _,
_, _, 5, 4, _, _, _, _, 8
],
hard: [
_, _, 7, 2, _, _, 6, _, _,
_, _, 1, _, 8, _, 5, _, _,
_, _, _, _, 5, 6, _, _, 4,
_, _, _, _, _, _, _, 4, _,
_, 8, _, _, _, _, _, _, 2,
_, _, 4, 3, _, _, _, 9, 8,
_, 1, _, _, _, _, _, _, _,
6, _, 9, 4, _, _, _, _, _,
5, _, _, _, 2, 3, _, _, _
]
};
const { solve, getCell } = suso;
const { solve: solve2 } = suso2;
/**
* @param {number[]} data
*/
function print(data) {
for (let y = 0; y < 9; ++y) {
const tr = document.querySelectorAll("tr")[y];
for (let x = 0; x < 9; ++x) {
const td = tr.querySelectorAll("td")[x];
td.textContent = getCell(data, x, y) || " ";
}
}
}
let puzzleToSolve = puzzles.hard;
document.querySelector("select").onchange = (evt) => {
puzzleToSolve = puzzles[evt.target.value];
print(puzzleToSolve);
};
print(puzzleToSolve);
function runSolver(solver) {
const puzzle = new Uint8Array(puzzleToSolve);
const t0 = performance.now();
const solved = solver(puzzle);
const t1 = performance.now();
document.querySelector("span").textContent = `Took ${(t1 - t0).toFixed(0)}ms`;
print(solved);
}
document.querySelector("button#basic").onclick = (evt) => {
runSolver(solve);
};
document.querySelector("button#optim").onclick = (evt) => {
runSolver(solve2);
};
</script>
</body>
</html>
Raw
suso.js
// @ts-check
(function(exports){
/**
* @param {number[]} data
* @param {number} x
* @param {number} y
*/
function getCell(data, x, y) {
return data[(y * 9) + x];
}
/**
* @param {number[]} data
* @param {number} x
* @param {number} y
* @param {number} v
*/
function canUse(data, x, y, v) {
// check the row for this value
for (let c = 0; c < 9; ++c) {
if (c !== x) {
if (getCell(data, c, y) === v) {
return false;
}
}
}
// check the column for this value
for (let r = 0; r < 9; ++r) {
if (r !== y) {
if (getCell(data, x, r) === v) {
return false;
}
}
}
// check the 3x3 block for this value
// excluding the values we already checked (x or y equal to source cell)
const bxs = x - (x % 3), bxe = bxs + 3;
const bys = y - (y % 3), bye = bys + 3;
for (let r = bys; r < bye; ++r) {
for (let c = bxs; c < bxe; ++c) {
if (c === x || r === y) {
continue;
}
if (getCell(data, c, r) === v) {
return false;
}
}
}
return true;
}
/**
* @param {number[]} puzzle
*/
function solve(puzzle) {
const solved = puzzle.slice(0);
let x = 0;
let y = 0;
const preset = (x, y) => {
return getCell(puzzle, x, y) !== 0;
};
const forward = () => {
++x;
if (x === 9) {
x = 0;
++y;
}
};
const back = () => {
if (x === 0 && y === 0) {
throw new Error("Impossible");
}
--x;
if (x === -1) {
x = 8;
--y;
}
if (preset(x, y)) {
back();
}
};
const inc = () => ++(solved[(y * 9) + x]);
const reset = () => solved[(y * 9) + x] = 0;
while (y < 9) {
if (preset(x, y)) {
forward();
}
else {
const v = inc();
if (v === 10) {
reset();
back();
}
else {
if (canUse(solved, x, y, v)) {
forward();
}
}
}
}
return solved;
}
exports.suso = {
getCell,
solve
};
}(window));
Raw
suso2.js
// @ts-check
(function(exports){
/**
* @param {number[]} data
* @param {number} x
* @param {number} y
*/
function getCell(data, x, y) {
return data[(y * 9) + x];
}
/**
* @param {number[]} data
* @param {number} sourceIndex
*/
function available(data, sourceIndex) {
let used = 0;
let y = (sourceIndex / 9) | 0;
let x = sourceIndex - (y * 9);
let index;
// check the row for this value
index = y * 9;
for (let c = 0; c < 9; ++c) {
if (c !== x) {
const v = data[index];
used |= 1 << v;
}
index += 1;
}
// check the column for this value
index = x;
for (let r = 0; r < 9; ++r) {
if (r !== y) {
const v = data[index];
used |= 1 << v;
}
index += 9;
}
// check the 3x3 block for this value
// excluding the values we already checked (x or y equal to source cell)
const bxs = x - (x % 3), bxe = bxs + 3;
const bys = y - (y % 3), bye = bys + 3;
index = (bys * 9) + bxs;
for (let r = bys; r < bye; ++r) {
for (let c = bxs; c < bxe; ++c) {
if (c !== x && r !== y) {
const v = data[index];
used |= 1 << v;
}
index += 1;
}
index += 6;
}
// at this point bits 0-9 can be set, but bit 0 means nothing
// shift back to 0-8, negate and mask to lowest 9 bits
return (~(used >> 1)) & 511;
}
/**
* @param {number[]} puzzle
*/
function solve(puzzle) {
const solved = puzzle.slice(0);
const cellAvail = new Uint32Array(81);
let index = -1;
const forward = () => {
++index;
if (index === 81) {
return;
}
if (puzzle[index] !== 0) {
forward();
}
else {
cellAvail[index] = available(solved, index);
}
};
const back = () => {
if (index === 0) {
throw new Error("Impossible");
}
--index;
if (puzzle[index] !== 0) {
back();
}
};
forward();
while (index < 81) {
// the following will reverse the algo, which for this particular
// hard puzzle will be slower
// const next = 32 - Math.clz32(cellAvail[index]);
// find the lowest bit set in avail, next is the bit index
// and thus value to put in the puzzle, mask is the corresponding
// bit mask
let mask = 1, next = 1;
const avail = cellAvail[index];
while ((mask & avail) === 0 && next < 10) {
mask <<= 1;
++next;
}
if (next !== 10) { // use !== 0 for the reversed search
cellAvail[index] ^= mask; // clear the bit in avail
solved[index] = next;
forward();
}
else {
solved[index] = 0;
back();
}
}
return solved;
}
exports.suso2 = {
getCell,
solve
};
}(window));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment