sudoku_solver.js

function sudoku(puzzle) {
	if (solved(puzzle)) {
  	return puzzle;
  }
  var copy = puzzle.slice(0);
  for(var x=0;x<9; x++) {
    for(var y=0;y<9;y++) {
    	if (puzzle[x][y] !== 0) continue;
    	var available = get_available(puzzle, x,y);
      for(var i = 0; i < available.length;i++) {
        copy[x] = puzzle[x].slice(0);
        copy[x][y] = available[i];
        var result = sudoku(copy);
        if (result) {
          return result;
        }
      }
      //if we get this far we've run out of available pieces and should bail.
      return false;
    }
  }
}

function get_available(p,row, col) {
	var cols = ~~((col)/3);
  var rows = ~~((row)/3);
  
  var used = [];
  for (var i=0; i < 3; i++) {
  	for(var j=0; j < 3; j++) {
    	used.push(p[(rows*3)+i][(cols*3)+j]);
    }
  }
  used = used.concat(p[row]);
  for(var i=0;i<p.length;i++){
  	used.push(p[i][col]);
  }
  return [1,2,3,4,5,6,7,8,9].filter(function(x) {
  	return used.indexOf(x)=== -1;
  });
};

function solved(puzzle) {
	if(!valid(puzzle)) return false;
  for (var x=0;x<puzzle.length;x++) {
    for (var y=0;y<puzzle.length;y++) {
    	if(puzzle[x][y] === 0) {
      	return false;
      }
    }
  }
  return true;
}

function valid(puzzle) {
	for(var row=0;row<puzzle.length;row++){
    var used_h = [];
    var used_v = [];
  	for(var col=0;col<puzzle[row].length;col++) {
    	if(used_h.indexOf(puzzle[row][col]) >=0 || used_v.indexOf(puzzle[col][row]) >= 0) {
        return false;
      }
      if (puzzle[row][col] !== 0)
        used_h.push(puzzle[row][col]);
      if (puzzle[col][row] !== 0)
        used_v.push(puzzle[col][row]);
    }
  }
  return true;
};