Knuth e i dancing links
Nel post precedente cercando di trovare un algoritmo interessante per la generazione di Sudoku mi sono imbattuto nei Dancing Links.
L’algoritmo DLX è stato inventato da Donald Knuth (il pdf originale è disponibile gratuitamente) ed è essenzialmente un’implementazione performante di un algoritmo di backtracking (Algoritmo X).
L’algoritmo X si applica a problemi chiamati ‘Exact Cover Problems’; tali problemi presentano (genericamente) questo enunciato:
Data una matrice di soli ‘0’ e ‘1’ è possibile trovare un sottoinsieme di righe tali che per ogni colonna vi sia uno e uno solo ‘1’ ?
L’approccio dell’algoritmo X per risolvere un problema come questo è il seguente (data una matrice A):
- Se A è vuota il problema è risolto
- Altrimenti scegli una colonna c
- Scegli una riga r, tale che A[r,c] = 1
- Includi r nella soluzione parziale
- Per ogni j che soddisfi A[r,j] = 1
- cancella la colonna j da A
- Per ogni i che soddisfi A[i,j] = 1
- cancella la riga i da A
- Ripeti questo algoritmo iterativamente sulla matrice A così ridotta
Il problema che rende questo algoritmo molto più laborioso di quanto non sembri è il punto 3. Knuth ci spiega infatti che la scelta della riga r determina la solvibilità o meno del problema (cioè se scegliamo la r giusta il problema si risolve, altrimenti no); questo ci costringe a provare iterativamente tutte le r candidate fino a che non troviamo quella giusta (il che equipara l’algoritmo X ad un algoritmo di backtracking).
I Dancing Links aiutano a velocizzare (in termini di esecuzione) l’algoritmo X offrendo una struttura di memorizzazione dati molto intelligente; Supponiamo di memorizzare solo gli ‘1’ della matrice A, e di farlo nel seguente modo:
- Creiamo un’oggetto Nodo che contiene 4 puntatori ad altrettanti oggetti nodi (su,giu,sinistra e destra) e un puntatore ad un oggetto Colonna.
- Creiamo un oggetto Colonna < Nodo con in più alcune informazioni sulla quantità di nodi che contiene (diciamo un campo size).
- Creiamo un’istanza un pò particolare dell’oggetto colonna (diciamo colonna 0) che punti al primo oggetto colonna della nostra matrice.
Il risultato è illustrato egregiamente a pagina 6 del pdf originale di Knuth.
Ma… dove risiede la velocità nell’operare su una struttura simile ? Se pensate ad un classico algoritmo di backtracking ricorderete che la parte più difficile/onerosa da gestire era quella legata al ripristino dello stato del sistema all’istante n (questo avveniva ogni volta che si realizzava che i passaggi n+1..n+k non portavano ad una soluzione).
Con i Dancing Links invece il tutto è leggermente più semplice, pensiamo infatti all’operazione ‘Inserisco un nodo’:
- Prendo x: un nodo da inserire tra i nodi k e m
- k.giu = x
- m.su = x
- x.su = k
- x.giu = m
- (k.colonna (equivalente a m.colonna)).size += 1
In questo breve pseudocodice ho escluso i puntatori destra e sinistra ma ormai il funzionamento dovrebbe essere abbastanza chiaro.
Il tutto in Ruby
Ho appena finito il porting dell’algorimo DLX implementato da Stan Chesnutt nel suo ‘Sudoku Solver’ in linguaggio Ruby, per il momento potete trovare tutti i sorgenti alla mia pagina di GitHub, nel prossimo articolo utilizzeremo quanto creato per sviluppare il risolvi-sudoku, che a sua volta verrà poi utilizzato per il più ambizioso genera-sudoku.
Tags: Algorithm X, Dancing Links, DLX, Knuth, ruby-dlx