Skip to content

Instantly share code, notes, and snippets.

@zenmumbler

zenmumbler/suso.c

Created July 26, 2020 12:42
Show Gist options
  • Save zenmumbler/ba3505cb87471a8d64e5abe53c2b215e to your computer and use it in GitHub Desktop.
Save zenmumbler/ba3505cb87471a8d64e5abe53c2b215e to your computer and use it in GitHub Desktop.
Download ZIP
SuSo - the happy sudoku solver — live at https://zenmumbler.net/suso/
Raw
suso.c
/**
* SuSo - C version - (c) 2018 by @zenmumbler
* The C version of my implementation of a brute-force Sudoku solver.
* For a web version see https://zenmumbler.net/suso/
* Compiled with -O3 this takes about 2.3ms to solve on my 2013 iMac
* I found the puzzle online by looking for "very hard sudoku"
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>
const uint8_t _ = 0;
const uint8_t puzzle[] = {
_, _, 7, 2, _, _, 6, _, _,
_, _, 1, _, 8, _, 5, _, _,
_, _, _, _, 5, 6, _, _, 4,
_, _, _, _, _, _, _, 4, _,
_, 8, _, _, _, _, _, _, 2,
_, _, 4, 3, _, _, _, 9, 8,
_, 1, _, _, _, _, _, _, _,
6, _, 9, 4, _, _, _, _, _,
5, _, _, _, 2, 3, _, _, _
};
uint8_t getCell(const uint8_t* data, int x, int y) {
return data[(y * 9) + x];
}
void print(const uint8_t* data) {
for (int y = 0; y < 9; ++y) {
printf("\n | | \n");
for (int x = 0; x < 9; ++x) {
printf(" %c ", '0' + getCell(data, x, y));
if (x == 2 || x == 5) {
printf("|");
}
}
printf("\n | | ");
if (y == 2 || y == 5) {
printf("\n-----------------------------");
}
}
}
int available(const uint8_t *data, int sourceIndex) {
int used = 0;
int y = (sourceIndex / 9);
int x = sourceIndex - (y * 9);
int index;
index = y * 9;
for (int c = 0; c < 9; ++c) {
if (c != x) {
int v = data[index];
used |= 1 << v;
}
index += 1;
}
index = x;
for (int r = 0; r < 9; ++r) {
if (r != y) {
int v = data[index];
used |= 1 << v;
}
index += 9;
}
const int bxs = x - (x % 3), bxe = bxs + 3;
const int bys = y - (y % 3), bye = bys + 3;
index = (bys * 9) + bxs;
for (int r = bys; r < bye; ++r) {
for (int c = bxs; c < bxe; ++c) {
if (c != x && r != y) {
int v = data[index];
used |= 1 << v;
}
index += 1;
}
index += 6;
}
return (~(used >> 1)) & 511;
}
typedef struct {
const uint8_t* puzzle;
uint8_t* solved;
uint16_t* cellAvail;
int index;
} SolveState;
void forward(SolveState *state) {
++state->index;
if (state->index == 81) {
return;
}
if (state->puzzle[state->index] != 0) {
forward(state);
}
else {
state->cellAvail[state->index] = available(state->solved, state->index);
}
}
void back(SolveState *state) {
if (state->index == 0) {
exit(1);
}
--state->index;
if (state->puzzle[state->index] != 0) {
back(state);
}
}
uint8_t* solve(const uint8_t* puzzle) {
SolveState state = {
puzzle,
malloc(81), // solved
malloc(2 * 81), // cellAvail
-1 // index
};
memcpy(state.solved, state.puzzle, 81);
forward(&state);
while (state.index < 81) {
int avail = state.cellAvail[state.index];
if (avail != 0) {
int next = __builtin_ctz(avail); // count trailing zeroes intrinsic
int mask = 1 << next;
state.cellAvail[state.index] ^= mask;
state.solved[state.index] = next + 1;
forward(&state);
}
else {
state.solved[state.index] = 0;
back(&state);
}
}
free(state.cellAvail);
return state.solved;
}
int main(int argc, char *argv[]) {
clock_t t0 = clock();
uint8_t *solved = solve(puzzle);
clock_t t1 = clock();
print(solved);
free(solved);
double duration = 1000.0 * (t1 - t0) / CLOCKS_PER_SEC;
printf("\nTook: %.2f ms\n", duration);
}
Raw
suso.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