Come usare il risolutore
Lo strumento qui sopra risolve in modo ottimale qualsiasi griglia risolvibile 3×3 o 4×4 — la risposta che restituisce è la sequenza di mosse più breve possibile, non solo una che funziona.
- Premi Modifica e inserisci la tua griglia: numera le tessere come dovrebbero leggersi nel puzzle completato (in alto a sinistra c’è l’1) e mettile dove si trovano adesso. Stai risolvendo un puzzle con immagine — di un gioco, di un’app fotografica, di un giocattolo di legno? Prima numera mentalmente l’immagine finita dall’alto a sinistra al basso a destra.
- Premi Risolvi. L’elenco delle mosse appare all’istante per le griglie 3×3 e in pochi istanti per le 4×4.
- Riproduci le mosse sul tuo puzzle reale, una alla volta.
Se il risolutore dice che la griglia è irrisolvibile, non è un bug — esattamente metà di tutte le disposizioni non può mai essere risolta, e nessuna sequenza di mosse legali potrà sistemarle. Preferisci imparare la tecnica invece di leggere le mosse? Il metodo umano è qui.
Come funziona un risolutore di puzzle scorrevoli — sei algoritmi a confronto
Se stai implementando un risolutore di puzzle scorrevoli e non sei sicuro di quale algoritmo usare, questo articolo ne confronta sei ben noti su velocità, memoria, complessità del codice e la dimensione della griglia che gestiscono comodamente. Le risposte sono diverse per il 3×3, il 4×4 e il 5×5.
1. Ricerca in ampiezza (BFS)
L’algoritmo più stupido corretto. Esplora gli stati livello per livello fino a trovare l’obiettivo.
- Tempo — esponenziale nella profondità della soluzione. Per l’8-puzzle termina in una frazione di secondo. Per il 15-puzzle, non termina prima che il tuo computer esaurisca la RAM.
- Memoria — mantiene in memoria l’intero set di stati visitati. Decine di milioni di stati per i 15-puzzle difficili.
- Complessità del codice — venti righe.
- Verdetto — va bene per il 3×3, inutile oltre.
2. A* con distanza di Manhattan
Il primo vero algoritmo. Stessa struttura di BFS ma gli stati vengono estratti da una coda di priorità ordinata per f = g + h, dove h è l’euristica della distanza di Manhattan.
- Tempo — millisecondi per l’8-puzzle, secondi-minuti per il 15-puzzle.
- Memoria — mantiene ancora tutto l’esplorato in memoria; gestibile per 8, doloroso per 15.
- Complessità del codice — cinquanta righe, per lo più cablaggio della coda di priorità.
- Verdetto — lo strumento giusto per l’8-puzzle. Borderline per il 15.
3. A* con Manhattan + conflitto lineare
Aggiungi 2 mosse all’euristica per ogni coppia di tessere nella stessa riga che sono entrambe nella loro riga obiettivo ma in ordine errato (analogamente per le colonne). Dovranno passarsi, cosa che la distanza di Manhattan non può vedere.
- Tempo — tipicamente 5–15% più veloce di A* con Manhattan semplice.
- Memoria — invariata.
- Complessità del codice — sessanta righe.
- Verdetto — strettamente migliore di A* con Manhattan semplice. Usalo sempre.
4. IDA* con Manhattan + conflitto lineare
A* a profondità iterativa. Fai DFS a profondità limitata usando il costo f come misura di profondità, alzando il limite a ogni iterazione. Scambia memoria con tempo riesplorando.
- Tempo — leggermente più lento per nodo di A* a causa dell’esplorazione ripetuta, ma la minor pressione sulla memoria di solito vince sui 15-puzzle difficili.
- Memoria — O(profondità), non O(stati esplorati). Questa è la vittoria.
- Complessità del codice — ottanta righe (DFS ricorsiva, gestione della soglia).
- Verdetto — lo strumento giusto per il 4×4. Lo standard da Korf 1985.
5. IDA* con walking distance
La walking distance è un’euristica più stretta. Precalcola, per ogni disposizione di tessere proiettata solo sulle righe, il numero minimo di operazioni di scambio di riga per portare ogni tessera nella sua riga corretta. Lo stesso per le colonne. Somma.
Cattura qualcosa che Manhattan perde: tessere nella stessa riga che si "contendono" lo stesso slot.
- Tempo — tipicamente 2× più veloce di Manhattan + conflitto lineare sui 15-puzzle difficili, perché l’euristica è più stretta quindi IDA* pota di più.
- Memoria — aggiunge una piccola tabella precalcolata (~500 KB per un 4×4).
- Complessità del codice — 150 righe. Il precalcolo è BFS su uno spazio degli stati ridotto.
- Verdetto — lo strumento giusto per il 4×4 se hai il budget di ingegneria. Il primo miglioramento non banale.
6. IDA* con database di pattern additivi e disgiunti
L’euristica più forte conosciuta per i puzzle scorrevoli. Partiziona le tessere in gruppi disgiunti (una partizione comune del 15-puzzle è 7+8, o 5+5+5). Precalcola, per ogni gruppo, il costo di permutare le tessere del gruppo nelle loro posizioni obiettivo su tutte le possibili disposizioni di quel gruppo. Al momento della ricerca, consulta il contributo di ogni gruppo e somma.
- Tempo — risolve il 15-puzzle più difficile in millisecondi. Risolve 24-puzzle casuali in secondi.
- Memoria — significativa. Una partizione 7+8 per il 15-puzzle è circa 1 GB. Una partizione 5+5+5+9 per il 24-puzzle è circa 4 GB. La memoria domina l’ingegneria.
- Complessità del codice — 300+ righe. Il passo di precalcolo usa BFS retrograda sullo spazio degli stati del gruppo ed è il grosso del lavoro.
- Verdetto — lo strumento giusto per 5×5 e 6×6. Eccessivo per 3×3.
Raccomandazioni riassuntive
Se stai scrivendo un risolutore oggi:
- Per il 3×3, usa A* con Manhattan + conflitto lineare. Qualsiasi altra cosa è sovra-ingegnerizzazione.
- Per il 4×4, usa IDA* con walking distance. I database di pattern danno vittorie marginali a questa dimensione; la complessità ingegneristica non ne vale la pena.
- Per il 5×5, usa IDA* con database di pattern additivi (5+5+5+9 è standard). Senza DB di pattern andrai in timeout sulle istanze più difficili.
- Per il 6×6 (il 35-puzzle), gli stessi algoritmi possono risolvere istanze casuali, ma i casi più difficili sono ancora domande di ricerca. La maggior parte delle app non ci prova.
E il machine learning?
Una domanda ragionevole nel 2026. Le euristiche con reti neurali sono state studiate almeno dal 2014 e possono produrre euristiche veloci per i puzzle scorrevoli. Il problema è che tipicamente non sono ammissibili — possono sovrastimare, il che significa che l’algoritmo risultante non è più garantito ottimale. Per gli sviluppatori di app che vogliono soluzioni garantite ottimali per la calibrazione della difficoltà, i classici database di pattern restano lo strumento giusto.
Per interesse di ricerca, database di pattern addestrati da una rete neurale producono leggeri speedup sulle istanze più difficili del 15-puzzle. Utili per articoli accademici, marginali per software in produzione.
Cosa va in un’app reale
Un’app mobile in produzione che ha bisogno di un risolutore per generare suggerimenti quasi sempre atterra su:
- IDA* + walking distance per il 4×4.
- IDA* + un piccolo DB di pattern per il 5×5.
- Una chiamata sola-prossima-mossa dal pulsante suggerimento.
- Tutto gira on-device. L’intero risolutore è qualche centinaio di kilobyte di codice più qualche megabyte di tabelle precalcolate.
Quello è lo stack pragmatico giusto per un’app per telefono calmo. Il pulsante suggerimento di Slide Puzzle funziona esattamente così.