Almost 150 years ago the game 15-puzzle was invented and quickly gain lots of popularity. The rules are quite simple – you start with a board with 15 numbered pieces as in the image below, where the pieces are ordered according to their numbers, except the 14 and 15 pieces which switch positions. Given this board we are allowed to slide into the missing place any one of the pieces next to it, how many times that we want, and we win if we manage to get all the pieces in the right order.

This game became very popular during the 1880 and there was even a cash reward for anyone who can solve it. However, no matter how many people tried, no one could solve it, which is not surprising since it is unsolvable (what is surprising, it that it was proved to be unsolvable in 1879). Indeed – this game has a game invariant which doesn’t change when using legal moves and the initial state (with 14, 15 switched) and the ordered state have different invariants, so it cannot be solved.

In this post we will see, as mathematicians, how to even start thinking about this problem, and eventually get to this game invariant.

Continue reading