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 ancora 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.

Per calcolare la complessità di un simile algoritmo supponiamo di avere una griglia con tutte lettere distinte. In questo modo però non contiamo più volte le parole che possono essere formate in modi diversi (questo comunque influisce in maniera minima).

Per prima cosa dobbiamo scegliere una delle 16 celle, questa formerà la prima lettera della nostra parola. Adesso dobbiamo scegliere una cella vicina per continuare. Ogni cella centrale ha 8 vicini, quelle negli angoli 3, mentre quelle negli spigoli 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ù all’aumentare del numero delle lettere. Con questo ragionamento, con parole di al massimo 7 lettere il numero di combinazioni supera già il milione.

Con un semplice algoritmo ricorsivo, sulla falsa riga di quello del solver, possiamo determinare con esattezza il numero di combinazioni della griglia: 12.029.624.

Un simile algoritmo ha pertanto bisogno di circa dodici milioni di lookup al dizionario. L’algoritmo più semplice che calcola solamente il numero di combinazioni viene eseguito in circa 2.5 secondi.

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.

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, possiamo leggere il nostro file del dizionario in maniera sequenziale, confrontando una parola dopo l’altra.

Infatti 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.

Se non fosse già chiaro dalle considerazioni fatte prima, anche osservando il grafico, notiamo che il numero di possibili parole cresce esponenzialmente; ma il vero incremento lo notiamo dalla quinta lettera in poi. 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. Ad esempio, con “xts” è inutile continuare a cercare parole più grandi di quella, non troveremo mai nulla.

Abbiamo bisogno allora di un “hashmap” un po’ più intelligente, alla quale possiamo chiedere anche se esiste, nel dizionario, 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à è molto utilizzato, come ad esempio in information retrieval, nella correzione ortografica del testo o nel word completition.

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 abbastanza ottimizzata dei Trie, risaputi essere onerosi in termini di memoria. Ricordo che esistono comunque strutture dati più efficienti in termini di memoria.

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.

Il secondo, nonostante il suo tempo di calcolo di 150ms, è molto pratico, non è infatti richiesto di memorizzare il dizionario in una qualche struttura dati. Infatti, il tempo richiesto dall’algoritmo che legge anche tutte le parole da un file, è abbastanza simile a quello dove tutte le parole sono già state caricate in memoria. 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. E’ sicuramente consigliato in tutti quei casi dove possiamo far partire il programma, lasciandolo in esecuzione in attesa di risolvere qualcosa. Inoltre, la memoria necessaria per questo algoritmo si può ridurre utilizzando altre strutture dati.