Fifteen | Classic retro game for the Commodore PET Computer (1979)

FIFTEEN is a computer version of the sliding-tile puzzle known as a 15 Puzzle. The goal is to arrange the tiles in ascending numeric order. The controls in this one are perfect and the puzzle plays really smoothly. From any starting position, an optimal solution should require no more than 80 moves. Armed with that information, you have something to aim for.

I did a bit of reading about the generation of 15 Puzzles and learned that half of all randomly-generated starting positions are impossible to solve. I also took a look at the BASIC listing for this program, and it appears that there is logic in place to prevent unsolvable puzzles from being generated (although I didn't trace through in any depth).