In 1948-9 it enjoyed what I suspect was one of several periodic resurgences, and at that time was called the "fifteen-puzzle." I suspect it goes back to Sam Lloyd and the late nineteenth century, and maybe even before then.

Because of odd/even parity considerations (I really don't know the technicalities, but that's what it boils down to), half of the configurations that can be depicted cannot be achieved by sliding the tiles, so there was the "Impossible" configuration,

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

and many others not presented, including Faldage's above. Exchange any two adjacent tiles, though, and the polarity is reversed, and now all the "impossible" configurations are available, but the other family has become entirely impossible without another swap.

There were variations with letters and, later, pictures; the Apple puzzle came as a still-later incarnation. If there are two superficially identical tiles, then "all" arrangements can be done.

With practice and a well-lubricated puzzle, an adept eight-year-old could make any possible arrangement within a minute or less. Not unlike the Rubik's Cube manipulators of thirty years later, less an order of magnitude of difficulty, of course.

Edit: google, under "Sam Lloyd and Fifteen-Puzzle," gives a bunch of hits, including this one

http://www.maths.soton.ac.uk/~gan/MA203/puzzles.html

which I haven't had a chance to play around with yet but seems to explore the 15-Puzzle and others as illustrations of group theory, and which ought to have some more rigorous discussion of impossibility if that's what's wanted. (If not, some of the other sites brought up should.) It also has implementations of various puzzles as Java applets, if that is appealing.