Articoli tecnici

Insight di MathWorks

Risoluzione del Sudoku con MATLAB


Autore:

  • Cleve Moler, MathWorks

7 minuti di lettura

Riepilogo

  • Il Sudoku può essere risolto in modo programmatico in MATLAB utilizzando un approccio di forza bruta basato sul backtracking ricorsivo.
  • Il puzzle è modellato come un problema di vincoli, in cui i valori candidati vengono valutati in base a regole relative a righe, colonne e sottogriglie.
  • La ricerca ricorsiva viene combinata con euristiche come l'identificazione dei singleton per ridurre lo spazio di ricerca.
  • Esempi che utilizzano griglie più piccole illustrano come la valutazione dei candidati e il backtracking producano soluzioni complete.

Chi risolve i puzzle a mano e i programmi informatici utilizzano tecniche molto diverse per risolvere il Sudoku. Il fascino di risolvere il Sudoku a mano deriva dalla scoperta e dalla padronanza di una miriade di sottili combinazioni e schemi che forniscono indizi sulla soluzione finale. Non è facile programmare un computer per replicare queste capacità umane di riconoscimento di schemi. Per questo motivo, la maggior parte dei programmi per la risoluzione del Sudoku adotta un approccio molto diverso, affidandosi alla capacità pressoché illimitata del computer di eseguire tentativi ed errori in modo esaustivo. Questo è l'approccio che ho utilizzato per il programma MATLAB®.

La sfida del Sudoku

Come probabilmente noto, risolvere un Sudoku consiste nel riempire una griglia 9x9 in modo che ogni riga, colonna e blocco principale 3x3 contenga tutte le cifre da 1 a 9. La griglia iniziale contiene alcune cifre, chiamate indizi. A differenza dei quadrati magici e di altri rompicapo numerici, il Sudoku non richiede alcuna operazione aritmetica; gli elementi di una griglia di Sudoku potrebbero essere lettere dell'alfabeto o qualsiasi altro simbolo.

La Figura 1 mostra una griglia iniziale. Apprezzo particolarmente la simmetria di questo esempio, opera di Gordon Royle dell'Università dell'Australia Occidentale. La Figura 2 mostra la soluzione.

sudoku_fig1_w.gif
Figura 1. Un esempio di puzzle, con gli indizi evidenziati in blu. Questo esempio presenta una simmetria particolarmente gradevole.
sudoku_fig2_w.gif
Figura 2. Il puzzle completato. Le cifre rimanenti sono state inserite in modo che ogni riga, colonna e blocco principale 3x3 contenga le cifre da 1 a 9.

Risoluzione del Sudoku con backtracking ricorsivo

Il nostro programma MATLAB utilizza un solo schema, i singleton, insieme a una tecnica informatica di base, il backtracking ricorsivo.

Per capire come funziona il programma, possiamo usare una griglia più semplice di 4x4 con blocchi di 2x2. Tali puzzle sono chiamati Shidoku invece di Sudoku perché in giapponese “Shi” significa “quattro”.

La Figura 3 mostra il nostro primo puzzle Shidoku. Le figure da 4 a 6 mostrano la sua soluzione. Nella Figura 4, i possibili valori, o candidati, sono rappresentati da cifre piccole. Ad esempio, la seconda riga contiene un “3” e la prima colonna contiene un “1”, quindi i candidati nella posizione (2,1) sono “2” e “4”. Quattro delle celle contengono un solo candidato. Queste celle sono i singleton. Questo primo esempio può essere risolto facilmente inserendo i singleton. Nella Figura 5, abbiamo inserito uno dei singleton e ricalcolato i candidati. Nella Figura 6, abbiamo inserito i restanti singleton così come appaiono per completare la soluzione.

sudoku_fig3_w.gif
Figura 3. Shidoku è una versione di Sudoku su una griglia 4x4.
sudoku_fig4_w.gif
Figura 4. I candidati. I candidati in rosso sono i singleton.
sudoku_fig5_w.gif
Figura 5. Inserimento del singleton “3” e ricalcolo dei candidati.
sudoku_fig6_w.gif
Figura 6. Inserimento dei singleton rimanenti per completare il puzzle.

Un puzzle facile potrebbe essere definito come un puzzle che può essere risolto semplicemente inserendo i singleton. In base a questa definizione, il nostro primo esempio è semplice, ma il successivo non lo è.

L'array di input per il puzzle mostrato nella Figura 7 è generato dall'istruzione MATLAB:

 X = diag(1:4) 
