1415 Puzzle  Generation & Automatic Solving 
Download Applet with Source (116 kb)
This applet allows you to investigate the socalled 1415 puzzle  of course you can also play it :). Although I think handling of this applet is quite intuitive, here are some notes to the controls:
Movement: You can move a tile by clicking on a tile that is next to the hole  this will move the tile to the hole, e.g.

clicking on tile 7 would result in 

Animation: check this to enable smooth movement of the tiles, otherwise they move in one step to the hole without animation. You can additionally adjust the animation speed. Note that this slider also influences the speed of the automatic solver playback  more concrete, it affects also the pause between each step of the solver.
Puzzle Generation: The are two buttons for generating a new random puzzle  it doesn't matter which method you use (see ???? for details), but ensure to check the 'Generate only solvable puzzles' if you really want to solve the generated puzzle  otherwise there is a 5050 chance that the created puzzle is not solvable at all.
Parity/Solvable: Here you can calculate the parity of the current puzzle (see ???) which is used to determine if a puzzle is solvable or not.
Solver: Press this button to start the automatic solver  the current puzzle is solved in front of your eyes!
For a good starting point of the origin of this puzzle, check the article at Wikipedia.
As I have already stated, some puzzles (well, approximately 50%) of all puzzles are not solvable. In fact, the original 1415 puzzle, that is the puzzle where only tiles 14 and 15 are swapped (the one you see when you start the applet) is also not solvable.
Here I present some notes along with a pseudocode algorithm that should gives you an idea why & how it works, but no mathematical prove  therefore you have to search somewhere else :)
At first, we introduce a disorder parameter that is defined as follows: For each tile, check how many tiles before this tile have a greater value than the tile itself (reading each row from left to right and top to bottom). An example will make it clear  look at following puzzle:

set disorder = 0; 
For our solvability argument, we do one additional step: We add the number of the row (starting with 0, that is 0..3) to the disorder parameter. To understand this, start with the solved puzzle:

It's easy to see that the disorder parameter is zero for the solved. Also note that moving the empty tile horizontally (left or right) does never change the disorder parameter. 

Playing around, e.g. moving the empty tile upwards, the disorder parameter changes to 3. 

Playing around, e.g. moving the empty tile upwards, the disorder parameter changes to 6. 
If you keep playing, you will notice that the disorder parameter is even if the empty tile is in the first or third row, and it its odd when the empty tile is in the second or fourth row. Contrary to this, consider the original puzzle state:

When you start with this setting, the disorder parameter is 1. 

If you play keep playing you'll notice that it's the other way round in this case! The disorder parameter is even if the empty tile is in the second or fourth row; it's odd if it's in the first or third row. 
Using these facts, we can summarize a solvability argument by defining the parity p:
where d_{i}= # tiles that are bigger than tile i and come before tile i and
The puzzle is solvable if p is even. In Pseudocode (assuming Puzzle is in array from 0 to 15 holding the puzzle tile where Value[0] to Value[3] are the tiles in the first row, Value[4] to Value[7] in the second row etc. Value[i] = 0 means the empty tile):
BOOL isSolvable() 
Although this is the most interesting part, I won't describe the automatic solver. In fact, the algorithm I implemented is already described  see [2] and [3]. Please also note the good explanation of the special cases in [2]  I must admit that I started implementing the algorithm but got stuck in such these special cases, so I 'borrowed' the good solution.
Here just an overview of the performance of the solver on my 2 PCs  2 million puzzles were generated:
Core2 T5500, 1,66Ghz, 2GB, WinXP X32 
Core i5750, Win7 X64 






I did not find useful information about generating a puzzle, so I created and implemented two different algortihms; let's call them RandomizeBruteforceAlgorithm and RandomizeShufflingAlgorithm:
a) RandomizeBruteforceAlgorithm:
This algorithm fills the tiles of the puzzle in random order. More precisely, again let Puzzle be an array holding the sixteen tiles, for each row from top to bottom. At first we fill the array in increasing order, thus Puzzle[0] = 0, Puzzle[1] = 1 ... so we put each tile into the puzzle array. Then we loop over the array and swap randomly two tiles. After this step we have a completely randomized puzzle  but here lies the first disadvantage: The puzzle we get may be solvable or not. If we want explicitely a solvable puzzle, then we have to check the puzzle for solvability after each randomization and repeat the procedure if necessary. This results in the second trap: In theory this algorithm could run forever if each time an unsolvable puzzle is generated. The probability that the puzzle is unsolvable is approximately 1/2 = 50% for one iteration of this algorithm and (1/2)^{n} after n iterations. So e.g. after n = 10 iterations, the probability that still no solvable puzzle is generated is (1/2)^{10} < 0,1% but still possible. Therefore, a maximum number of iterations should be defined after the algorithm aborts in every case. In Pseudocode:
void Randomize_Bruteforce() 
b) RandomizeShufflingAlgorithm:
This algorithm follows another idea. Here we start with the solved puzzle. Then we move the empty space by one position where the direction of the movement is randomly. We repeat this step for a predefined number of movements or until we think the puzzle is 'randomly enough'  I chose the first termination condition as I was to lazy to think about a good metric to classify a puzzle as random or not. This has also the advantage that the algorithm always terminates with a quite balanced execution time. Moreover, the algorithm always produces a solvable puzzle. The drawback of this approach was releaved while testing  for a good 'random' puzzle I suggest at least 100 movements of the empty tile which makes the algorithm slower in average compared to my bruteforce apporach. Here the pseudocode:
void Randomize_Shuffling() 
c) Performance Overview:
Just a short overview of both algorithms on my PC (in average) again 2 million puzzles were generated:
Core2 T5500, 1,66Ghz, 2GB, WinXP X32 
Core i5750, Win7 X64 




RandomizeShufflingAlgorithm (NUM_OF_STEPS = 50) 



RandomizeShufflingAlgorithm (NUM_OF_STEPS = 100) 



RandomizeBruteforceAlgorithm 


References:
[1] 15Puzzle Article at Wikipedia
[2]
www.javaonthebrain.com  15 Puzzle Technical Stuff
[3] www.wikihow.com  SolveaFifteenPuzzle
Sunshine, February 2010
This site is part of Sunshine's Homepage