// Brute-force Sudoku solver by Josh Jordan (public domain):
// https://tentorcupu.wordpress.com/2013/11/08/just-another-extreme-sudoku-solution/
var coly013= [
0, 0, 0, 0, 9, 0, 0, 5, 0,
0, 1, 0, 0, 0, 0, 0, 3, 0,
0, 0, 2, 3, 0, 0, 7, 0, 0,
0, 0, 4, 5, 0, 0, 0, 7, 0,
8, 0, 0, 0, 0, 0, 2, 0, 0,
0, 0, 0, 0, 0, 6, 4, 0, 0,
0, 9, 0, 0, 1, 0, 0, 0, 0,
0, 8, 0, 0, 6, 0, 0, 0, 0,
0, 0, 5, 4, 0, 0, 0, 0, 7,
];
// https://tentorcupu.wordpress.com/2013/11/08/just-another-extreme-sudoku-solution/
var tarx0134 = [
0, 0, 0, 0, 0, 0, 0, 0, 8,
0, 0, 3, 0, 0, 0, 4, 0, 0,
0, 9, 0, 0, 2, 0, 0, 6, 0,
0, 0, 0, 0, 7, 9, 0, 0, 0,
0, 0, 0, 0, 6, 1, 2, 0, 0,
0, 6, 0, 5, 0, 2, 0, 7, 0,
0, 0, 8, 0, 0, 0, 5, 0, 0,
0, 1, 0, 0, 0, 0, 0, 2, 0,
4, 0, 5, 0, 0, 0, 0, 0, 3,
];
var platinum_blonde = [
0, 0, 0, 0, 0, 0, 0, 1, 2,
0, 0, 0, 0, 0, 0, 0, 0, 3,
0, 0, 2, 3, 0, 0, 4, 0, 0,
0, 0, 1, 8, 0, 0, 0, 0, 5,
0, 6, 0, 0, 7, 0, 8, 0, 0,
0, 0, 0, 0, 0, 9, 0, 0, 0,
0, 0, 8, 5, 0, 0, 0, 0, 0,
9, 0, 0, 0, 4, 0, 5, 0, 0,
4, 7, 0, 0, 0, 6, 0, 0, 0,
];
// "Golden Nugget... accepted by many sources as the world's hardest sudoku
// puzzle" - http://www.sudokusnake.com/goldennugget.php
var golden_nugget = [
0, 0, 0, 0, 0, 0, 0, 3, 9,
0, 0, 0, 0, 1, 0, 0, 0, 5,
0, 0, 3, 0, 0, 5, 8, 0, 0,
0, 0, 8, 0, 0, 9, 0, 0, 6,
0, 7, 0, 0, 2, 0, 0, 0, 0,
1, 0, 0, 4, 0, 0, 0, 0, 0,
0, 0, 9, 0, 0, 8, 0, 5, 0,
0, 2, 0, 0, 0, 0, 6, 0, 0,
4, 0, 0, 7, 0, 0, 0, 0, 0,
];
// Arto Inkala's "Hardest Sudoko" from 2010
// http://www.mirror.co.uk/news/weird-news/worlds-hardest-sudoku-can-you-242294
var inkala2010 = [
0, 0, 5, 3, 0, 0, 0, 0, 0,
8, 0, 0, 0, 0, 0, 0, 2, ,
0, 7, 0, 0, 1, 0, 5, 0, 0,
4, 0, 0, 0, 0, 5, 3, 0, 0,
0, 1, 0, 0, 7, 0, 0, 0, 6,
0, 0, 3, 2, 0, 0, 0, 8, 0,
0, 6, 0, 5, 0, 0, 0, 0, 9,
0, 0, 4, 0, 0, 0, 0, 3, 0,
0, 0, 0, 0, 0, 9, 7, 0, 0,
];
// Peter Norvig's "hardest (for my program) of the million random puzzles"
// http://norvig.com/sudoku.html
var norvig_hard = "000006000059000008200008000045000000003000000006003054000325006000000000000000000".split('').map(function(x) { return +x})
// Peter Norvig's impossible sudoko (has no solutions) from
// http://norvig.com/sudoku.html
var norvig_impossible = [
0, 0, 0, 0, 0, 5, 0, 8, 0,
0, 0, 0, 6, 0, 1, 0, 4, 3,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 5, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 6, 0, 0, 0,
3, 0, 0, 0, 0, 0, 0, 0, 5,
5, 3, 0, 0, 0, 0, 0, 6, 1,
0, 0, 0, 0, 0, 0, 0, 0, 4,
0, 0, 0, 0, 0, 0, 0, 0, 0,
];
var box_grid;
function initBoxGrid() {
box_grid = [];
for (var i = 0; i < 9; i++) {
box_grid[i] = []
}
for (var i = 0; i < 81; i++) {
box_grid[cell_box(i)].push(i);
}
}
function solveable(board) {
return solveable_r(board.slice(), 80);
}
function solveable_r(board, i) {
if (box_grid === undefined) {
initBoxGrid();
}
if (i < 0) {
console.log(board); // show the solution
return board;
}
if (board[i] > 0) {
return solveable_r(board, i-1);
}
for (var j = 1; j < 10; j++) {
board[i] = j;
if(valid(board, i) && solveable_r(board, i-1)) {
return true;
}
board[i] = 0;
}
return false;
}
function valid(board, cell) {
return valid_row(board, cell_row(cell))
&& valid_col(board, cell_col(cell))
&& valid_box(board, cell_box(cell));
}
// Given a cell (0-80), return the number of the row to which it belongs (0-8).
function cell_row(i) {
return Math.floor(i / 9);
}
// Given a cell (0-80), return the number of the column to which it belongs (0-8).
function cell_col(i) {
return i % 9;
}
// Given a cell (0-80), return the number of the box to which it belongs (0-8).
function cell_box(i) {
return 3 * Math.floor(cell_row(i) / 3) + Math.floor(cell_col(i) / 3)
}
function valid_row(board, row) {
return valid_line(board, row, 9, 1);
}
function valid_col(board, col) {
return valid_line(board, col, 1, 9);
}
function valid_line(board, row, a, b) {
var seen = 0;
for (var i = 0; i < 9; i++) {
j = board[row * a + i * b];
if (j == 0) continue;
if (seen & (1 << j)) {
return false;
}
seen = seen | (1 << j);
}
return true;
}
function valid_box(board, b) {
var seen = 0;
for (var i = 0; i < 9; i++) {
j = board[box_grid[b][i]];
if (j == 0) continue;
if (seen & (1 << j)) {
return false;
}
seen = seen | (1 << j);
}
return true;
}
console.log(solveable(coly013));
console.log(solveable(platinum_blonde));
console.log(solveable(tarx0134));
console.log(solveable(golden_nugget));
console.log(solveable(inkala2010));
console.log(solveable(norvig_hard));
console.log(solveable(norvig_impossible));
No comments:
Post a Comment