# Fifteen Puzzle

The puzzle consists of a 4 by 4 grid containing 15 slideable squares and one blank space. The puzzle is initialized by randomly sliding the squares until they are sufficiently "shuffled". The player then moves individual squares, or entire rows/columns until the pieces are back in ascending order.

This is an excellent vehicle for teaching programming from novice to intermediate.

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ``` Drawing the puzzle is an excellent first iteration. Introduce `cout` and print a single line. Introduce loops and print the entire puzzle. Discuss the distinction between positions and numbers (there are 16 positions and 15 numbers). Introduce the tools of variables and arrays. How do you want to maintain the position of each number? Would a 2D [4][4] array or a 1D 16-element array be preferable?

How should moves be specified? Do you want to have the user move the empty space by specifying: up, down, left, or right? What about accepting a number, and having the program identify if the empty space is adjacent. To the right, when the user specifies 3, the program identifies that the 3 should be moved up.

 ``` 1 2 8 1 2 3 8 1 2 3 8 10 4 3 11 10 4 11 10 4 11 5 6 15 12 5 6 15 12 5 6 15 12 9 13 7 14 9 13 7 14 9 13 7 14 3 4 ```
What about designing this program to support a configurable width and height?

What about allowing multiple numbers to be moved at once?   Perhaps recursion would come in handy.

 ``` 1 9 10 17 2 1 9 10 17 2 1 9 10 17 2 4 1 9 10 17 2 4 8 3 11 5 16 4 8 3 11 5 16 4 8 3 11 5 16 8 3 11 5 16 13 14 7 15 12 6 13 14 7 15 12 6 13 14 7 15 12 6 13 14 7 15 12 6 2 4 3 ```

### Puzzle Solver

How hard would it be to create the capability to solve the puzzle autonomously? At a high level, what kind of algorithm would it take?

 ``` E E E ? E E E ? E E E ? ? ? ? ``` I think the 'E' locations are easy to fill; but the '?' locations are hard.
Jaap Scherphuis (`www.geocities.com/jaapsch/puzzles/fifteen.htm`) suggested the strategy portrayed to the right. For the '1' positions: move each number directly to its desired position. For the '2' positions: move each number to the position directly below its correct spot, with the space directly below that, then move the blank space in the following directions: up, up, left, down, right, down, left, up, up, right, down. [See the series of play below, reading from left-to-right and top-to-bottom.]

For the last 2 rows:

1. Rotate the puzzle a quarter turn to the right. The left column of the last two rows now becomes the top row.

2. Move the region '3' number directly to its position, and use the "last number on the row" algorithm to position the region '4' number, until there are only two rows left.

3. Move the pieces in the remaining 2x2 square around until one piece is positioned correctly (region 5), and the space is in the correct spot (region 6). The other two numbers will automatically be in their correct position.

The order for filling each position is given to the right.

 ``` 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 2 4 4 4 4 5 x 3 3 3 3 x 6 1 2 3 4 5 6 7 8 10 12 13 x 9 11 x 14 ```

 ``` 1 2 3 9 1 2 3 9 1 2 3 1 2 3 1 2 8 3 1 2 8 3 11 12 8 4 11 12 8 11 12 8 9 11 12 8 9 11 12 9 11 12 9 6 15 13 6 15 13 4 6 15 13 4 6 15 13 4 6 15 13 4 6 15 13 4 7 5 10 14 7 5 10 14 7 5 10 14 7 5 10 14 7 5 10 14 7 5 10 14 1 2 8 3 1 2 8 3 1 2 8 3 1 2 3 1 2 3 1 2 3 4 11 12 9 4 11 12 9 4 11 12 4 11 12 8 4 11 12 8 4 11 12 8 6 15 13 6 15 13 6 15 9 13 6 15 9 13 6 15 9 13 6 15 9 13 7 5 10 14 7 5 10 14 7 5 10 14 7 5 10 14 7 5 10 14 7 5 10 14 ```

The notion of moving a number "directly to its desired position" that was assumed above, requires some thought. Are you moving numbers? Or ... are you moving the blank space around?

 ``` 1 2 3 4 9 8 10 7 15 6 5 11 12 13 14 ``` To get the '5' to its correct column, do you want to move the blank space around the top of the '5', or around the bottom of it?
To get the '3' to its correct position, do you want to move the blank space around the left side of the '3', or around the right side?
 ``` 1 2 10 7 9 8 14 5 15 12 3 13 11 4 6 ```
If you had previously chosen to move the blank space around the left side of the number you are trying to position, will that choice work with this configuration?
 ``` 1 2 3 4 5 6 13 9 8 12 7 11 14 10 15 ```
 ``` 1 3 2 11 12 8 4 6 15 13 9 7 5 10 14 ``` To get the '2' to its correct position, do you want to move the blank space "through" the '2', or "around" it?
Can you move the blank space directly to the position over the '3'; or do you need to send it under, around, and then over the '3'?
 ``` 1 2 12 11 6 3 4 9 15 13 14 10 5 8 7 ```
impl