# Sliding Block Puzzle Solver Algorithm

### The Puzzle

This was a fun exercise to write a solver for an NxN sliding block puzzle. This is also known as a 16-puzzle.

A board consists of NxN spaces, with numbers 1 to (N^2-1). In a 4x4 puzzle, this tiles are numbered 1-15. One space is empty, and is used to shuffle the tiles around the board.

The goal of this exercise is to write a solving algorithm to solve the NxN puzzle.

Notes:

- A locked spot/row/column is ineligible to be visited by the empty spot.
- I think of a board as a grid, from (0,0) in the top left to (N,N) at the lower right.
- Moves are in relation to the empty spot. For instance, moving
*up*would move the tile above the empty spot*down*. - This does not find the shortest set of moves, but trades this for a reasonable complexity against large puzzles (e.g., 10x10)

### The Algorithm - high-level:

- Starting in the top left corner of the board (0,0)
- Solve the row
- Solve the column
- Advance diagonally to the next corner (1,1) repeat steps 2-4 until there are only 3 left in the bottom square.
- Crunch Last Square: Solve last 3 tiles: until solved, or too many attempts are made, move empty space clockwise: left,up,right,down
- Optimize: Remove every no-op move pairs: (up,down), (down,up), (left,right), (right,left)

### To solve a row:

- For each number except the last two in the row, move the target value into its spot and lock it
- Move the
*last*value in this row to the bottom right spot in the board - Stage the
*second to last*value in the*last*spot in the row and lock it. - Stage the
*last*value beneath the*second to last*value and lock it - Unlock both values
- Sweep both values into place via the second-to last spot (moves: right,down). Lock the row.

(The column algorithm is the same, except rotated vertically)

### To move a target value from it’s current location to a particular spot (x,y):

- Find the location of the value on the board
- Find the path between its location and the target location (x,y) as a set of nodes with moves (e.g,
`up`

,`down`

,`left`

,`right`

) - Execute that set of moves
*against*the target value (e.g.,`up`

means “move the empty space above the value, then move down”)

High-Level Algorithm to move a target value `val`

to (x,y).

`moveVal(val, moveName)`

essentially moves a target value in a particular direction. It locks the spot to avoid passing over it.

Take note of the `DELTA_MAP`

which knows where the empty space should be to execute an operation. For instance, to move something *up*, the empty space has to be ABOVE the target value, then MOVE DOWN.

Goto is implemented as finding the path between two spots, and moving there.

Note: This is different from `moveValToSpot`

because it is an operation on the empty space itself.

### Even Yet Deeper: To find a path between two spots (x1,y1) to (x2,y2):

This is a recursive algorithm for finding the path between two spots. The result is a list of anonymous objects that each have a functional reference to the move operation against the empty space.

This algorithm is used for two purposes: moving a target value from A to B, and also moving the empty space around the board (to accomplish the former).

To find path from (x1,y1) to (x2,y2), while avoiding obstacles:

- If already at the target spot, return the current path (YAY!)
- Otherwise, find all
*eligible next spots*that from (x1,y1) that have*NOT*been visited before and SORT this list by distance to the TARGET spot (closest first) - For each move, put this move in a copy of the ‘current path’, and try to calculate the path from this node to the TARGET (x2,y2).
- If path is found, return the path (YAY!)
- If path is null, then remove entry from the list and try next value in list.

Algorithm in groovy:

Distance calculation (Remember from Algebra?):

Eligible values next to (x,y) (I thought this was cool):

Is legal location is defined as “on the board” AND “not locked” (It’s strucutred this way for readability…but I could be talked out of it)

###Get the source code, if you’re interested in trying it out: Get the Source Example GUI (knockoutjs)