|A simple algorithm: A
simple way to solve the 15 puzzle is to try to place the block with the
number "1" in its final position. Then, without moving the
"1", place the block numbered "2" in its final
place. Then, without moving the blocks, numbered "1" and
"2", move the "3".... and so on.
If one attempts this, one will find that the first two rows can be organized quite easily.
However, when it comes to the third and fourth row, it is not always possible to move a later block, without moving an earlier block.
For instance, consider this arrangement:
The blocks from 1 though 11 are arranged already. However, we must move them, if we want to get the block numbered "12" to its position.
We arrive at this:
|Notice that though 9 steps are listed, some
steps (e.g. step 2) require moving more than one block.
If we count each block moved as one move, then these 9 steps contain 17 moves.