kopiro/sudoku-solver-with-bt.js

var puzzle = [
            [5,3,0,0,7,0,0,0,0],
            [6,0,0,1,9,5,0,0,0],
            [0,9,8,0,0,0,0,6,0],
            [8,0,0,0,6,0,0,0,3],
            [4,0,0,8,0,3,0,0,1],
            [7,0,0,0,2,0,0,0,6],
            [0,6,0,0,0,0,2,8,0],
            [0,0,0,4,1,9,0,0,5],
            [0,0,0,0,8,0,0,7,9]];

sudoku(puzzle);
/* Should return
[[5,3,4,6,7,8,9,1,2],
[6,7,2,1,9,5,3,4,8],
[1,9,8,3,4,2,5,6,7],
[8,5,9,7,6,1,4,2,3],
[4,2,6,8,5,3,7,9,1],
[7,1,3,9,2,4,8,5,6],
[9,6,1,5,3,7,2,8,4],
[2,8,7,4,1,9,6,3,5],
[3,4,5,2,8,6,1,7,9]]

function getp(puzzle, x, y) {
    var hash = {};

    for (var u = 0; u < 9; u++) {
        hash[ puzzle[y][u] ] = 
        hash[ puzzle[u][x] ] = 
        hash[ puzzle[ 3*((y/3)|0) + ((u/3)|0) ][ 3*((x/3)|0) + (u%3) ] ] = 1
    }

    var poss = [];
    for (var i = 1; i <= 9; i++) if (!(i in hash)) poss.push(i);
    return poss;
}

function sudoku(p) {
var f=[],a=function(p,d,e){var o=[],h={};
for(var u=0;++u<9;h[p[e][u]]=h[p[u][d]]=h[p[3*((e/3)|0)+((u/3)|0)][3*((d/3)|0)+(u%3)]]=1);
for(var i=10;--i>0;(i in h)?0:o.push(i));return o};
for(var n=0;++n<81;p[(n/9)|0][n%9]?0:f.push({v:n,p:0,i:0}));
for(var c,d,e,n=0,l=f.length;n<l;c=f[n],e=(c.v/9)|0,d=c.v%9,c.p=c.p||a(p,d,e),(c.i>=c.p.length)
?[p[e][d]=c.i=c.p=0,n--]:[p[e][d]=c.p[c.i++],n++]);return p}