1 2 3 4
5 6 7 8
9 10 11 12
13 14 15
is possible
2 1 3 4
5 6 7 8
9 10 11 12
13 14 15
is not.
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.