This is the classic 15-puzzle, with the option of making it a 3x3 8-puzzle for ease or a 5x5 24-puzzle for a greater challenge. You are given a randomly shuffled grid, and your job is to output, in an array, the series of moves that will bring the grid to the correct arrangement - 0 at the top left, then 1 to the right, and progressively increasing numbers left to right then top to bottom from there. Moves are defined by the direction of "moving" the empty spot, or zero - 0 means sliding in the number above the vacant spot, 1 means sliding in the number on the right, 2 on the bottom and 3 on the left. For example, the arrangement:
312
045
678
with the move instruction 2 will become:
312
645
078
while the instruction 0 will solve the configuration. The easy solution can be found with A* search, but for the medium and hard solutions I recommend not even trying to find an optimal solution and instead using a search algorithm that first picks out possibilities solely based on the criterion of how similar they are to the solved state. States are just strings that represent the layout left to right, then top to bottom, with letters of the alphabet substituting for the higher numbers - for example, the solved 4x4 configuration is "0123456789abcdef", and moving 222111
from the configuration will get you to "41238567c9abdef0". Here is some code that will help:
//Alphabet
var sym = "0123456789abcdefghijklmnopqrstuvwxyz";
//A similarity heuristic of a state to the solved state
var distance = 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.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;
}
//Returns the result of moving in a direction from
//a state
var move = function(state,dir) {
var place = state.indexOf('0');
var size = Math.sqrt(state.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 state;
var newplace = newy * size + newx;
var output = state.replace('0',state[newplace])
output = output.substr(0,newplace) + '0' +
output.substr(newplace + 1);
return output;
}