Game of Fifteen, a.k.a. the 15-Puzzle, was very popular 100+ years ago. The game is still found in stores; for example, you can search Amazon for "15 Puzzle" and get it for about 5 dollars.
In the paper Notes on the 15 puzzle (American Journal of Mathematics, 1879, Vol. 2, No. 4, 397-404) W.W. Johnson and W.E. Story showed, via parity argument, that half of the positions in the puzzle are not solvable. The parity argument is accessible even to high school students.