Algoritmo del Ruzzle Solver

Con il successo di Ruzzle Solver, molti utenti mi hanno più volte richiesto di pubblicarne il codice sorgente, o semplicemente delle informazioni su come se ne potesse fare uno simile. Altri invece erano particolarmente interessati, visto che avrebbero dovuto fare un progetto simile per un esame universitario.

In questo post cercherò solamente di valutare brevemente alcuni metodi per poter realizzare un algoritmo di questo tipo. Sicuramente scriverò altri articoli che tratteranno di temi più specifici in futuro.

I test che vedrete in seguito sono stati eseguiti con algoritmi scritti in C, ed su un MacBook Pro con processore Intel Core i5 da 2.3 Ghz; altre implementazioni potranno quindi riportare risultati differenti, anche se mi aspetto che il rapporto tra di esse sia identico.

Algoritmi

Il nostro dizionario (consideriamo quello italiano), è composto di circa 600.000 parole. Essendo la nostra matrice fissa a 4×4, in realtà abbiamo una prima osservazione da fare: dal punto di vista asintotico stiamo parlando di un problema O(1). Nonostante questo, non possiamo dire che in qualunque modo lo facciamo vada comunque bene, teoria e pratica sono cose diverse.

Full Enumeration

Supponiamo che questo insieme sia memorizzato su una hashmap. Come sappiamo, questo tipo di struttura dati ci fornisce una funzione lookup che, nel caso medio, richiede tempo O(1). Visto che il nostro dizionario è statico, possiamo anche assumere che la nostra hashmap sia semplicemente un vettore abbastanza grande per contenere tutte le nostre parole, e che la funzione di hash sia perfetta (ovvero iniettiva): in questo modo riusciamo ad avere sempre tempo O(1). Quest’ultima struttura dati in realtà è già nota e viene comunemente chiamata Direct Access Table.

Il primo algoritmo che può venire in mente avendo questo tipo di struttura è quello di cercare tutte le possibili combinazioni presenti nella griglia, e per ognuna di esse vedere se è presente o meno nel dizionario.

Cerchiamo allora di stimare il numero di accessi all’hashmap che vengono fatti con tale algoritmo. Per poter fare ciò supponiamo di avere una griglia con tutte lettere distinte, che risulta essere una buona approssimazione di una matrice che può essere trovata nel gioco.

L’algoritmo comincia scegliendo una delle 16 celle: questa formerà la prima lettera della parola che stiamo analizzando. Adesso l’algoritmo deve scegliere una cella vicina per continuare. Ogni cella centrale ha 8 vicini, quelle negli angoli ne hanno 3, mentre quelle negli spigoli ne hanno 5. In media quindi abbiamo (8*4+5*8+3*4)/16 = 5,25 vicini. Le possibili parole di due lettere che si possono formare sono quindi 16 * 5,25 = 84. Da questo punto in poi ogni vicino ne avrà almeno un’altro già visitato, facendo scendere la nostra media a 4,25. Le possibili parole di tre lettere che si possono formare sono quindi 16*5,25*4,25 = 357. Ovviamente la media del numero dei vicini tenderà a diminuire sempre di più visto che ci saranno sempre più vicini già visitati. Con questo ragionamento, con parole di al massimo 7 lettere, il numero di combinazioni supera già il milione.

Ovviamente fare una stima precisa in maniera analitica è difficile, perché non tenendo conto dei vicini già visitati in maniera precisa i numeri tenderanno a crescere eccessivamente rispetto alla realtà. Tuttavia, con un semplice algoritmo ricorsivo, possiamo determinare con esattezza il numero di combinazioni della griglia: 12.029.624.

Con il grafico possiamo osservare l’andamento esatto del numero di parole possibili. Ogni barra del grafico illustra il numero di parole presenti nella griglia (anche del tutto errate) con al più N lettere, ovvero la grandezza dell’albero di ricerca (fino al livello N) dell’algoritmo ricorsivo. Possiamo osservare come questo cresce prima in maniera esponenziale (come era prevedibile) ed in seguito tale crescita rallenta a causa del numero di vicini visitati che aumenta sempre di più.

Un simile algoritmo ha pertanto bisogno di circa dodici milioni di lookup al dizionario (molti dei quali falliranno). L’algoritmo più semplice, che calcola solamente il numero di combinazioni, viene eseguito in circa 2.5 secondi, sarà ovviamente molto maggiore quello che eseguirà anche le lookup.

Active Dictionary

Visto il numero eccessivo calcolato precedentemente in realtà viene in mente un’altro algoritmo, che capovolge il ruolo del dizionario: da passivo ad attivo.

Supponiamo di avere il nostro dizionario e leggiamo una parola alla volta: per ognuna verifichiamo se è presente o meno nella griglia. Ciò è ragionevole visto che il numero di parole esistenti in un dizionario è di molto minore rispetto al numero di parole (anche non esistenti) che possibile formare nella griglia.

