Ci sono due modi per risolvere un 15-puzzle. Uno è il modo che ogni giocatore alla fine scopre — risolvi la riga in alto, poi la colonna a sinistra, poi ricorri. L’altro è il modo in cui lo fanno i computer: una ricerca euristica attraverso milioni di stati, guidata da un’abile stima inferiore di quante mosse rimangano.
Questa guida copre entrambi, all’incirca nell’ordine in cui la maggior parte delle persone li impara.
Il 15-puzzle, in un paragrafo
Una griglia 4×4, quindici tessere numerate, una casella vuota. Fai scorrere le tessere nel vuoto finché i numeri non sono in ordine — da 1 a 15, con il vuoto nell’angolo in basso a destra. La griglia fu inventata da Noyes Chapman nel 1874 e divenne una mania internazionale negli anni 1880 dopo che Sam Loyd offrì 1000 dollari per risolvere una variante irrisolvibile. È fondamentalmente lo stesso puzzle dell’8-puzzle — solo una riga e una colonna più grandi.
Risolverlo a mano: il metodo riga-e-colonna
La tecnica che ogni essere umano alla fine trova è questa:
- Risolvi la riga 1. Sistema 1 e 2. Poi sistema 3 nell’angolo in alto a destra. La manovra a "L" — porta 4 nella posizione di 3, fai scivolare 3 sotto, poi ruota la coppia nell’angolo — è il trucco che rende possibili gli angoli.
- Risolvi la colonna 1. Sistema 5, poi 9, poi 13 nell’angolo in basso a sinistra, usando lo stesso trucco a L dell’angolo.
- Ricorri. Quello che rimane è un sotto-puzzle 3×3 (con la colonna e la riga in basso a destra), che è solo un 8-puzzle che sai già risolvere.
Un giocatore sicuro risolve un 15-puzzle in 3–5 minuti a mano. Un nuovo giocatore può impiegare 20 minuti la prima volta e un terzo di quello alla terza.
Lo stesso metodo si estende a 5×5 e 6×6. La ricorsione finisce sempre su un endgame 3×3.
Risolutore ottimale: A* con distanza di Manhattan
Un computer può fare molto meglio del metodo riga-e-colonna. Specificamente: può trovare la soluzione più breve, che è raramente quella che gioca un essere umano.
Il fatto matematico: il 15-puzzle mediano richiede circa 52 mosse di singola tessera quando risolto in modo ottimale. Il caso peggiore è 80. Il metodo riga-e-colonna usa tipicamente 100–150 mosse sulla stessa griglia.
Per trovare una soluzione ottimale, la ricerca A* tratta ogni stato della griglia come un nodo, ogni mossa come un arco, e chiede: quante mosse fino all’obiettivo, almeno? Il numero minimo di mosse rimanenti è impossibile da calcolare esattamente senza risolvere il puzzle, ma un buon limite inferiore rende A* veloce.
Il limite inferiore classico è la distanza di Manhattan:
Per ogni tessera, somma la distanza in riga più la distanza in colonna dalla sua posizione attuale alla sua posizione obiettivo. (Ignora il vuoto.)
La distanza di Manhattan è ammissibile — non sovrastima mai la distanza reale, perché ogni tessera deve viaggiare almeno quel tanto. Con A* e la distanza di Manhattan, l’8-puzzle si risolve in microsecondi e il 15-puzzle in secondi.
IDA*: il cugino amico della memoria
A* deve ricordare ogni stato esplorato. Per i 15-puzzle, questo si traduce in centinaia di megabyte di RAM per le griglie più difficili. Iterative-deepening A (IDA)** scambia memoria con tempo facendo DFS a profondità limitata con l’euristica, alzando il limite di profondità ad ogni giro.
IDA* è ciò che ogni risolutore di riferimento usa effettivamente per il 15-puzzle. L’articolo di Richard Korf del 1985 lo introdusse proprio per risolvere 15-puzzle in modo ottimale su hardware dei primi anni ’80.
Oltre Manhattan: walking distance e database di pattern
La distanza di Manhattan è veloce ma lasca. Assume che le tessere possano attraversarsi liberamente. Non possono — due tessere nella stessa riga devono fare a turno, il che costa mosse extra.
La walking distance conta queste mosse extra. Precalcola, per ogni coppia di righe, il numero minimo di "scambi di riga" necessari per permutare le tessere nelle righe corrette. Fai lo stesso per le colonne. Somma i due. Il risultato è dimostrabilmente più stretto della distanza di Manhattan — tipicamente circa il 25% più grande, il che significa che A*/IDA* esplora il 25% in meno di nodi.
L’euristica più forte conosciuta per il 15-puzzle è il database di pattern additivo e disgiunto:
- Partiziona le tessere in gruppi disgiunti (una suddivisione comune è 5-5-5 più il vuoto).
- Per ogni gruppo, precalcola, per ogni possibile disposizione delle tessere di quel gruppo sulla griglia, il numero minimo di mosse per mettere quelle tessere nelle loro posizioni obiettivo, ignorando tutte le altre tessere.
- Al momento della ricerca, somma le ricerche per ogni gruppo.
Una partizione 7+8 per il 15-puzzle occupa circa 1 GB di spazio ma permette a IDA* di risolvere qualsiasi 15-puzzle in millisecondi. Per il 24-puzzle (5×5), i database di pattern sono essenzialmente l’unico approccio pratico.
Perché risolvere a mano è di solito più veloce (per un puzzle)
Una breve verifica della realtà: scrivere un’implementazione A*, scegliere un’euristica e aspettare che giri richiede più tempo che prendere un singolo 15-puzzle e risolverlo a mano. La matematica è interessante; la praticità è che chi conosce il metodo riga-e-colonna risolve qualsiasi singola griglia in cinque minuti netti.
La ragione per cui i risolutori contano è l’aggregato: articoli di ricerca che confrontano euristiche su migliaia di istanze casuali, libri di testo di IA che usano il 15-puzzle come benchmark, e app che devono generare puzzle garantiti risolvibili in circa N mosse per la calibrazione della difficoltà.
Ordine di lettura suggerito
Se sei arrivato a questa pagina sperando di scrivere un risolutore, parti da A*/Manhattan, guardalo risolvere qualche 8-puzzle, poi portalo a IDA* per i 15-puzzle. Dopo, la walking distance è un’aggiunta di 100 righe che raddoppia la tua velocità. I database di pattern sono un progetto di un weekend che ti guadagna un altro ordine di grandezza.
Se sei venuto qui sperando di giocare a un 15-puzzle, impara prima il metodo riga-e-colonna, poi leggi perché alcune griglie sono irrisolvibili, poi torna qui per la teoria.