sudoku_fig7_w.gif
Figura 7. shidoku(diag(1:4))

Poiché in questo puzzle non ci sono singleton (Figura 8), utilizzeremo il backtracking ricorsivo. Selezioniamo una delle celle vuote e inseriamo provvisoriamente uno dei suoi candidati. Abbiamo scelto di considerare le celle nell'ordine determinato dall'indicizzazione unidimensionale di MATLAB, X(:), e di provare i candidati in ordine numerico. Quindi inseriamo un “3” nella cella (2,1), creando un nuovo puzzle (Figura 9). Successivamente, richiamiamo il programma in modo ricorsivo.

sudoku_fig8_w.gif
Figura 8. I candidati. Non ci sono singleton.
sudoku_fig9_w.gif
Figura 9. Inserimento provvisorio di un “3” per creare un nuovo puzzle. Quindi si torna indietro (backtracking).

Il nuovo rompicapo è facile; il risultato è mostrato nella Figura 10. Tuttavia, questa soluzione dipende dalle scelte che abbiamo fatto prima della chiamata ricorsiva. Altre scelte potrebbero portare a soluzioni diverse. Per questa semplice condizione iniziale diagonale, esistono due possibili soluzioni, che risultano essere l'una la matrice trasposta dell'altra. Poiché la soluzione non è unica, la griglia nella Figura 7 non è un puzzle valido.

sudoku_fig10_w.gif
Figura 10. La soluzione risultante. Questa soluzione non è unica; la sua trasposta è un'altra soluzione.

Esistenza e unicità

In quanto matematici, cerchiamo di dimostrare che esiste una soluzione a un problema e che tale soluzione è unica. Con il Sudoku, né l'esistenza né l'unicità possono essere facilmente determinate dagli indizi iniziali. Ad esempio, con il puzzle mostrato in Figura 1, se inserissimo un “1”, un “5” o un “7” nella cella (1,1), le condizioni relative a riga, colonna e blocco sarebbero soddisfatte, ma il puzzle risultante non avrebbe soluzione. Sarebbe davvero frustrante se un puzzle del genere comparisse sul giornale.

Il backtracking genera molte configurazioni impossibili. Il nostro programma interrompe la ricorsione quando incontra una cella che non ha candidati. Questi puzzle non hanno soluzione.

L'unicità è una qualità sfuggente. Nella maggior parte delle descrizioni del Sudoku non viene specificato che debba esserci una sola soluzione. Anche in questo caso, sarebbe frustrante scoprire una soluzione diversa da quella proposta. Alcuni dei programmi per la generazione di puzzle presenti su MATLAB Central non verificano l'unicità. L'unico modo che conosco per verificare l'unicità è elencare in modo esaustivo tutte le possibili soluzioni.

L'algoritmo per la risoluzione del Sudoku

Il nostro programma MATLAB si compone di soli quattro passaggi:
1. Inserire tutti i singleton.
2. Uscire se una cella non ha candidati.
3. Inserire un valore provvisorio per una cella vuota.
4. Richiamare il programma in modo ricorsivo.

La funzione interna chiave è candidates. Ogni cella vuota inizia con z = 1:9 e utilizza i valori numerici nella riga, colonna e blocco associati per azzerare gli elementi in z. I valori diversi da zero che rimangono sono i candidati. Ad esempio, si consideri la cella (1,1) nella Figura 1. Iniziamo con

 z = 1 2 3 4 5 6 7 8 9 

I valori nella prima riga cambiano z in

 z = 1 0 0 0 5 6 7 8 9 

Quindi la prima colonna cambia z in

 z = 1 0 0 0 5 0 7 0 9 

Il blocco (1,1) non apporta ulteriori modifiche, quindi i candidati per questa cella sono

 C{1,1} = [1 5 7 9] 

Un rompicapo difficile

Il rompicapo illustrato nella Figura 1 è in realtà molto difficile da risolvere, sia a mano che con il computer. Le figure 11 e 12 sono istantanee del calcolo. Inizialmente non ci sono singleton, quindi il primo passo ricorsivo avviene immediatamente. Proviamo con un “1” nella cella (1,1). La Figura 11 mostra come la prima colonna venga quindi riempita entro il passaggio 22. Ma siamo ancora lontani dalla soluzione. Dopo 3.114 passaggi, la ricorsione inserisce un “5” nella cella (1,1) e, dopo 8.172 passaggi, prova con un “7”.

