L’8-puzzle è ciò che scrivi per primo, il giorno in cui impari la ricerca euristica. È abbastanza piccolo da far funzionare quasi ogni approccio, abbastanza grande perché gli approcci cattivi siano visibilmente peggiori di quelli buoni. Questo articolo segue la soluzione standard dall’alto verso il basso.
Lo stato
Rappresenta la griglia come un array di nove interi, indicizzati da 0 a 8 in ordine riga-per-riga:
posizioni: indici:
1 2 3 0 1 2
4 5 6 ←→ 3 4 5
7 8 _ 6 7 8
La casella vuota è un valore sentinella — 0 è la scelta abituale. Lo stato obiettivo è [1, 2, 3, 4, 5, 6, 7, 8, 0].
Le mosse
Da una posizione con il vuoto all’indice e, puoi scambiare il vuoto con i suoi vicini ortogonali: e-3 (sopra) se non sei nella riga in alto, e+3 (sotto) se non sei nella riga in basso, e-1 (sinistra) se non sei nella colonna più a sinistra, e+1 (destra) se non sei nella colonna più a destra.
Una funzione neighbors(state) restituisce gli stati (fino a quattro) raggiungibili in una mossa.
L’euristica: distanza di Manhattan
Per ogni tessera (ignora il vuoto), calcola la distanza in riga più la distanza in colonna dalla sua posizione attuale alla sua posizione obiettivo. Somma su tutte le tessere. Quella somma è un limite inferiore sul numero di mosse rimanenti — ogni tessera deve viaggiare almeno quel tanto.
In pseudocodice:
h(state) = sum over tiles t:
abs(row(current) - row(goal)) + abs(col(current) - col(goal))
La distanza di Manhattan è ammissibile (non sovrastima mai) e consistente (soddisfa la disuguaglianza triangolare). Entrambe le proprietà sono importanti per A*.
A* in dodici righe
A* mantiene una coda di priorità di stati, ordinati per f = g + h, dove g è la profondità (mosse finora) e h è la stima euristica delle mosse rimanenti. A ogni iterazione: estrai lo stato con f più basso, espandilo, inserisci i vicini con f aggiornato.
open = priority_queue()
open.push(start, f=h(start))
came_from = {}; g = {start: 0}
while open is not empty:
state = open.pop()
if state == goal: return reconstruct_path(came_from, state)
for n in neighbors(state):
tentative_g = g[state] + 1
if n not in g or tentative_g < g[n]:
g[n] = tentative_g
came_from[n] = state
open.push(n, f=tentative_g + h(n))
Quello è l’intero risolutore. Implementa h, implementa neighbors, e puoi risolvere qualsiasi 8-puzzle.
Prestazioni
A* con distanza di Manhattan risolve qualsiasi 8-puzzle in poche centinaia di microsecondi, espandendo poche centinaia o poche migliaia di stati per le istanze più difficili. Lo spazio degli stati è abbastanza piccolo che A* domina su IDA* a questa dimensione — A* è la scelta giusta per il 3×3, IDA* prende il sopravvento dal 4×4 in poi.
Trabocchetti comuni
Tre cose che sbaglierai al primo tentativo:
Hashing dello stato. Le tuple di Python si hashano bene; gli array di int di Java no. Qualsiasi linguaggio usi, lo stato deve essere hashabile perché i set chiuso/aperto funzionino. Un trucco comune è codificare lo stato di 9 tessere come un singolo intero a 32 bit (4 bit per cella, dato che le celle sono 0..8).
Dimenticare il controllo di parità delle inversioni. Se generi un 8-puzzle casuale rimescolando, metà delle volte il puzzle è irrisolvibile, e A* esplorerà l’intero spazio di 181.440 stati cercando un percorso che non esiste. Aggiungi un rapido controllo di parità prima di eseguire A*, o genera camminando all’indietro dall’obiettivo.
Trattare il vuoto come una tessera nell’euristica. La distanza di Manhattan è sommata solo sulle tessere reali. Includere il vuoto gonfia l’euristica e rompe l’ammissibilità (puoi "sistemare" il vuoto gratis con una mossa).
Oltre Manhattan
Puoi fare meglio di Manhattan sull’8-puzzle, ma non di molto:
- Conflitto lineare — se due tessere nella stessa riga sono entrambe nella loro riga obiettivo ma in ordine errato, avranno bisogno di almeno due mosse extra per passarsi. Aggiungi 2 per conflitto. Migliora Manhattan del 5–15%.
- Database di pattern — precalcola il costo ottimale su sottoinsiemi di tessere. Costo di memoria enorme per un minuscolo guadagno di velocità sull’8-puzzle. Vale la pena per i risolutori del 15-puzzle, non qui.
Per gli 8-puzzle, Manhattan semplice con conflitto lineare è il punto di equilibrio pratico.
Cosa costruire dopo
Se hai scritto un risolutore per l’8-puzzle, le estensioni naturali sono:
- Risolutore del 15-puzzle con IDA* + walking distance. Stesse idee di base, ricerca più profonda. (Guida qui.)
- Risolutore N-puzzle generale con database di pattern. Un progetto da weekend.
- Test di risolvibilità — una funzione di 30 righe che restituisce true se una griglia è raggiungibile dall’obiettivo. Utile per lo sviluppo di app. (Basato sul teorema di parità.)
L’8-puzzle è piccolo. Le tecniche che impari risolvendolo scalano fino in cima.