Un algoritmo per creare Sudoku?
Da un paio di settimane stò studiando un pò il mondo che contorna questi simpatici puzzles con l’obiettivo di creare un generatore di Sudoku in Ruby.
La prima cosa che ho scoperto è che non è stato ancora dimostrato il numero minimo di cifre che è necessario esporre (cioè visualizzare ‘completate’ all’inizio del puzzle) per garantire al Sudoku una soluzione univoca; al momento sono stati trovati Sudoku validi con 17 cifre esposte.
Ma come si determina quando un Sudoku ha una soluzione univoca?
Il primo articolo che ho trovato in questo senso è una pubblicazione scientifica chiamata Sudoku Squares and Chromatic Polynomials che si ‘limita’ a dimostrare che per garantire una soluzione univoca un Sudoku deve avere, tra le sue celle esposte, almeno 8 delle 9 cifre.
E’ stato inoltre dimostrato che per avere una soluzione univoca un Sudoku deve necessariamente esporre almeno una casella all’interno dell’area illustrata in questa immagine.
Chiaramente queste due dimostrazioni mi aiutano soltanto ad escludere a priori alcuni Sudoku ma non mi danno garanzie ne in un senso ne nell’altro nel caso che il mio puzzle superi le richieste espresse; in questo caso sembra che un buon modo per valutare l’unicità delle soluzioni du un Sudoku sia il DLX ovvero il metodo dei Dancing Links
I Dancing Links:
La tecnica dei Dancing Links è stata inventata da Donald Knuth come metodo risolutivo per l’Algoritimo X da lui stesso inventato. Secondo questa interpretazione il problema posto dai Sudoku viene visto come una serie di vincoli che legano gruppi di possibili valori.
Cerco di spiegarmi: per ogni Sudoku esistono 81 caselle, ognuna delle quali può ospitare 9 cifre (nel senso che sono virtualmente nove le cifre che concorrono ad insediare una casella), quindi possiamo dire che:
R1C1 = {R1C1#1 R1C1#2 R1C1#3 R1C1#4 R1C1#5 R1C1#6 R1C1#7 R1C1#8 R1C1#9 }
R1C2 = {R1C2#1 R1C2#2 R1C2#3 R1C2#4 R1C2#5 R1C2#6 R1C2#7 R1C2#8 R1C2#9 }
...
R9C9 = {R9C9#1 R9C9#2 R9C9#3 R9C9#4 R9C9#5 R9C9#6 R9C9#7 R9C9#8 R9C9#9 }
cioè che per la prima casella in alto a sx ( R1C1: Riga 1 Colonna 1 ) ci sono 9 potenziali valori (marcati come R1C1#1..R1C1#9), lo stesso discorso si può fare per tutte le altre 80 celle ottenendo un numero complessivo di 81(celle) * 9(potenziali valori per cella) = 729 elementi del tipo “RxCy#z.
Ora che abbiamo definito questo primo set di vincoli (bhe, sono vincoli a tutti gli effetti; abbiamo assegnato ad ogni cella un particolare sottoinsieme di valori potenziali) possiamo prendere in considerazione le altre regole sancite da questo gioco:
Per ogni colonna ogni cifra può comparire una sola volta:
Modellizziamo questa regola usando la sintassi precedente ed associando ad ogni coppia (colonna/valore) i valori potenziali che la soddisfano:
C1#1 = {R1C1#1, R2C1#1, R3C1#1, R4C1#1, R5C1#1, R6C1#1, R7C1#1, R8C1#1, R9C1#1}
C1#2 = {R1C1#2, R2C1#2, R3C1#2, R4C1#2, R5C1#2, R6C1#2, R7C1#2, R8C1#2, R9C1#2}
...
C9#9 = {R1C9#9, R2C9#9, R3C9#9, R4C9#9, R5C9#9, R6C9#9, R7C9#9, R8C9#9, R9C9#9}
Anche qui, come nel caso precedente definiamo i valori potenziali che si candidano a soddisfare le coppie colonna/valore.
Per ogni riga una cifra può comparire una sola volta:
Ripetiamo lo stesso ragionamento fatto per le colonne stavolta per le righe:
R1#1 = {R1C1#1, R1C2#1, R1C3#1, R1C4#1, R1C5#1, R1C6#1, R1C7#1, R1C8#1, R1C9#1}
R1#2 = {R1C1#2, R1C2#2, R1C3#2, R1C4#2, R1C5#2, R1C6#2, R1C7#2, R1C8#2, R1C9#2}
...
R9#9 = {R9C1#9, R9C2#9, R9C3#9, R9C4#9, R9C5#9, R9C6#9, R9C7#9, R9C8#9, R9C9#9}
In ognuno dei 9 box 3×3 ogni cifra può comparire una sola volta:
Il ragionamento è di nuovo lo stesso ma questa volta elenchiamo i valori potenziali per ogni coppia (box/valore); chiamiamo il box con la sintassi B1..B9:
B1#1 = {R1C1#1, R1C2#1, R1C3#1, R2C1#1, R2C2#1, R2C3#1, R3C1#1, R3C2#1, R3C3#1}
B1#2 = {R1C1#2, R1C2#2, R1C3#2, R2C1#2, R2C2#2, R2C3#2, R3C1#2, R3C2#2, R3C3#2}
...
B9#9 = {R7C7#9, R7C8#9, R7C9#9, R8C7#9, R8C8#9, R8C9#9, R9C7#9, R9C8#9, R9C9#9}
Conclusioni (per questo episodio):
Se proviamo a fare due conti scopriremo che abbiamo definito 81(cella/valori) + 81(colonna/valore) + 81(riga/valore) + 81(box/valore) = 81 x 4 = 324 vincoli. Ognuno di questi vincoli coinvolge 9 valori potenziali quindi per ogni valore potenziale esistono sempre 4 vincoli.
E’ possibile rappresentare tutti questi vincoli in una matrice che riporti sulle colonne i suddetti vincoli (quindi R1C1..R9C9,C1#1..C9#9,R1#1..R9#9,B1#1..B9#9) e sulle righe tutti i valori potenziali (R1C1#1..R9C9#9). Ad ogni cella di questa matrice si andrà poi ad inserire un 1 nel caso che il vincolo specificato incida sul valore potenziale ed uno zero altrimenti.
Bob Hanson ha creato e pubblicato la matrice completa.
Nel prossimo capitolo (che spero vivamente di postare tra sette giorni) scopriremo come risolvere un Sudoku, e – cosa importante – accertarci che tale soluzione sia univoca, usando la tecnica dei Dancing Links.
Sandro
Tags: Dancing Links, Sudoku