// Sudoku solving and hinting engine in Javascript.
// Thanksgiving 2008 version 11-28-2008
// Copyright 2008 David Bau, all rights reserved.

function solution(board, limit) {
  if (typeof(limit) == 'undefined') limit = Infinity;
  return solvefast(board, limit).solution;
}

function solvable(board, limit) {
  if (typeof(limit) == 'undefined') limit = Infinity;
  return solvefast(board, limit).solution !== null;
}

function uniquesolution(board) {
  var s = solvefast(board, Infinity);
  if (s.solution === null) return false;
  s = solvenext(s.track, Infinity);
  return (s.solution === null);
}

function easysolution(board) {
  var deduced = board.slice();
  return null === deduce(deduced);
}

function makepuzzle(board, hard) {
  var solved = solution(board);
  var order1 = [];
  var order2 = [];
  var deduced = emptyboard();
  var puzzle = [];
  for (var i = 0; i < 81; i++) {
    if (board[i] !== null) order1.push(i);
    else order2.push(i);
  }
  shuffle(order1);
  shuffle(order2);
  var order = order1.concat(order2);
  var edge = 0;
  for (var i in order) {
    var pos = order[i];
    if (i == order1.length) edge = puzzle.length;
    if (deduced[pos] === null) {
      puzzle.push([pos, solved[pos]]);
      deduced[pos] = solved[pos];
      deduce(deduced);
    }
  }
  var puzzle1 = puzzle.slice(0, edge);
  var puzzle2 = puzzle.slice(edge);
  shuffle(puzzle1);
  shuffle(puzzle2);
  puzzle = puzzle1.concat(puzzle2);
  for (var i = puzzle.length - 1; i >= 0; i--) {
    var old = puzzle[i];
    puzzle.splice(i, 1);
    var remove = hard ? uniquesolution(boardforentries(puzzle)) :
                        easysolution(boardforentries(puzzle));
    if (!remove) {
      puzzle.splice(i, 0, old);
    }
  }
  return boardforentries(puzzle);
}  

function solvefast(original, limit) {
  // Almost always, a board can be solved - or proved to have no solution -
  // in less than 100 steps.  However, when given an unsolvable board,
  // it is possible to get stuck in an unlucky path that leads to an
  // exponential explosion of backtracking, so we run "rabbits" in
  // parallel to the main "turtle" to expore other paths.
  var turtle = solveboard(original, 100);
  var steps = 100;
  var rabbitsteps = 60;
  while (steps < limit) {
    if (turtle.solution !== null || turtle.track.length == 0) return turtle;
    var rabbit = solveboard(original, rabbitsteps);
    if (rabbit.solution !== null || rabbit.track.length == 0) return rabbit;
    turtle = solvenext(turtle.track, rabbitsteps);
    steps += 2 * rabbitsteps;
    rabbitsteps += 10;
  }
}
  
function solveboard(original, limit) {
  var board = original.slice();
  var guesses = deduce(board);
  if (guesses === null) return {track:[], solution:board};
  return solvenext([{guesses:guesses, c:0, board:board}], limit);
}

function solvenext(remembered, limit) {
  var steps = 0;
  while (remembered.length > 0 && steps < limit) {
    steps += 1;
    var r = remembered.pop();
    if (r.c >= r.guesses.length) continue;
    remembered.push({guesses:r.guesses, c:r.c+1, board:r.board});
    workspace = r.board.slice();
    workspace[r.guesses[r.c][0]] = r.guesses[r.c][1];
    newguesses = deduce(workspace);
    if (newguesses === null) {
      return {track:remembered, solution:workspace};
    }
    remembered.push({guesses:newguesses, c:0, board:workspace});
  }
  return {track:remembered, solution:null};
}

function allowed(board, pos) {
  var deduced = board.slice();
  deduce(deduced);
  if (deduced[pos] !== null) return (1 << deduced[pos]);
  var bits = figurebits(deduced, true);
  return bits.allowed[pos];
}

function deduce(board) {
  while (true) {
    var choices = hint(board, false);
    if (choices.length == 0) return null;
    if (choices[0].length != 1) return choices[0];
    for (i in choices) {
      board[choices[i][0][0]] = choices[i][0][1];
    }
  }
}

function hint(board, advanced) {
  var result = []
  var bits = figurebits(board, advanced);
  for (var pos = 0; pos < 81; pos++) {
    if (board[pos] === null) {
      var numbers = listbits(bits.allowed[pos]);
      var choices = [];
      for (var i in numbers) { choices.push([pos, numbers[i]]); }
      updatechoices(result, choices);
    }
  }
  for (var axis = 0; axis < 3; axis++) {
    for (var x = 0; x < 9; x++) {
      var numbers = listbits(bits.needed[axis * 9 + x]);
      for (var i in numbers) {
        bit = 1 << numbers[i];
        var choices = [];
        for (var y = 0; y < 9; y++) {
          var pos = posfor(x, y, axis);
          if (bits.allowed[pos] & bit) { choices.push([pos, numbers[i]]); }
        }
        updatechoices(result, choices);
      }
    }
  }
  shuffle(result);
  if (result.length) shuffle(result[0]);
  return result;
}

function figurebits(board, advanced) {
  var needed = [];
  var allowed = [];
  for (var i in board) {
    if (board[i] === null) allowed.push(511);
    else allowed.push(0);
  }
  for (var axis = 0; axis < 3; axis++) {
    for (var x = 0; x < 9; x++) {
      var bits = axismissing(board, x, axis);
      needed.push(bits);
      for (var y = 0; y < 9; y++) {
        allowed[posfor(x, y, axis)] &= bits
      }
    }
  }
  if (advanced) {
    figuretuples(allowed);
  }
  return {allowed:allowed, needed:needed};
}

function figuretuples(allowed) {
  var mask = [];
  for (var i = 0; i < 81; i++) mask.push(511);
  for (var axis = 0; axis < 3; axis++) {
    for (var x = 0; x < 9; x++) {
      a = [];
      m = masktuples(allowed, x, axis);
      for (var y = 0; y < 9; y++) {
        mask[posfor(x, y, axis)] &= m[y];
      }
    }
  }
  for (var i = 0; i < 81; i++) {
    allowed[i] &= mask[i];
  }
}

function masktuples(allowed, x, axis) {
  // For each number, form a bit vector of allowed positions
  var positions = [0, 0, 0, 0, 0, 0, 0, 0, 0];
  for (var i = 0; i < 9; i++) {
    var a = allowed[posfor(x, i, axis)];
    for (var j = 0; j < 9; j++) {
      if (((1 << j) & a) != 0)
        positions[j] |= (1 << i);
    }
  }
  var cpos = [];
  var num = [];
  // Ignore numbers with no allowed positions
  for (var i in positions) {
    if (positions[i] != 0 && positions[i] != 511) {
      num.push(i);
      cpos.push(positions[i]);
    }
  }
  // Total number of interesting combinations
  var combinations = (1 << cpos.length);
  var mask = [511, 511, 511, 511, 511, 511, 511, 511, 511];
  // Find tuples
  for (var i = 0; i < combinations; i++) {
    var combine = listbits(i);
    var places = 0;
    for (var j in combine) {
      places |= cpos[combine[j]];
    }
    var spots = listbits(places);
    // Found a tuple
    if (spots.length && spots.length == combine.length) {
      var allowed = 0;
      for (var j in combine) {
        allowed |= (1 << num[combine[j]]);
      }
      for (var j in spots) {
        mask[spots[j]] &= allowed;
      }
    }
  }
  return mask;
}

function posfor(x, y, axis) {
  if (axis == 0) return x * 9 + y;
  if (axis == 1) return y * 9 + x;
  return [0,3,6,27,30,33,54,57,60][x] + [0,1,2,9,10,11,18,19,20][y];
}

function axisfor(pos, axis) {
  if (axis == 0) return (pos - pos % 9) / 9;
  if (axis == 1) return pos % 9;
  return ((pos - pos % 27) / 27) * 3 + ((pos - pos % 3) / 3) % 3;
}

function axismissing(board, x, axis) {
  var bits = 0
  for (var y = 0; y < 9; y++) {
    var e = board[posfor(x, y, axis)]
    if (e !== null) bits |= 1 << e;
  }
  return 511 ^ bits;
}

function listbits(bits) {
  var result = []
  for (var y = 0; y < 9; y++) {
    if (0 != (bits & (1 << y))) result.push(y);
  }
  return result;
}

function updatechoices(result, choices) {
  if (result.length) {
    if (choices.length > result[0].length) return;
    if (choices.length < result[0].length) result.length = 0;
  }
  result.push(choices);
}

function boardforentries(entries) {
  var result = emptyboard();
  for (var i in entries) {
    result[entries[i][0]] = entries[i][1];
  }
  return result;
}

function emptyboard() {
  var result = [];
  for (var pos = 0; pos < 81; pos++) {
    result.push(null);
  }
  return result;
}

function shuffle(o) {
  for (var j, x, i = o.length; i;
       j = parseInt(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x);
  return o;
}