Algoritmo del solver di Sokoban: come la ricerca trova una soluzione
Un algoritmo di Sokoban trasforma il puzzle in una ricerca tra gli stati della tavola. Registra casse, pavimento raggiungibile, spinte legali e posizioni già note.
Questa guida spiega come funziona un solver. Usa la pagina del solver online per inserire una tavola ASCII e ottenere un percorso.
Un solver valuta la tavola come un grafo di stati, non solo come immagine.
Che cosa esplora davvero un risolutore di Sokoban
L’unità utile è normalmente una spinta, non un singolo passo con le frecce. Camminare fra due spinte sposta il giocatore ma non le casse. Il campo diventa quindi un grafo: un nodo è una posizione nota e un arco è una spinta legale con il cammino necessario per arrivare dietro la cassa successiva.
Il grafo è grande perché le spinte non sono sempre reversibili. Bisogna stare sul lato opposto per spostare una cassa e non la si può tirare fuori da un angolo sbagliato. Ogni nodo deve indicare quali caselle contengono casse e quali sono raggiungibili senza spostarle.
Quando tutti gli obiettivi sono occupati, il risolutore segue i collegamenti ai predecessori fino all’inizio e ricostruisce il percorso. La stringa di direzioni può contenere molti passi, ma le decisioni fondamentali sono le spinte che cambiano lo stato.
Come rappresentare lo stato del campo
Il campo ha dati fissi e variabili. Muri e obiettivi vengono letti una sola volta. Cambiano le coordinate delle casse e la regione raggiungibile dal giocatore. Due posizioni del giocatore sono spesso equivalenti se si può passare dall’una all’altra senza attraversare casse. Normalizzarle evita di riempire la coda con posizioni di cammino duplicate.
| Parte dello stato | Informazione registrata | Utilità |
|---|---|---|
| Muri e obiettivi | Geometria fissa | Definisce caselle percorribili e condizione di vittoria. |
| Disposizione delle casse | Una coordinata per cassa | Determina spinte e assegnazioni agli obiettivi possibili. |
| Regione del giocatore | Pavimento raggiungibile senza spingere | Indica da quali lati si può agire sulle casse. |
| Predecessore e azione | Stato precedente e direzione della spinta | Permette di riprodurre il percorso anziché rispondere solo sì o no. |
Una tabella delle trasposizioni, o insieme degli stati visitati, conserva una chiave per stato normalizzato. Esaminare di nuovo la stessa disposizione e la stessa regione raggiungibile non rivela continuazioni nuove. Si usa memoria per guadagnare velocità.
Schema illustrativo: l’ordine delle casse cambia gli stati raggiungibili dopo ogni spinta. L’immagine spiega il concetto e non mostra il codice del risolutore.
Come cresce la frontiera di ricerca
Dopo aver letto uno stato, un riempimento calcola l’area percorribile. Per ogni cassa si verificano quattro direzioni. Una spinta è legale se la destinazione è libera e il giocatore raggiunge la casella opposta. Si crea quindi un nuovo stato con la cassa spostata e si ricalcola la regione accessibile.
L’ordine di ricerca cambia le garanzie. La ricerca in ampiezza esamina prima le sequenze brevi e minimizza le spinte se ogni arco ha lo stesso costo. Quella in profondità segue un ramo e usa meno memoria di frontiera, ma può restare a lungo in un ramo inutile. La ricerca a costo uniforme o A* combina costi ed euristiche; qualità e proprietà della stima determinano il significato del risultato.
- Leggere.Identificare muri, obiettivi, casse e giocatore; rifiutare conteggi errati o simboli non supportati.
- Raggiungere.Segnare le caselle accessibili senza spostare casse.
- Espandere.Generare spinte con caselle di appoggio e destinazione valide.
- Potare e registrare.Saltare duplicati e blocchi evidenti, memorizzando predecessore e spinta.
- Terminare.Fermarsi a obiettivi coperti o segnalare che non è stato trovato un percorso entro il limite.
Non serve conservare ogni cammino separatamente. Dopo una spinta basta una regione raggiungibile normalizzata per generare le spinte successive. Questo rende pratico un piccolo risolutore nel browser.
Perché eliminare i rami bloccati
Senza potatura si spreca tempo in posizioni senza soluzione. La regola più semplice è l’angolo senza obiettivo: una cassa contro due muri perpendicolari non esce più e il ramo si scarta subito. Altri controlli riguardano muri senza obiettivi compatibili, gruppi 2×2 immobili e casse che chiudono corridoi larghi una casella.
Alcuni problemi riguardano l’accesso, non una cassa immobile. Un obiettivo occupato correttamente può bloccare l’unica casella di appoggio per un’altra cassa. Due casse possono ancora scorrere mentre il giocatore non raggiunge il lato necessario per separarle. Questi casi difficili richiedono regole semplici, controllo dei duplicati e un budget finito.
Un blocco d’angolo si riconosce prima di approfondire la ricerca. Perdite d’accesso più sottili richiedono controlli più ampi dello stato.
La potatura deve preservare la correttezza: una regola troppo aggressiva può cancellare una soluzione insolita. I piccoli strumenti dovrebbero descrivere i limiti delle regole, senza presentare ogni mancata soluzione come una prova.
Costo delle spinte, dei passi ed euristiche
La «soluzione più breve» richiede una definizione. Un percorso ottimo nelle spinte minimizza gli spostamenti delle casse; uno ottimo nelle mosse considera anche i passi. I due obiettivi possono contrastare: aggirare una stanza può risparmiare una spinta e mantenere sicura l’assegnazione delle casse. Il risolutore deve scegliere la priorità e dichiararla nel risultato.
Un’euristica stima la distanza dal completamento. Una stima semplice associa casse e obiettivi usando distanze sulla griglia e penalizza le casse intrappolate contro i muri. Muri, appoggi e ordine delle casse complicano però il percorso reale. La stima dà priorità a stati promettenti senza dimostrare una distanza esatta.
Per schemi piccoli conviene mostrare sequenza di mosse, spinte, passi e stati verificati. Così il lettore confronta il risultato con il proprio piano senza scambiarlo per un ottimo non dimostrato.
Seguire uno schema piccolo
In questo esempio con una cassa, # indica un muro, . un obiettivo, $ una cassa e @ il giocatore.
##### # . # # $ # # @ # #####
La regione iniziale comprende la casella del giocatore e il pavimento sotto la cassa. C’è una spinta legale: stare sotto e spingere verso l’obiettivo in alto. Il risolutore registra la nuova coordinata, ricalcola l’accesso e rileva che tutti gli obiettivi sono coperti. Il collegamento al predecessore ricostruisce il cammino necessario seguito da una spinta.
Negli schemi difficili la frontiera contiene più spinte candidate. Un ramo verso un angolo viene potato, mentre uno ancora praticabile resta in coda. È la differenza tra tentativi casuali e una ricerca che ricorda ciò che ha accertato.
Quando il risolutore si ferma o segnala un problema
Il risolutore può fermarsi per vari motivi. Conteggi diversi di casse e obiettivi, simboli non supportati o giocatore assente rendono l’input non valido. Un campo valido può superare limiti sicuri di righe, colonne, casse o stati visitati. Una ricerca limitata può anche esaurire la frontiera senza trovare una soluzione.
Solo l’ultimo caso in una ricerca completa e illimitata giustifica una prova matematica di impossibilità. I piccoli strumenti limitano normalmente il lavoro per mantenere reattiva la pagina. Un avviso invita a ridurre lo schema, cercare blocchi o pianificare a ritroso. Il risolutore di Sokoban associato documenta i limiti per schemi piccoli e restituisce un messaggio chiaro invece di continuare all’infinito.
Chi progetta livelli può verificare un percorso con il risolutore e poi usare prove con persone per controllare che l’idea sia comprensibile. La guida alla progettazione dei livelli di Sokoban descrive questo processo; qui si spiega la ricerca sottostante.
FAQ sull’algoritmo di Sokoban
Che cos’è un algoritmo risolutore di Sokoban?
È una procedura di ricerca che rappresenta casse e giocatore, genera spinte legali, scarta i blocchi noti e ricostruisce un percorso quando tutti gli obiettivi sono occupati.
Il risolutore esamina ogni pressione delle frecce?
Di solito raggruppa i passi in una regione raggiungibile e sviluppa le spinte come archi principali, eliminando molti percorsi a piedi equivalenti.
Perché la potatura dei blocchi accelera la ricerca?
Elimina rami con angoli senza obiettivo, gruppi immobili e corridoi chiusi prima di esplorarne gli stati successivi.
Il primo percorso trovato è il più breve?
Solo se l’ordine di ricerca e il modello dei costi lo garantiscono. Un risolutore limitato può restituire un percorso utile senza dimostrare l’ottimalità delle spinte o delle mosse.
Cosa significa aver raggiunto il limite di ricerca?
Lo strumento ha esaurito il budget di sicurezza prima di dimostrare una soluzione o la sua impossibilità. Prova uno schema più piccolo o verifica manualmente la posizione; il messaggio non dimostra che manchi una soluzione.
Fonti e approfondimenti
Stati e regioni raggiungibili sono confrontati con la guida ai risolutori della wiki di Sokoban. Gli esempi di ordine seguono Algoritmi di ricerca di base per Sokoban. La crescita dello spazio degli stati e le stime di distanza sono trattate nella documentazione del risolutore di Pavel Klavik. Le fonti descrivono Sokoban standard; i limiti di questo strumento provengono dal risolutore Zeek collegato.
Risolvi un piccolo schema e controlla il risultato
Incolla uno schema ASCII nel risolutore del browser, poi torna a collegare la sequenza a stati, spinte e potatura.
Apri il risolutore di Sokoban