Sliding puzzle is a game composed by 2^{n} - 1 pieces dispersed along a board and a blank space. Those pieces are then shuffled and the objective is to rearrange them back to their original form, where the disposition of pieces is on ascending order, like shown below (go on, it’s interactive):
You can rearrange the pieces “moving” the blank space across the board. Since you can only move it in four directions, it’s a hell of a task to solve this game for a human, sometimes taking hours. Luckily, we dispose of some good algorithms to solve it, taking only few milliseconds even for the worst case. Let’s explore them in this tutorial! :)
Finding the correct abstraction
The hardest part of a problem is surely finding a useful abstraction for it, that allows a solution to be even thought! Like most path finding problems, the sliding puzzle can be correctly abstracted as a graph, i.e., a set of vertices connected by edges.
It’s common to use the term “state” to designate vertices. The meaning of a state depends on the problem. For example, for the sliding puzzle, each state is a determined disposition of pieces. Logically, there’s also a “goal state”, a state where the problem is solved. Finally, the edges are the allowed actions that takes our problem from a state to another. For example, in the sliding puzzle, the set of allowed actions is to move the blank space in four directions (up, down, left, right). The figure below illustrates well those concepts.
Assimilated those concepts, our job is simply to find a path from any state to the goal state, and that can be done with any graph search algorithm. Let’s discuss the pros/cons of some approaches.
Javascript implementation of Sliding Puzzle
Before discussing about specific algorithms, let’s implement the building blocks. I’ll start with a class called “Puzzle”, containing basically four attributes: dimension (dimension of our puzzle, i.e., 3 = 8-puzzle, 4 = 15-puzzle, etc.,…), the board (two-dimensional numeric array), the path and the last performed move (we will cover those last two later).
sliding-puzzle.js
1234567891011121314151617
functionPuzzle(dimension){this.dimension=dimension;this.board=[];this.path=[];this.lastMove=null;// Fill the boardfor(vari=0;i<dimension;i++){this.board.push([]);for(varj=0;j<dimension;j++){if(i==this.dimension-1&&j==this.dimension-1){this.board[i].push(0);}else{this.board[i].push(dimension*i+j+1);}}}}
Let’s create some utilitary methods that will help during the craft of our solution:
sliding-puzzle.js
1234567891011121314151617
// Get the (x, y) position of the blank spacePuzzle.prototype.getBlankSpacePosition=function(){for(vari=0;i<this.dimension;i++){for(varj=0;j<this.dimension;j++){if(this.board[i][j]==0){return[i,j];}}}};// Swap two items on a bidimensional arrayPuzzle.prototype.swap=function(i1,j1,i2,j2){vartemp=this.board[i1][j1];this.board[i1][j1]=this.board[i2][j2];this.board[i2][j2]=temp;}
And finally, let’s implement the methods that will move the pieces:
Direction={LEFT:"left",RIGHT:"right",UP:"up",DOWN:"dow"};// Return the direction that a piece can be moved, if anyPuzzle.prototype.getMove=function(piece){varblankSpacePosition=this.getBlankSpacePosition();varline=blankSpacePosition[0];varcolumn=blankSpacePosition[1];if(line>0&&piece==this.board[line-1][column]){returnDirection.DOWN;}elseif(line<this.dimension-1&&piece==this.board[line+1][column]){returnDirection.UP;}elseif(column>0&&piece==this.board[line][column-1]){returnDirection.RIGHT;}elseif(column<this.dimension-1&&piece==this.board[line][column+1]){returnDirection.LEFT;}};// Move a piece, if possible, and return the direction that it was movedPuzzle.prototype.move=function(piece){varmove=this.getMove(piece);if(move!=null){varblankSpacePosition=this.getBlankSpacePosition();varline=blankSpacePosition[0];varcolumn=blankSpacePosition[1];switch(move){caseDirection.LEFT:this.swap(line,column,line,column+1);break;caseDirection.RIGHT:this.swap(line,column,line,column-1);break;caseDirection.UP:this.swap(line,column,line+1,column);break;caseDirection.DOWN:this.swap(line,column,line-1,column);break;}if(move!=null){this.lastMove=piece;}returnmove;}};
Breadth-First Search (BFS)
The most well-known graph search algorithm, along with Depth-First Search (DFS). I believe you are already familiarized with this algorithm. It works really simple: For each visited node, its immediate children are stored on a queue, and it’s performed recursively until the queue is empty or a goal state is reached, that way transversing the graph “level-by-level”.
In order to implement the BFS, we are going to need first two method beforehand: “isGoalState” and “visit”. The “isGoalState” will check if the current state is a solution to the puzzle, while “visit” will generate the immediate children of the current state in the state space.
Let’s start with “isGoalState”. Well, it’s kinda simple: We are in a goal state if all pieces are in their places. The original place of a piece can be defined as [(piece - 1) % dimension, (piece - 1) / dimension]. Let’s take some examples to check if this formule makes sense:
About the “visit” method, first we need to know all allowed moves we can do in a certain state. For example, if the blank space is on the bottom-left of screen, we may not be able to move down nor left. Luckily, this functionality is already implemented through the method “getMove” described on previous section.
sliding-puzzle.js
12345678910111213
// Return all current allowed movesPuzzle.prototype.getAllowedMoves=function(){varallowedMoves=[];for(vari=0;i<this.dimension;i++){for(varj=0;j<this.dimension;j++){varpiece=this.board[i][j];if(this.getMove(piece)!=null){allowedMoves.push(piece);}}}returnallowedMoves;};
But knowing the allowed moves is not enough. We need to generate new states. In order to do that, we are going to need an utilitary method that makes a copy of the current state:
sliding-puzzle.js
12345678910111213
// Return a copy of current puzzlePuzzle.prototype.getCopy=function(){varnewPuzzle=newPuzzle(this.dimension);for(vari=0;i<this.dimension;i++){for(varj=0;j<this.dimension;j++){newPuzzle.board[i][j]=this.board[i][j];}}for(vari=0;i<this.path.length;i++){newPuzzle.path.push(this.path[i]);}returnnewPuzzle;};
Notice that we are not just copying the board, but also the path. “path” is an attribute that stores the pieces that were moved so far, that way allowing us to reexecute the whole process when a goal state is found.
Notice that we are ignoring moves that are equal to “lastMove”. There’s a reason behind it: Moving a piece that was already moved on the last turn will only make it to turn back to its original position! In another words, going back to a state that was already explored. That why we are “prunning” the tree avoiding this kind of behavior.
*sigh* After all those necessary things, we are now ready to finally implement the BFS algorithm, that is ridiculously simple:
We create an array called “states” to store the states that are waiting to be visited and put the current state on it. On a loop, we remove the first element (through the “shift” method, remember we are simulating a queue) and then check if that element is a goal state. If it is, return the sets of steps from our initial state until it (the “path” attribute), otherwise visit it and append the immediate children to the list of states.
*BONUS*! You can check a simulation below:
BFS
Time elapsed: 0ms
PRO: It’s easy to be implemented. CON: Waaaaaaay too slow.
A*
As we saw previously, the BFS can correctly find an optimal solution to our problem, i.e., find a path from the starting state to the goal state with the minimum number of steps, but it has a huge drawback: it’s too slow! If you shuffle the game too much and try to run it, it will possibly freeze your browser.
So here’s the A*, the top #1 favorite algorithm for problem solving agents, and, good for us, it’s pretty simple too!
It works similarly to BFS, but with some differences: Instead of a queue, we use a priority queue (a.k.a., min-heap), that is a data structure that instead of returning the first element added, it returns the element with lowest value. And, to each discovered state, we assign a value to it, that can be defined as:
f(n) = g(n) + h(n)
g(n) (called real cost function) is the cost necessary to go from the starting state to the state n. Since we already discovered the whole path to it, we can easily calculate that cost with precision (for our sliding puzzle example, that cost can be represented as the path length, for example).
h(n) (called heuristic function) is the estimated cost to go from the state n to the goal state. But here’s the trick: We don’t know the path from state n to the goal state yet! It’s called heuristic precisely because we use heuristics to estimate it.
For priority-queue implementation, I’m going to use that you can you find here.
Good, good. Now let’s implement the “g” and “h” functions. For “g” function, I’ll simply count the path length (what else could be considered as the real cost?):
The heuristic function is the tricky part. We could think in many things. It’s important the heuristic be admissible, i.e., it must underestimate the real cost until the goal state. The closer the estimated value by heuristic function is to the real cost to go to the goal state, the better.
Heuristic #1: Misplaced tiles
This function counts simply the number of pieces(tiles) that are not in their final position. This function is almost identical to the one we implemented to check if a state is the goal:
Instead of just counting the number of misplaced tiles, this heuristic function calculates the manhattan distance (L1 distance) between the current misplaced position and the final position. Manhattan distance can be calculated as:
Direction={LEFT:"left",RIGHT:"right",UP:"up",DOWN:"dow"};Algorithm={BFS:"BFS",AMisplaced:"A*: Misplaced tiles",AManhattan:"A*: Manhattan distance"};functionPuzzle(dimension,solve_func){this.board=[];this.path=[];this.dimension=dimension;this.solve_func=solve_func;this.lastMove=null;for(vari=0;i<dimension;i++){this.board.push([]);for(varj=0;j<dimension;j++){if(i==this.dimension-1&&j==this.dimension-1){this.board[i].push(0);}else{this.board[i].push(dimension*i+j+1);}}}};// Get the (x, y) position of the blank spacePuzzle.prototype.getBlankSpacePosition=function(){for(vari=0;i<this.dimension;i++){for(varj=0;j<this.dimension;j++){if(this.board[i][j]==0){return[i,j];}}}};// Swap two items on a bidimensional arrayPuzzle.prototype.swap=function(i1,j1,i2,j2){vartemp=this.board[i1][j1];this.board[i1][j1]=this.board[i2][j2];this.board[i2][j2]=temp;}// Return the direction that a piece can be moved, if anyPuzzle.prototype.getMove=function(piece){varblankSpacePosition=this.getBlankSpacePosition();varline=blankSpacePosition[0];varcolumn=blankSpacePosition[1];if(line>0&&piece==this.board[line-1][column]){returnDirection.DOWN;}elseif(line<this.dimension-1&&piece==this.board[line+1][column]){returnDirection.UP;}elseif(column>0&&piece==this.board[line][column-1]){returnDirection.RIGHT;}elseif(column<this.dimension-1&&piece==this.board[line][column+1]){returnDirection.LEFT;}};// Move a piece, if possible, and return the direction that it was movedPuzzle.prototype.move=function(piece){varmove=this.getMove(piece);if(move!=null){varblankSpacePosition=this.getBlankSpacePosition();varline=blankSpacePosition[0];varcolumn=blankSpacePosition[1];switch(move){caseDirection.LEFT:this.swap(line,column,line,column+1);break;caseDirection.RIGHT:this.swap(line,column,line,column-1);break;caseDirection.UP:this.swap(line,column,line+1,column);break;caseDirection.DOWN:this.swap(line,column,line-1,column);break;}if(move!=null){this.lastMove=piece;}returnmove;}};Puzzle.prototype.isGoalState=function(){for(vari=0;i<this.dimension;i++){for(varj=0;j<this.dimension;j++){varpiece=this.board[i][j];if(piece!=0){varoriginalLine=Math.floor((piece-1)/this.dimension);varoriginalColumn=(piece-1)%this.dimension;if(i!=originalLine||j!=originalColumn)returnfalse;}}}returntrue;};// Return a copy of current puzzlePuzzle.prototype.getCopy=function(){varnewPuzzle=newPuzzle(this.dimension);for(vari=0;i<this.dimension;i++){for(varj=0;j<this.dimension;j++){newPuzzle.board[i][j]=this.board[i][j];}}for(vari=0;i<this.path.length;i++){newPuzzle.path.push(this.path[i]);}returnnewPuzzle;};// Return all current allowed movesPuzzle.prototype.getAllowedMoves=function(){varallowedMoves=[];for(vari=0;i<this.dimension;i++){for(varj=0;j<this.dimension;j++){varpiece=this.board[i][j];if(this.getMove(piece)!=null){allowedMoves.push(piece);}}}returnallowedMoves;};Puzzle.prototype.visit=function(){varchildren=[];varallowedMoves=this.getAllowedMoves();for(vari=0;i<allowedMoves.length;i++){varmove=allowedMoves[i];if(move!=this.lastMove){varnewInstance=this.getCopy();newInstance.move(move);newInstance.path.push(move);children.push(newInstance);}}returnchildren;};Puzzle.prototype.solveBFS=function(){varstartingState=this.getCopy();startingState.path=[];varstates=[startingState];while(states.length>0){varstate=states[0];states.shift();if(state.isGoalState()){returnstate.path;}states=states.concat(state.visit());}};Puzzle.prototype.g=function(){returnthis.path.length;};Puzzle.prototype.getManhattanDistance=function(){vardistance=0;for(vari=0;i<this.dimension;i++){for(varj=0;j<this.dimension;j++){varpiece=this.board[i][j];if(piece!=0){varoriginalLine=Math.floor((piece-1)/this.dimension);varoriginalColumn=(piece-1)%this.dimension;distance+=Math.abs(i-originalLine)+Math.abs(j-originalColumn);}}}returndistance;};Puzzle.prototype.countMisplaced=function(){varcount=0;for(vari=0;i<this.dimension;i++){for(varj=0;j<this.dimension;j++){varpiece=this.board[i][j];if(piece!=0){varoriginalLine=Math.floor((piece-1)/this.dimension);varoriginalColumn=(piece-1)%this.dimension;if(i!=originalLine||j!=originalColumn)count++;}}}returncount;}Puzzle.prototype.h=function(){if(this.solve_func==Algorithm.AMisplaced){returnthis.countMisplaced();}else{returnthis.getManhattanDistance();}};Puzzle.prototype.solveA=function(){varstates=newMinHeap(null,function(a,b){returna.distance-b.distance;});this.path=[];states.push({puzzle:this,distance:0});while(states.size()>0){varstate=states.pop().puzzle;if(state.isGoalState()){returnstate.path;}varchildren=state.visit();for(vari=0;i<children.length;i++){varchild=children[i];varf=child.g()+child.h();states.push({puzzle:child,distance:f});}}};Puzzle.prototype.solve=function(){if(this.solve_func==Algorithm.BFS){returnthis.solveBFS();}else{returnthis.solveA();}};
And since this page itself is utilizing this code for demonstration, you can also get it visualizing the source code.
Conclusion
Well, that was a quite interesting tutorial. We discussed about space of states, goal state, graph search algorithms, A* and admissible heuristics. I hope you have enjoyed reading this tutorial as much as I did writing it. See ya on the next tutorial! :D