sudoku_fig11_w.gif
Figura 11. La situazione dopo soli 22 passaggi verso la soluzione della Figura 1. I valori colorati in ciano rappresentano le scelte provvisorie effettuate tramite il backtracking, mentre i valori colorati in verde rappresentano i singleton implicati da tali scelte. Il numero “1” non è la scelta giusta per la cella (1,1). Clicca sull'immagine per visualizzarla ingrandita.
sudoku_fig12_w.gif
Figura 12. Dopo 14.781 passaggi, sembriamo vicini a una soluzione, ma è impossibile continuare perché non ci sono candidati per la cella (1,9). Il “7” è la scelta sbagliata per la cella (1,1). Clicca sull'immagine per visualizzarla ingrandita.

La Figura 12 mostra la situazione dopo 14.781 passaggi. Sembriamo vicini a una soluzione, dato che a 73 delle 81 celle sono stati assegnati dei valori. Ma la prima riga e l'ultima colonna, prese insieme, contengono tutte le cifre da 1 a 9, quindi non ci sono più valori disponibili per la cella (1,9) nell'angolo in alto a destra. L'elenco dei candidati per questa cella è vuoto e la ricorsione termina. Infine, dopo 19.229 passaggi, proviamo con un “9” nella prima cella. Questo “9” è una buona idea perché, meno di 200 passaggi più tardi, al passaggio 19.422, il programma raggiunge la soluzione mostrata nella Figura 2. Si tratta di molti più passaggi rispetto a quelli richiesti dalla maggior parte dei puzzle.

Risoluzione del Sudoku tramite backtracking ricorsivo

function X = sudoku(X) 
% SUDOKU  Solve Sudoku using recursive backtracking. 
%   sudoku(X), expects a 9-by-9 array X. 
 % Fill in all “singletons”. 
 % C is a cell array of candidate vectors for each cell. 
 % s is the first cell, if any, with one candidate. 
 % e is the first cell, if any, with no candidates. 
 [C,s,e] = candidates(X); 
 while ~isempty(s) && isempty(e) 
    X(s) = C{s}; 
    [C,s,e] = candidates(X); 
 end 
 % Return for impossible puzzles. 
 if ~isempty(e) 
    return 
 end 
 % Recursive backtracking. 
 if any(X(:) == 0) 
    Y = X; 
    z = find(X(:) == 0,1);    % The first unfilled cell. 
    for r = [C{z}]            % Iterate over candidates. 
       X = Y; 
       X(z) = r;              % Insert a tentative value. 
       X = sudoku(X);         % Recursive call. 
       if all(X(:) > 0)       % Found a solution. 
          return 
       end 
     end 
   end 
% ------------------------------ 
   function [C,s,e] = candidates(X) 
      C = cell(9,9); 
      tri = @(k) 3*ceil(k/3-1) + (1:3); 
      for j = 1:9 
         for i = 1:9 
            if X(i,j)==0 
               z = 1:9; 
               z(nonzeros(X(i,:))) = 0; 
               z(nonzeros(X(:,j))) = 0; 
               z(nonzeros(X(tri(i),tri(j)))) = 0; 
               C{i,j} = nonzeros(z)’; 
            end 
         end 
      end 
 L = cellfun(@length,C);   % Number of candidates. 
 s = find(X==0 & L==1,1); 
 e = find(X==0 & L==0,1); 
 end % candidates 
end % sudoku

Le origini del Sudoku

Molti ritengono che il Sudoku abbia avuto origine in Giappone. In realtà, si tratta di un'invenzione americana. Apparve per la prima volta, con il nome di Number Place, sulla rivista Dell Puzzle Magazine nel 1979. Nel 1984, un editore giapponese, Nikoli, portò il rompicapo in Giappone e gli diede il nome di Sudoku, che è un acronimo in kanji che significa “i numeri devono essere singoli, non sposati”. Il Times di Londra iniziò a pubblicare il rompicapo nel 2004, e in breve tempo si diffuse negli Stati Uniti e nel resto del mondo.

Pubblicato nel 2009 - 91789v00


Prodotti utilizzati: MATLAB

Informazioni sull'autore

Cleve Moler

Cleve Moler, cofondatore di MathWorks, ha ricoperto il ruolo di Chairman e Chief Scientist. Per quasi vent’anni è stato professore di matematica e informatica presso la University of Michigan, Stanford University e University of New Mexico. È il creatore della prima versione di MATLAB e coautore delle fondamentali librerie di sottoprogrammi scientifici LINPACK ed EISPACK. Ha inoltre collaborato alla stesura di tre libri di testo dedicati ai metodi numerici.

Per saperne di più