Un risolutore di puzzle scorrevoli è un programma che, data una qualsiasi posizione di partenza risolvibile, produce in output una sequenza di mosse che porta all’obiettivo. È il tipo di strumento che ha due pubblici: i giocatori che si sono bloccati, e gli sviluppatori che devono spedire un’app di puzzle scorrevoli.
I due pubblici vogliono cose molto diverse.
Perché i giocatori non hanno quasi mai bisogno di un risolutore
Se sei bloccato su un puzzle scorrevole, la soluzione onesta di solito non è "esegui un risolutore". È una di tre cose:
- Impara il metodo riga-e-colonna. La maggior parte dei giocatori che si arrendono sono giocatori che non hanno mai imparato la strategia canonica. (Inizia con l’8-puzzle, poi scala.)
- Verifica che il puzzle sia risolvibile. Se non riesci a trovare una soluzione qualunque cosa tu provi, l’app potrebbe aver generato per errore una griglia irrisolvibile. Velocemente verificabile.
- Usa un suggerimento, non una soluzione completa. La prossima singola mossa è di solito sufficiente a sbloccarti. Le app che offrono suggerimenti (la nostra lo fa, in Premium) di solito calcolano una mossa su richiesta anziché un’intera soluzione.
Una soluzione completa raramente ti insegna qualcosa di utile, perché il risolutore produce una sequenza ottimale — di solito 52 mosse per un 15-puzzle difficile — e guardare 52 mosse ottimali sfrecciare sul telefono non costruisce intuito.
Il suggerimento è l’unità giusta. Se hai bisogno di un suggerimento, non hai bisogno di un risolutore.
Perché gli sviluppatori ne hanno sempre bisogno
Costruire un’app di puzzle scorrevoli significa impegnarsi su diverse promesse:
- Ogni puzzle è risolvibile.
- Ogni puzzle richiede circa un dato numero di mosse (calibrazione della difficoltà).
- Ogni puzzle può produrre un suggerimento su richiesta.
Nessuna di quelle promesse è onesta senza un risolutore che gira in background.
La generazione risolvibile per costruzione può evitare di eseguire un risolutore durante la generazione: cammina all’indietro dallo stato obiettivo applicando mosse valide casuali, e garantisci una posizione di partenza risolvibile. La maggior parte delle app, la nostra inclusa, fa esattamente questo.
La calibrazione della difficoltà vuole che il puzzle sia "interessante" — né banale (una griglia che è già per lo più risolta) né estenuante (una griglia che richiede 60 mosse su un 3×3 per sistemarsi). Il trucco standard è applicare abbastanza mosse all’indietro da atterrare vicino alla distanza ottimale dall’obiettivo — tipicamente 20–30 per un 3×3, 40–60 per un 4×4. Il risolutore verifica la distanza dopo la generazione.
I suggerimenti richiedono un risolutore che possa produrre una buona mossa successiva in qualche centinaio di millisecondi. È più veloce di una soluzione ottimale completa ma richiede comunque un vero lavoro algoritmico.
Quale tipo di risolutore
La scelta dipende dalla dimensione della griglia:
| Griglia | Algoritmo raccomandato | Tempo per risoluzione |
|---|---|---|
| 3×3 | A* + Manhattan | < 1 ms |
| 4×4 | IDA* + walking distance | 10 ms – 1 sec |
| 5×5 | IDA* + DB di pattern 5+5+5+9 | 100 ms – minuti |
| 6×6 | IDA* + DB di pattern più grande | secondi – ore |
Per un 3×3, anche la forza bruta BFS funziona. Al 4×4 serve una vera euristica, e la distanza di Manhattan è lo standard dagli anni ’80. Al 5×5 servono database di pattern. Al 6×6 stai facendo ricerca.
Copriamo i dettagli degli algoritmi nella guida al risolutore del 15-puzzle e nella guida al risolutore dell’8-puzzle. Per un confronto degli algoritmi vedi la pagina risolutore di puzzle scorrevoli.
On-device vs lato server
Le app mobili che spediscono un risolutore hanno due scelte di implementazione: eseguirlo on-device, o chiamare un server.
On-device è la scelta più onesta per un’app che rispetta la privacy. Il risolutore è qualche centinaio di righe di codice, i database di pattern per il 4×4 stanno in pochi megabyte, e un telefono moderno risolve qualsiasi 15-puzzle in ben meno di un secondo. Non c’è ragione di inviare uno stato del puzzle a un server — e non inviarlo è una delle cose che distinguono un gioco per telefono calmo da uno che ha bisogno della telemetria per funzionare.
Lato server è quello che viene usato quando lo sviluppatore vuole tracciare su quali puzzle gli utenti si bloccano, o fare A/B test sulle curve di difficoltà. Sono ragioni di prodotto reali, ma vengono con un costo di privacy e una dipendenza di rete. Le app che non possono risolvere un puzzle offline sono app che non funzioneranno su un aereo.
Slide Puzzle risolve interamente on-device. Il database di pattern per il 4×4 è di circa 6 MB e vive dentro il bundle dell’app. Il pulsante suggerimento lo usa direttamente. Nessuna richiesta lascia il telefono.
Una nota pragmatica
Se sei arrivato qui cercando "un sito risolutore dove incollo la mia griglia e mi dice la risposta" — esistono, e sono di solito risolutori web-based per 8-puzzle. Vanno bene per il 3×3. Per 4×4 e oltre, l’esperienza utente è scomoda: digitare 16 numeri, guardare una sequenza di 50 mosse, cercare di eseguire 50 mosse specifiche su una griglia fisica. Nessuno lo apprezza.
Gli usi realistici di un risolutore di puzzle scorrevoli sono:
- Verificare la tua implementazione nel codice.
- Generare un corpus di griglie di test.
- Dentro un’app, calcolare un suggerimento.
A parte questi, imparare il metodo riga-e-colonna è più veloce.