L’8-puzzle ha un ingombro minimo e una reputazione sproporzionata. Otto tessere quadrate, numerate da 1 a 8, su una griglia 3×3. Una casella è vuota. Il tuo compito: far scorrere le tessere nella casella vuota, una mossa alla volta, finché i numeri non sono in ordine — di solito 1‑2‑3 in alto, 4‑5‑6 al centro, 7‑8‑vuoto in basso.
È il membro più piccolo della famiglia degli N-puzzle. Il 15-puzzle è il cugino più conosciuto, ma l’8-puzzle è il punto di partenza di quasi tutti — bambini, studenti e ricercatori di algoritmi di ricerca.
Come funziona una singola mossa
La casella vuota è l’unica cosa che davvero controlli. Puoi far scorrere solo una tessera che sia direttamente sopra, sotto, a sinistra o a destra della casella vuota. Le mosse diagonali non sono ammesse. Non puoi sollevare le tessere e riposarle altrove. Ogni mossa è una singola tessera vicina che scivola di una casella nel vuoto, e il vuoto va a occupare il posto della tessera.
Questa regola minuscola è ciò che rende interessante il puzzle. Sembra sempre di avere solo una o due mosse utili, eppure una griglia 3×3 nasconde 181.440 disposizioni risolvibili distinte. (L’altra metà — quelle irrisolvibili — è oggetto di una guida separata sulla parità.)
La strategia manuale standard
Il trucco a cui la maggior parte delle persone arriva da sola, e che si estende a 4×4, 5×5 e oltre, è questo:
- Risolvi prima la riga in alto — sistema 1, 2, 3 e non toccarli più.
- Risolvi poi la colonna a sinistra — sistema 4 e 7. Ora la riga in alto e la colonna a sinistra sono bloccate.
- Il 2×2 rimanente — tre tessere e un vuoto — ha esattamente due stati: risolto, oppure con una tessera fuori posto. Se è fuori posto, non puoi sistemarlo lavorando solo nel 2×2 partendo da una posizione risolvibile; devi tornare nel resto del puzzle. (È per questo che la parità conta.)
La parte difficile è piazzare l’ultima tessera di ogni riga o colonna. Per mettere il 3 nell’angolo in alto a destra di solito devi prima far scorrere il 2 nell’angolo, poi portare il 3 sotto di esso, e poi ruotare la coppia in posizione. Questa piccola manovra a "L" è la stessa mossa che userai sul 15-puzzle, sul 24-puzzle e su ogni altra dimensione.
Le soluzioni ottimali sono brevi
L’8-puzzle più difficile possibile si risolve in 31 mosse. Questo vale per tutte le 181.440 posizioni di partenza — la peggiore dista solo 31 scorrimenti dalla soluzione.
Una posizione media richiede circa 22 mosse. Un computer che usa la ricerca A* con una buona euristica trova la risposta ottimale in microsecondi. A mano, chi conosce la strategia della riga in alto risolve qualsiasi 8-puzzle in ben meno di un minuto una volta individuato lo schema.
Perché gli informatici lo amano
L’8-puzzle è il benchmark introduttivo standard per la ricerca euristica. La griglia è abbastanza piccola da poter essere enumerata in modo esaustivo, abbastanza grande da rendere la forza bruta inefficiente, e abbastanza ricca da mostrare la differenza tra due euristiche ben note:
- Tessere fuori posto — contare quante tessere non sono nella loro posizione finale. Economico da calcolare, guida debole.
- Distanza di Manhattan — per ogni tessera, sommare la distanza in righe e in colonne dalla sua destinazione. Guida più forte, sempre economica.
Un’implementazione A* da manuale con la distanza di Manhattan risolve qualsiasi 8-puzzle in microsecondi. Passa al 15-puzzle e servono database di pattern additivi per restare veloci — è un discorso più ampio, e vive nella guida al risolutore del 15-puzzle.
Quando giocare all’8-puzzle
Una griglia 3×3 è un piacere tranquillo. Non ci sono molte mosse a cui pensare, la condizione di vittoria è ovvia, e si completa in un minuto o due. È la dimensione giusta per:
- Un bambino che impara cosa significa "pianificare una mossa in anticipo".
- Un adulto in autobus che non vuole un puzzle lungo tra le mani.
- Un giro di pratica prima di passare al 15-puzzle.
È anche la dimensione che è quasi sempre gratuita nelle app di puzzle scorrevoli, la nostra inclusa — le griglie più grandi tendono a stare dietro a un paywall perché generano sessioni più lunghe, ma il 3×3 è l’onboarding di tutti.
Cosa cambia al 4×4
Tutto ciò che riguarda la strategia rimane uguale. Risolvi la riga in alto, poi la colonna a sinistra, poi ricorri nel 3×3 rimanente. Quello che cambia è il tempo: un 8-puzzle in 30 secondi diventa un 15-puzzle in 5–10 minuti. I numeri peggiorano da lì in poi — le dimensioni 5×5 e 6×6 richiedono pazienza seria.
Se gli 8-puzzle iniziano ad annoiare dopo una settimana, è il segnale per passare al livello successivo.