Quest’ultima verifica è in realtà abbastanza veloce. La parola guida la strada escludendo i percorsi sbagliati. Le operazioni da fare sono poi dei semplici confronti tra le lettere della parola in esame e quelle della matrice. Inoltre, in questo caso, non dobbiamo neanche costruire l’hashmap, sprecando tempo e memoria: possiamo leggere il nostro file del dizionario dalla memoria secondaria in maniera sequenziale, confrontando una parola dopo l’altra.

In questo caso, il tempo medio per trovare tutte le parole presenti nella matrice è di 150 millisecondi.

Branch and Bound

Riguardando il primo metodo però osserviamo qualcosa. Se abbiamo costruito la parola “attr”, questa fallirà nel lookup, ma ciò non vuol dire che che dobbiamo arrestare la nostra ricerca, infatti proseguendo nella costruzione di parole più grandi possiamo costruire parole come “attrito” che invece sono parole presenti nel dizionario. Per velocizzare la ricerca, sarebbe utile sapere già dalle prime lettere che la parola non è prefisso di nessuna parola tra quelle presenti nel dizionario, in modo da fermarci in tempo senza analizzare le moltissime parole più lunghe che sappiamo già essere inesistenti. Ad esempio, avendo formato la parola “xts” è inutile continuare a cercare parole più grandi di quella, non ne troveremo mai una corretta.

Abbiamo bisogno allora di un “hashmap” un po’ più intelligente, alla quale possiamo chiedere anche se esiste una parola che inizia per “attr”; ed allo stesso modo che non esiste nessuna parola che inizi per “xts”. Questo tipo di strutture dati in realtà è già molto utilizzato, come ad esempio in information retrieval, nella correzione ortografica del testo o nel word completition. Esempi di queste sono: Trie, e Radix Tree.

Con questo algoritmo ci aspettiamo che il tempo sia molto poco, poiché l’enumerazione delle possibili parole viene rigorosamente guidata, escludendo percorsi sbagliati, ed utilizzando un lookup decisamente veloce. Per testare questo algoritmo, ho implementato una versione utilizzando i Trie, risaputi essere onerosi in termini di memoria. Per ovviare ai problemi di spazio richiesto da questa struttura è comunque possibile utilizzare i Radix Tree.

Questo algoritmo richiede, in media, meno di 1ms per calcolare tutte le parole presenti nella griglia.

Conclusioni

Abbiamo visto tre metodi generali per risolvere questo problema, ognuno con i propri pregi e difetti. Ecco una piccola tabella riassuntiva.

Algoritmo Tempo Tempo
(con costruzione struttura dati)
Memoria Primaria Richiesta
Full Enumeration 2,5sec+ 2,5sec+ ~6MB
Active Dicionary 150ms 170ms ~0MB
Branch and Bound 1ms 300ms ~140MB

Il secondo, nonostante il suo tempo di calcolo di 150ms, è molto pratico, non è infatti richiesto di memorizzare il dizionario in una qualche struttura dati in memoria centrale. La lettura delle parole dal file che si trova in memoria secondaria può anche essere più veloce se si pensa che il sistema operativo può fare caching di tale file. Questo è consigliato in quei casi in cui il programma nasce e muore risolvendo solamente una configurazione.

Il terzo è sicuramente molto più veloce, ma bisogna considerare che è necessaria una fase di popolazione della struttura dati che può essere lunga, e che la memoria necessaria per la sua memorizzazione può essere consistente se non si utilizzano strutture dati come i Radix Tree. E’ sicuramente consigliato in tutti quei casi dove possiamo far partire il programma, lasciandolo in esecuzione in attesa di risolvere qualcosa.

5 commenti su “Algoritmo del Ruzzle Solver

  1. Ciao! Congratulazioni per il lavoro svolto! Mi sono dedicato un pò anchio alla risoluzione di Ruzzle e sono arrivato a preferire quella che indichi come “soluzione 2″, cioè quella di leggere parola per parola ogni volta dal dizionario (uso mark.txt).
    Altra parte interessante del tuo lavoro dal mio punto di vista è quella dell’algoritmo javascript che disegna le parole nella scacchiera!
    All’algoritmo passi solo il piccolo dizionario o altre informazioni? Lasci fare tutto allo script?
    Grazie della eventuale risposta :D
    Alessandro

    • Grazie, all’algoritmo javascript passo solo ed esclusivamente il piccolo dizionario (più una piccola informazione sul tempo che ha impiegato il server a generarle). Ovviamente quando hai a che fare con un servizio che potrebbe generare afflusso notevole di persone bisogna progettare le cose con un certo criterio. Generare le soluzioni lato server, considerando anche i moltiplicatori e generando anche la lista delle mosse per generare i punti ottimali, è una cosa pesante dal punto di vista computazionale; meglio se è direttamente l’utente a fare i calcoli che può fare. Poi anche c’è il discorso della banda: ritornare solamente una lista di parole è la minima quantità di informazioni che al client serve, è sicuramente molto più pesante passare una bella tabella con le parole, e la lista delle mosse, e tutto il resto.

  2. Pingback: Tabella di Hash per indicizzazione dizionario - How To in C

  3. Molto bravo!
    è possibile creare un programma simile per una griglia che abbia numeri invece di lettere?
    mi potresti aiutare?

Lascia un Commento

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *

*