Il gioco del 15

Tutti noi da bambini abbiamo giocato a quello che viene comunemente chiamato il gioco del 15. Si tratta di una cornice di legno o plastica di forma quadrata, nella quale vi sono $15$ blocchi quadrati uguali (numerati da $1$ a $15$) che possono scorrere in alto, in basso, a destra e a sinistra utilizzando lo spazio fornito dal quadrato mancante. Lo scopo del gioco è partire da una configurazione in cui i blocchi sono disordinati e arrivare alla configurazione di partenza in cui essi sono numerati consecutivamente e lo spazio vuoto è in basso a destra.

Le origini del rompicapo non sono completamente chiare. Sebbene l’enigmista Sam Loyd (1841-1911) ne reclamò spesso la paternità, sembra che sia stato in realtà inventato da un certo Noyes Palmer Chapman a New York nel 1874. Esso divenne estremamente popolare in America ed Europa a partire dal 1880.

Nel 1889 Loyd offrì un premio di 1000 dollari a chiunque fosse stato in grado di risolvere la configurazione in cui tutti i numeri sono al loro posto, tranne il $14$ e il $15$ che sono scambiati fra loro.

In realtà Loyd era sicuro di non dover sborsare nulla, dato che nel 1879 Johnson e Story avevano completato l’analisi matematica del gioco, scoprendo che un invariante completo che distingue le configurazioni ammissibili da quelle non ammissibili è costituito dalla parità della corrispondente permutazione e dalla taxicab distance (numero di righe più numero di colonne) del quadrato vuoto dal quadrato in basso a destra. Questo segue dal fatto che ogni mossa effettuata cambia contemporaneamente sia la parità della configurazione che la taxicab distance.

Di conseguenza, se lo spazio vuoto si trova in basso a destra, una configurazione è ammissibile se e solo se essa corrisponde ad una permutazione pari di $\{1, \ldots,15\}$. In particolare, la configurazione proposta da Loyd non è ammissibile, dato che corrisponde alla trasposizione $(14 \; 15)$, che è una permutazione dispari. Questo è un esempio tipico in cui un semplice controllo di parità permette di risolvere elegantemente un problema che sembra a prima vista intrattabile senza l'uso della forza bruta (enumerazione di tutte le configurazioni).

La configurazione impossibile di Sam Loyd

Esistono anche versioni del rompicapo con più di $15$ tasselli, e in generale ha senso chiedersi quale sia il massimo numero di mosse necessarie per risolvere una configurazione nel caso con $n^2-1$ tasselli. Al crescere di n questo è un problema NP-difficile.

Nel caso del gioco del $15$, il massimo numero di mosse necessarie è $80$ (vi sono esattamente $17$ configurazioni che richiedono $80$ mosse). Per il gioco con $24$ tasselli, si sa che il numero massimo di mosse è compreso fra $152$ e $208$. Per $35$ o più tasselli, limitare il numero massimo di mosse necessarie è al momento un problema aperto.


Riferimenti:

A. F. Archer: A modern treatment of the 15 puzzle, The American Mathematical Monthly 106 (1999), 793–799.

J. J. Rotman: Advanced Modern Algebra (Second Edition), Chapter I. Graduate Studies in Mathematics 114, American Mathematical Society (2010).