8-puzzle solution using breadth-first method

breadFirstSearch.js

'use strict';

var endTime,
    startTime,
    counted = 0,
    counter = 1000,
    allSuc = [],
    hash = {},
    values = new Array(1000000),
    size = 0;

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

function move(state, successors, pos, steps) {
  var newState;
  newState = state.slice();
  swap(newState, pos, pos + steps);
  return newState;
}

function hashState(state) {
    var stateLength = state.length;
    var hash = 0;
    for(var i = 0; i < stateLength; i++) {
        hash += state[i] * Math.pow(stateLength, i);
    }
    return hash;
}

function getSuccessors(state) {
  var newState, _state;
  var successors = [];
  var pos = state.indexOf(0);
  var row = Math.floor(pos / 3);
  var col = pos % 3;
  if (row > 0) {
    //move up
    newState = move(state, successors, pos, -3);
    if (!compare(newState, state.prev)) {
      _state = hashState(newState);
      if (typeof hash[_state] === 'undefined') {
        hash[_state] = newState;
        newState.prev = state;
        successors.push(newState);
      }
    }
  }
  if (col > 0) {
    //move left
    newState = move(state, successors, pos, -1);
    if (!compare(newState, state.prev)) {
      _state = hashState(newState);
      if (typeof hash[_state] === 'undefined') {
        hash[_state] = newState;
        newState.prev = state;
        successors.push(newState);
      }
    }
  }
  if (row < 2) {
    //move down
    newState = move(state, successors, pos, 3);
    if (!compare(newState, state.prev)) {
      _state = hashState(newState);
      if (typeof hash[_state] === 'undefined') {
        hash[_state] = newState;
        newState.prev = state;
        successors.push(newState);
      }
    }
  }
  if (col < 2) {
    //move right
    newState = move(state, successors, pos, 1);
    if (!compare(newState, state.prev)) {
      _state = hashState(newState);
      if (typeof hash[_state] === 'undefined') {
        hash[_state] = newState;
        newState.prev = state;
        successors.push(newState);
      }
    }
  }
  return successors;
}

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

function statesPerSecond() {
  var now = new Date();
  if (now.getTime() - startTime.getTime() >= counter) {
    console.log('counted', counter, allSuc.length - counted);
    counted = allSuc.length;
    counter += 1000;
  }
}

function collateStates(i) {
  var _ = values[i].prev;
  var result = [values[i]];
  while (_) {
    for (var j = 0; j < size; j++) {
      if (compare(_, values[j])) {
        _ = values[j].prev;
        result.push(values[j]);
        break;
      }
    }
  }
  console.log(size);
  return result.reverse();
}

function breadthFirstSearch(state, goalState) {
  values = new Array(1000000);
  // size = 0;
  state.prev = null;
  values[0] = state;
  size++;
  for (var i = 0; i < size; i++) {
    statesPerSecond();
    if (compare(goalState, values[i])) {
      return collateStates(i);
    } else {
      var _successors = getSuccessors(values[i]);
      for (var k = 0; k < _successors.length; k++) {
        values[size] = _successors[k];
        size++;
      }
    }
  }
}

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;
}

/* 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;
}

/* 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;
}

function generatePuzzle(state) {
  var firstElement, secondElement;
  var _state = state.slice();
  shuffle(_state);
  if (!checkSolvable(_state)) {
    firstElement = _state[0] !== 0 ? 0 : 3;
    secondElement = _state[1] !== 0 ? 1 : 3;
    swap(_state, firstElement, secondElement);
  }
  // _state = [1, 0, 2, 3, 4, 5, 6, 7, 8];
  // _state = [0,7,4,8,2,1,5,3,6];
  // _state = [6,3,1,4,7,2,0,5,8];
  // _state = [8,0,1,3,4,7,2,6,5];
  _state = [8, 6, 7, 2, 5, 4, 3, 0, 1]; //32 steps
  // _state = [0,8,7,6,3,5,1,4,2]; //29 steps
  console.log('Puzzle to solve: [' + _state + ']');
  return _state;
}

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

time();

This is a good start. Generally the goal state has the 0 in the first position (i.e. [0,1,2,...]). You did a good job of coming to an initial solution, and now it's time to refactor a few things.

Typically it's better to name things what they are intended to be, so if someone comes along trying to figure out how the program works, it's a little easier to look through if they already understand the algorithms. Renaming solver to breadthFirstSearch is a good idea along those lines. Along those same lines, extract out a function from solver to handle building the solution so it doesn't overwhelm the visual flow of the breadth first search algorithm.

You are using slice in a lot of places that it is not necessary. The only time you need to be careful about what you're doing is when you are writing to a data structure; reading does not alter the state, so there is no need to copy an array before a read. Memory allocations are one of the slowest operations in all of programming, regardless of the language. Getting rid of all the unneeded array copies will help with performance quite a bit.

When all the program is doing is math, it's quite fast. Output is very slow, particularly writing to the console. Instead of outputting on every iteration, set a repeating timer that outputs the number of iterations once every second or so and cancel the timer when the solution is found.

You mentioned it is an infinite loop when you're trying puzzles with longer solutions. This is not entirely correct. If you let it run long enough, it will find a solution, although it might take a very long time. Let's assume that the branching factor is (2_4)+(3_4)+(4*1)/9 = ~2.67. I derived that by saying the 4 corners have a branching factor of 2, the 4 center edges have a branching factor of 3 and the center square has a branching factor of 4. Then divide by 9 because there are 9 possible places for the blank. The hardest starting state has a solution length of 31. Math.pow(2.67, 31) = ~16 trillion. That's a seriously big number. Even if you could evaluate 1,000,000 states per second (a reasonable estimate), it would take 193 days to finish, but you'd almost certainly run out of memory way before that anyway.

A very naive, yet exceptionally powerful improvement is to not immediately move the blank space back to where it just came from. I.E. if you arrived at the current state by moving the blank up, then don't expand the successor that moves the state back down to where it just came from, and the same is true for all directions. This changes the branching factor significantly. (1_4)+(2_4)+(3*1)/9 = ~1.67. Math.pow(1.67, 31) = ~8 million. Now if you can evaluate 1,000,000 states per second, it would only take about 8 seconds for the hardest problem. 193 days => 8 sec. That's a powerful improvement.

Alter your program to output how many states per second it evaluates and you can adjust the math to see how long the hardest problem would take. In any case, if you just did this naive improvement, you would be able to solve any random 8-puzzle in a very reasonable amount of time now.

Of course if you think about it, there are only 9! (362,880) unique states and obviously if we're evaluating 8 million states, we're evaluating a lot of states multiple times. That motivates keeping track of states you have already evaluated, so you can skip them when you run into them again. You need to be able to quickly check if you have already visited a state, which is harder than it seems. Try a few things and see what you can come up with. Fast lookups are often done with a hash set; you'll just have to figure it out for javascript.

Hopefully you'll have this figured out before our meeting on Thursday and we'll go over a couple of small changes that will get your code to a full A* search.

Thank you, Nick, for your feedback, I have optimised it, and it now runs in less than 2000 ms. I am open to suggestions to make this more optimised.