The Game of Fifteen

The game of fifteen is a classic puzzle game created in 1874 by Noyes Palmer Chapman, a postman serving in Canastota, and popularized in 1880 by Samuel Loyd. The game consists of a square-shaped table, usually made of plastic, divided into four rows and four columns (therefore 16 positions), on which 15 square tiles are placed, numbered progressively starting from 1. The tiles can scroll horizontally or vertically, but their displacement is obviously limited by the existence of a single empty space. The aim of the game is to rearrange the tiles after having "shuffled" them randomly (the position to reach is the one with the number 1 in the upper left corner and the other numbers following from left to right and from top to bottom, up to 15 followed by the empty box).

The game of fifteen (often generalized in the nth version) is a classic problem with which heuristic based algorithms are explained. Among the commonly used heuristics for this problem we have the number of badly positioned tiles (whose typical mathematical model is the Hamming distance) and the sum of the Manhattan distances between each tile and its correct position. 

Both heuristics are admissible (i.e. they never overestimate the number of missing moves), therefore they allow to solve the problem in an optimal way for some algorithms like A.

Loyd first described his fifteen puzzle in Sam Loyd's Cyclopaedia of 5000 Puzzles, Tricks and Conundrums, published posthumously in 1914 by his son (also Samuel Loyd). The game was immediately successful, contributing to the fame of its inventor, already a renowned riddler and author of other successful games.

Loyd gave away the sum of one thousand dollars as a prize for those who managed to solve a version of the game starting from a position identical to the final one, but with the numbers 14 and 15 exchanged. 

An award that no one could ever claim since, as the author knew very well, the solution of the game starting from such a configuration is mathematically impossible.

The game of fifteen is now considered a classic solitaire, a so-called harp or puzzle. It has been marketed by many publishing houses and in many variations. Many editions combine the original idea with that of the puzzle, distributing a design on the tiles that reappears correctly only when they have been correctly rearranged. There are also variants with a different number of squares (and therefore of tiles). Many software versions are available for personal computers.