Skip to content

Instantly share code, notes, and snippets.

@potix2
Created September 17, 2011 12:00
Show Gist options
  • Save potix2/1223873 to your computer and use it in GitHub Desktop.
Save potix2/1223873 to your computer and use it in GitHub Desktop.
Sudoku Solver (easy level)
function complete(data) {
var result = true;
var sum;
for ( var i = 0; i < 9; i++ ) {
sum = 0;
for ( var j = 0; j < 9; j++ ) {
sum += data[i * 9 + j];
}
if ( sum != 45 ) {
result = false;
break;
}
}
return result;
}
var __checker = [1,2,3,4,5,6,7,8,9];
function basicsud(s) {
var stillchanging = true;
while ( stillchanging ) {
stillchanging = false;
for ( var i = 0; i < 81; i++ ) {
if ( s[i] == 0 ) {
var check = {};
var row = Math.floor(i / 9);
var col = i % 9;
var in_row = Math.floor(row / 3) * 3;
var in_col = Math.floor(col / 3) * 3;
for ( var j = 0; j < 9; j++ ) {
check[s[row * 9 + j]] = 1;
check[s[j * 9 + col]] = 1;
check[s[(in_row + Math.floor(j / 3)) * 9 + in_col + (j % 3)]] = 1;
}
var m = __checker.filter(function(elem, index, arr) {
return !check.hasOwnProperty(elem);
});
if ( m.length == 0 ) {
return null;
}
else if ( m.length == 1 ) {
s[i] = m[0];
stillchanging = true;
}
}
}
}
return s;
}
function solver(s) {
var s1 = basicsud(s);
if ( s1 == null ) {
return null;
}
if ( complete(s1) ) {
return s1;
}
else {
var stack = [];
for ( var i = 0; i < 81; i++ ) {
if ( s1[i] == 0 ) {
var check = {};
var row = Math.floor(i / 9);
var col = i % 9;
var in_row = Math.floor(row / 3) * 3;
var in_col = Math.floor(col / 3) * 3;
for ( var k = 0; k < 9; k++ ) {
check[s1[row * 9 + k]] = 1;
check[s1[k * 9 + col]] = 1;
check[s1[(in_row + Math.floor(k / 3)) * 9 + in_col + (k % 3)]] = 1;
}
var m = __checker.filter(function(elem, index, arr) {
return !check.hasOwnProperty(elem);
});
if ( m.length > 2 ) {
for ( var l = 0; l < m.length; l++ ) {
stack.push($.toJSON(s1));
s1[i] = m[l];
var s2 = solver(s1);
if ( complete(s2) ) return s2;
s1 = $.parseJSON(stack.pop());
}
}
}
}
}
return null;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment