http://aichallenges.appspot.com/fifteen solution

var sym = "0123456789abcdefghijklmnopqrstuvwxyz";
var heuristic = function(state) {
  var h = 0;
  var size = Math.sqrt(state.str.length);
  for (var x = 0; x < size; x++) {
    for (var y = 0; y < size; y++) {
      var val = sym.indexOf(state.str.charAt(x + y * size));
      var fx = val % size;
      var fy = Math.floor(val / size);
      if (val > 0) h += Math.abs(fx-x) + Math.abs(fy-y);
    }
  }
  return h;
}
var move = function(state,dir) {
    var input = state.str;
    var moves = state.moves.concat(dir);
    var place = input.indexOf('0');
    var size = Math.sqrt(input.length);
    var px = place % size;
    var py = Math.floor(place / size);
    var newx = px + [0,1,0,-1][dir];
    var newy = py + [-1,0,1,0][dir];
    if (newx < 0 || newy < 0 || newx >= size || newy >= size) return {'str':input,'moves':moves};
    var newplace = newy * size + newx;
    var output = input.replace('0',input[newplace])
    output = output.substr(0,newplace) + '0' + output.substr(newplace + 1);
    return {'str':output,'moves':moves};
}
var snapshot = function(list) {
  var s = "";
  for (var i = 0; i < list.length; i++) {
    s += list[i].str + " (" + heuristic(list[i]) + "); ";
  }
  return s;
}
var frontier = [];
var explored = [];
var binsearch = function(val) {
    var min = 0;
    var max = frontier.length - 1;
    while (max - min > 1) {
      var ave = Math.floor((max + min) * 0.5);
      if (heuristic(frontier[ave]) > val) min = ave;
      else max = ave;
    }
    if (frontier.length == 0) return 0;
    else if (val > heuristic(frontier[min])) return min;
    else if (val > heuristic(frontier[max])) return max;
    else return max + 1;
}
var unexplored = function(state) {
  for (var i = 0; i < explored.length; i++) {
    if (state.str == explored[i].str) return false;
  }
  return true;
}
this.run = function(map) {
  var count = 0;
  explored = [];
  frontier = [{'str':map,'moves':[]}];
  //var least = 99999;
  while (frontier.length > 0) {
    last = frontier.pop();
    if (unexplored(last)) {
      explored.push(last);
      if (last.str == sym.substring(0,last.str.length))
        return last.moves;
      for (var dir = 0; dir < 4; dir++) {
        var newstate = move(last,dir);
        var heur = heuristic(newstate);
        var place = binsearch(heur);
        //Pruning
        for (var p = frontier.length - 1; p >= 0; p--) {
          if (newstate.str == frontier[p].str) {
            frontier = frontier.slice(0,p).concat(
              frontier.slice(p+1));
            break;
          }
        }
        frontier = frontier.slice(0,place).concat(newstate,
          frontier.slice(place));
      }
    }
  }
}