Skip to content

Instantly share code, notes, and snippets.

@bellbind
Last active August 29, 2015 14:21
Show Gist options
  • Save bellbind/2415a53ff67b28233d94 to your computer and use it in GitHub Desktop.
Save bellbind/2415a53ff67b28233d94 to your computer and use it in GitHub Desktop.
[es6][javascript] 10 lines Sudoku Solver by ES6 generator
"use strict"; // enable "block scope" `const` on iojs
// usual backtrack style sudoku solver
var sudoku = function* (board) {
// used number data in each row/column/block as bitfield
const masks = [0, 1<<0, 1<<1, 1<<2, 1<<3, 1<<4, 1<<5, 1<<6, 1<<7, 1<<8];
const rows = [0, 0, 0, 0, 0, 0, 0, 0, 0];
const cols = [0, 0, 0, 0, 0, 0, 0, 0, 0];
const blks = [0, 0, 0, 0, 0, 0, 0, 0, 0];
// row/column/block index from board index
const row = function (i) {return 0|(i / 9);};
const col = function (i) {return i % 9;};
const blk = function (i) {return (0|i / 27) * 3 + (0|i % 9 / 3);};
// collect used number data from the initial board
for (var i = 0; i < 81; i++) {
const mask = masks[board[i]];
rows[row(i)] |= mask, cols[col(i)] |= mask, blks[blk(i)] |= mask;
}
// backtrack solver
var solve = function* solve(i) {
if (i === 81) return yield board;
if (board[i] !== 0) return yield* solve(i + 1);
const r = row(i), c = col(i), b = blk(i);
const used = rows[r] | cols[c] | blks[b];
for (var v = 1; v <= 9; v++) {
const mask = masks[v];
if (used & mask) continue;
board[i] = v;
rows[r] |= mask, cols[c] |= mask, blks[b] |= mask;
yield* solve(i + 1);
rows[r] &= ~mask, cols[c] &= ~mask, blks[b] &= ~mask;
board[i] = 0;
}
};
// run solver
yield* solve(0);
};
var format = function (board) {
var split = function (a, n) {
var r = [];
for (var i = 0; i < a.length; i += n) r.push(a.slice(i, i + n));
return r;
};
var lines = split(board, 9).map(function (line) {
return split(line, 3).map(function (c3) {
return c3.join("");
}).join("|");
});
return split(lines, 3).map(function (l3) {
return l3.join("\n");
}).join("\n---+---+---\n");
};
// example case from http://rosettacode.org/wiki/Sudoku
var problem = [
8, 5, 0, 0, 0, 2, 4, 0, 0,
7, 2, 0, 0, 0, 0, 0, 0, 9,
0, 0, 4, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 7, 0, 0, 2,
3, 0, 5, 0, 0, 0, 9, 0, 0,
0, 4, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 8, 0, 0, 7, 0,
0, 1, 7, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 3, 6, 0, 4, 0
];
for (var solution of sudoku(problem, 0)) {
console.log(format(solution));
}
// 11 lines Sudoku Solver
// structure of board b: 81-element flat-array of 1-9 or 0 as blank cell
var solve = function solve(b, i) {
if (i === 81) return b; // <= solution
if (b[i] !== 0) return solve(b, i + 1);
var used = b.filter(function (_, j) {
return (i % 9) === (j % 9) || (0|i / 9) === (0|j / 9) ||
(0|i / 27) === (0|j / 27) && (0|i % 9 / 3) === (0|j % 9 / 3);
});
for (var v = 1; v <= 9; v++) if (used.indexOf(v) === -1) {
var r = solve(b.slice(0, i).concat([v]).concat(b.slice(i + 1)), i + 1);
if (r) return r;
}
};
// for output board
var format = function (board) {
var split = function (a, n) {
var r = [];
for (var i = 0; i < a.length; i += n) r.push(a.slice(i, i + n));
return r;
};
var lines = split(board, 9).map(function (line) {
return split(line, 3).map(function (c3) {
return c3.join("");
}).join("|");
});
return split(lines, 3).map(function (l3) {
return l3.join("\n");
}).join("\n---+---+---\n");
};
// example case from http://rosettacode.org/wiki/Sudoku
var problem = [
8, 5, 0, 0, 0, 2, 4, 0, 0,
7, 2, 0, 0, 0, 0, 0, 0, 9,
0, 0, 4, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 7, 0, 0, 2,
3, 0, 5, 0, 0, 0, 9, 0, 0,
0, 4, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 8, 0, 0, 7, 0,
0, 1, 7, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 3, 6, 0, 4, 0
];
//console.log(format(problem);
var solution = solve(problem, 0);
console.log(format(solution));
// 11 lines Sudoku Solver
// structure of board b: 81-element flat-array of 1-9 or 0 as blank cell
var solve = function solve(b, i) {
if (i === 81) return [b]; // <= solution
if (b[i] !== 0) return solve(b, i + 1);
var used = b.filter(function (_, j) {
return (i % 9) === (j % 9) || (0|i / 9) === (0|j / 9) ||
(0|i / 27) === (0|j / 27) && (0|i % 9 / 3) === (0|j % 9 / 3);
});
var before = b.slice(0, i), after = b.slice(i + 1), r = [];
for (var v = 1; v <= 9; v++) if (used.indexOf(v) === -1)
r = r.concat(solve(before.concat([v]).concat(after), i + 1));
return r;
};
// for output board
var format = function (board) {
var split = function (a, n) {
var r = [];
for (var i = 0; i < a.length; i += n) r.push(a.slice(i, i + n));
return r;
};
var lines = split(board, 9).map(function (line) {
return split(line, 3).map(function (c3) {
return c3.join("");
}).join("|");
});
return split(lines, 3).map(function (l3) {
return l3.join("\n");
}).join("\n---+---+---\n");
};
// example case from http://rosettacode.org/wiki/Sudoku
var problem = [
8, 5, 0, 0, 0, 2, 4, 0, 0,
7, 2, 0, 0, 0, 0, 0, 0, 9,
0, 0, 4, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 7, 0, 0, 2,
3, 0, 5, 0, 0, 0, 9, 0, 0,
0, 4, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 8, 0, 0, 7, 0,
0, 1, 7, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 3, 6, 0, 4, 0
];
//console.log(format(problem);
var solutions = solve(problem, 0);
solutions.forEach(function (solution) {
console.log(format(solution));
});
// sudoku solver in C11: clang -Wall -Wextra -O3 -std=c11 sudoku.c -o sudoku
#include <stdio.h>
// helpers for board data
static const unsigned MASKS[] = {
0, 1 << 0, 1 << 1, 1 << 2, 1 << 3, 1 << 4, 1 << 5, 1 << 6, 1 << 7, 1 << 8};
static inline unsigned row(unsigned i) {return i / 9;}
static inline unsigned col(unsigned i) {return i % 9;}
static inline unsigned blk(unsigned i) {return i / 27 * 3 + i % 9 / 3;}
static void output(unsigned board[])
{
for (unsigned y = 0; y < 9; y++) {
for (unsigned x = 0; x < 9; x++) {
putchar(board[y * 9 + x] > 0 ? board[y * 9 + x] + '0' : '.');
if (x % 3 == 2) putchar(x == 8 ? '\n' : '|');
}
if (y % 3 == 2) puts(y == 8 ? "" : "---+---+---");
}
}
// sudoku solver
typedef struct {
unsigned board[81];
unsigned rows[9], cols[9], blks[9];
} sudoku_t;
static void sudoku_init(sudoku_t* s, unsigned board[])
{
for (unsigned i = 0; i < 81; i++) {
const unsigned mask = MASKS[board[i]];
s->rows[row(i)] |= mask, s->cols[col(i)] |= mask, s->blks[blk(i)] |= mask;
s->board[i] = board[i];
}
}
static void sudoku_solve(sudoku_t* s, unsigned i)
{
if (i == 81) {
output(s->board);
} else if (s->board[i] != 0) {
sudoku_solve(s, i + 1);
} else {
const unsigned r = row(i), c = col(i), b = blk(i);
const unsigned used = s->rows[r] | s->cols[c] | s->blks[b];
for (unsigned v = 1; v <= 9; v++) {
const unsigned mask = MASKS[v];
if (used & mask) continue;
s->board[i] = v;
s->rows[r] |= mask, s->cols[c] |= mask, s->blks[b] |= mask;
sudoku_solve(s, i + 1);
s->rows[r] &= ~mask, s->cols[c] &= ~mask, s->blks[b] &= ~mask;
s->board[i] = 0;
}
}
}
void sudoku(unsigned board[])
{
sudoku_t s = {.board = {0}, .rows = {0}, .cols = {0}, .blks = {0}};
sudoku_init(&s, board);
sudoku_solve(&s, 0);
}
// example problem from http://rosettacode.org/wiki/Sudoku
static unsigned problem[] = {
8, 5, 0, 0, 0, 2, 4, 0, 0,
7, 2, 0, 0, 0, 0, 0, 0, 9,
0, 0, 4, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 7, 0, 0, 2,
3, 0, 5, 0, 0, 0, 9, 0, 0,
0, 4, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 8, 0, 0, 7, 0,
0, 1, 7, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 3, 6, 0, 4, 0
};
int main(int argc, char* argv[])
{
if (argc <= 1) {
puts("[problem]");
output(problem);
puts("[solution]");
sudoku(problem);
} else {
for (int i = 1; i < argc; i++) {
char ch = -1;
for (int c = 0; c < 81; c++) {
if (ch == '\0') {
problem[c] = 0;
} else {
ch = argv[i][c];
problem[c] = '0' <= ch && ch <= '9' ? ch - '0' : 0;
}
}
puts("[problem]");
output(problem);
puts("[solution]");
sudoku(problem);
}
}
return 0;
}
// 10 lines Sudoku Solver as ES6 generator
// structure of board b: 81-element flat-array of 1-9 or 0 as blank cell
var solve = function* solve(b, i) {
if (i === 81) return yield b; // <= solution
if (b[i] !== 0) return yield* solve(b, i + 1);
var used = b.filter(function (_, j) {
return (i % 9) === (j % 9) || (0|i / 9) === (0|j / 9) ||
(0|i / 27) === (0|j / 27) && (0|i % 9 / 3) === (0|j % 9 / 3);
});
for (var v = 1; v <= 9; v++) if (used.indexOf(v) === -1)
yield* solve(b.slice(0, i).concat([v]).concat(b.slice(i + 1)), i + 1);
};
// for output board
var format = function (board) {
var split = function (a, n) {
var r = [];
for (var i = 0; i < a.length; i += n) r.push(a.slice(i, i + n));
return r;
};
var lines = split(board, 9).map(function (line) {
return split(line, 3).map(function (c3) {
return c3.join("");
}).join("|");
});
return split(lines, 3).map(function (l3) {
return l3.join("\n");
}).join("\n---+---+---\n");
};
// example case from http://rosettacode.org/wiki/Sudoku
var problem = [
8, 5, 0, 0, 0, 2, 4, 0, 0,
7, 2, 0, 0, 0, 0, 0, 0, 9,
0, 0, 4, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 7, 0, 0, 2,
3, 0, 5, 0, 0, 0, 9, 0, 0,
0, 4, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 8, 0, 0, 7, 0,
0, 1, 7, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 3, 6, 0, 4, 0
];
//console.log(format(problem);
for (var solution of solve(problem, 0)) {
console.log(format(solution));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment