Solution to n-puzzle using a-star algorithm

aStar.js

'use strict';

var goalState = [0, 1, 2, 3, 4, 5, 6, 7, 8];
var hash = {},
  openList = [],
  startTime,
  endTime,
  solved = false,
  steps = 0,
  counter = 100,
  counted = 0,
  checked = 0;

function statesPer100Millisecond() {
  var now = new Date();
  if (now.getTime() - startTime.getTime() >= counter) {
    console.log('counted', counter, checked - counted);
    counted = checked;
    counter += 100;
  }
}

/* Fisher-Yates shuffle http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle*/
function shuffle(array) {
  var size = array.length;
  var rand;
  for (var i = 1; i < size; i += 1) {
    rand = Math.round(Math.random() * i);
    swap(array, rand, i);
  }
  return array;
}

/* This post on stackexchange explained the condition when a puzzle
   is unsolvable http://math.stackexchange.com/a/838818
*/
function checkSolvable(state) {
  var pos = state.indexOf(0);
  var _state = state.slice();
  _state.splice(pos,1);
  var count = 0;
  for (var i = 0; i < _state.length; i++) {
    for (var j = i + 1; j < _state.length; j++) {
      if (_state[i] > _state[j]) {
        count++;
      }
    }
  }
  return count % 2 === 0;
}

function generatePuzzle(state) {
  var _state = state.slice();
  shuffle(_state);
  if(!checkSolvable(_state)) {
    swap(_state, 0, 1);
  }
  console.log('Puzzle to solve: [' + _state + ']');
  return _state;
}

function move(state, successors, pos, steps) {
  var _state, newState;
  newState = state.slice();
  swap(newState, pos, pos + steps);
  if (!compare(newState, state.prev)) {
    _state = newState.join('');
    if (typeof hash[_state] === 'undefined') {
      hash[_state] = newState;
      newState.prev = state;
      newState.manhanttanDistance = calcManhanttanDistance(newState);
      newState.levels = newState.prev.levels + 1;
      successors.push(newState);
    }
  }
}

function swap(state, from, to) {
  var _ = state[from];
  state[from] = state[to];
  state[to] = _;
}

function compare(arr1, arr2) {
  if (!arr1 || !arr2) {
    return false;
  }

  for (var i = 0; i < arr1.length; i++) {
    if (arr1[i] !== arr2[i]) {
      return false;
    }
  }
  return true;
}


function getSuccessors(state) {
  var successors = [];
  var pos = state.indexOf(0);
  var row = Math.floor(pos / 3);
  var col = pos % 3;
  if (row > 0) {
    //move up
    move(state, successors, pos, -3);
  }
  if (col > 0) {
    //move left
    move(state, successors, pos, -1);
  }
  if (row < 2) {
    //move down
    move(state, successors, pos, 3);
  }
  if (col < 2) {
    //move right
    move(state, successors, pos, 1);
  }
  return successors;
}

function calcManhanttanDistance(state) {
  var totalDist = 0;
  for (var i = 0; i < state.length - 1; i++) {
    if (state[i] !== 0) {
      var realPos = goalState.indexOf(state[i]);
      var realCol = realPos % 3;
      var realRow = Math.floor(realPos / 3);
      var col = i % 3;
      var row = Math.floor(i / 3);
      totalDist += (Math.abs(realCol - col) + Math.abs(realRow - row));
    }
  }
  return totalDist;
}

function collateSteps(state) {
  console.log(state.splice(0, 9));
  steps++;
  if (!state.prev) {
    console.log(state, steps);
    return state;
  }
  collateSteps(state.prev);
}

function aStarSearch(state) {
  state.levels = 0;
  state.prev = null;
  openList.push(state);
  while (solved !== true) {
    var currentState = openList.shift();
    checked++;
    statesPer100Millisecond();
    var successors = getSuccessors(currentState);
    for (var i = 0; i < successors.length; i++) {
      if (compare(goalState, successors[i])) {
        solved = true;
        collateSteps(successors[i]);
        break;
      } else {
        heap(openList, successors[i]);
      }
    }
  }
}

function parent(index) {
  return Math.floor((index - 1) / 2);
}

function heap(state, successor) {
  state.push(successor);
  var node = state.length - 1;
  while (parent(node) >= 0 && node > 0) {
    var parentElement = state[parent(node)];
    var currentElement = state[node];
    var totalWeightA = parentElement.manhanttanDistance + parentElement.levels;
    var totalWeightB = currentElement.manhanttanDistance + currentElement.levels;
    if (totalWeightA >= totalWeightB) {
      swap(state, parent(node), node);
      node = parent(node);
      continue;
    }
    break;
  }
}


function time() {
  var puzzle = generatePuzzle(goalState);
  startTime = new Date();
  aStarSearch(puzzle);
  endTime = new Date();
  console.log('Operation took ' + (endTime.getTime() - startTime.getTime()) + ' msec');
}
time();

checkSolvable: this implementation is not 100% right. You cannot count inversions that include the blank tile. In the outerloop just skip the iteration if the index is the blank tile. In the inner loop skip counting if the blank tile is being checked against.

generatePuzzle: along those same lines, this is incorrect because swapping the blank tile won't add or remove a countable inversion. Swap the first 2 non blank tile indexes.

move: right now it's doing like 5 things, and it should only be doing 1. Get rid of the the call to compare, get rid of the call to calculateManhattanDistance, get rid of setting the level and get rid of adding it directly to the successors list. All it should do is copy the state, make the swap and return it, all of those other functions are the responsibility of some other function.

getSuccessors: on your state you're calling the cost of that state levels. Fix the naming because it is much easier to understand for people who are familiar with A*. getSuccessors should be responsible for setting the cost (and only the cost!). Why? In the N-puzzle the cost of each step is always 1, that's not true for all problem, in particular getting driving directions where the cost of each step might be measure in number of seconds that step will take. Often times that's done via some function to calculate it and the getSuccessors function is the only function responsible for calling that function.

There is the case of getting rid of the "move back". This is a difficult thing to place exactly where it should go, but it's typically handled in getSuccessors. There is a shortcut (performance-wise) to checking it. On each state, store the direction you used to get there. In your if statements, check to make sure that value doesn't equal the opposite of the direction each check is trying to move. i.e. if your state.direction = r, don't expand the move that would try to move left. You can skip ever generating the state with one comparison instead of actually generating the state and then looping over the whole thing to see if it's the same.

calcManhanttanDistance: good job on this one, you did it the most correct possible. Often times the goal state is consider to be that each index has that tile number in the goal state. They choose that goal state to make this calculation more efficient by not having to do the index of for each value. You correctly are doing the index of which is good because your code can handle any goal state. I just want to make sure you were aware of that.

aStarSearch: this is really good, the only thing you need to do is pull the heuristic calculation in here. On the state, you have a property called manhattanDistance, which needs to be renamed heuristicCost, for those people who know A* again. For each successor, calculate the cost of the heuristic in the aStarSearch function, then calculate the totalCost and store that on the state also so you are not recalculating it over and over. Other than that, just read about your heap implementation.

heap: this is broken, and will actually cause your heap to be invalid. You are handling the push case correctly. You are not handling the pop case correctly. You cannot just remove the top element with a shift, because it's possible the left hand child of the root node is higher than the right hand child. e.g. [0,2,1], when you shift the top element off you'll end up with, [2,1] which is an invalid heap. In pop you have to remember top element, move the last element to the top, then sink it back down to until the heap property is restored, then return the remembered top element from the first step. You also have to remember the size yourself because the array length wont represent the actual number of elements on the heap after you pop the first one. It's a lot of work, yes, but this is imperative in order for the algorithm to be correct.

---

Now all that is awesome and you have to fix the heap first and foremost, but it still doesn't explain the slowdown you're experiencing. I'll give you a hint. You had something in the BFS version that you removed from this version, and it's the thing that makes it super efficient.

The only other thing I would say is when you're testing, make sure you're using the same state every time because otherwise the runs are not comparable.