Introduzione

Visto che uno tra i temi di interesse del sito è MATLAB e conoscendolo un poco (veramente poco rispetto alle sue potenzialità) ho pensato di inserire nel blog un intero programma con lo scopo di far sorridere chi conosce bene MATLAB e di incuriosire chi lo conosce meno.

La peculiarità del programma in oggetto è di essere ricorsivo (ricorsivo è un programma, o una sua funzione, che richiama se stesso) e questo potrebbe interessare chi sta approfondendo la programmazione per apprendere la tecnica della ricorsione: una tecnica molto utile e sfruttata in tanti linguaggi per risolvere con eleganza ed efficacia problemi complessi.

Darò per scontato che si abbia MATLAB installato, che si sappia gestirne gli script e che si abbia dimestichezza con almeno un linguaggio di programmazione.

Lo spunto per scriverlo nacque diversi anni fa con l'intento di risolvere il gioco SUDOKU che stava imperando su quotidiani e settimanali; addirittura erano nate riviste specializzate e persino libri che ne spiegavano trucchi e metodi risolutivi.

Io non capivo il motivo di tanto successo: ritenevo assurdo perdere tempo a risolvere a mano un gioco che il computer poteva risolvere in pochi secondi. Per scrivere il programma risolutivo ho dovuto, con riluttanza, risolverne qualcuno a mano, ma senza che me ne rendessi conto e con la scusa che dovevo verificare il programma ho continuato a giocarci e ci gioco tutt'ora. E così mi son fatto un'idea del suo successo: penso che incontri il favore del pubblico perché la regola del gioco è semplice e la mente ne svolge il compito quasi in stato ipnotico come avviene giocando a carte o anche guardando la TV, per cui si perde la cognizione del tempo, si dimenticano gli affanni quotidiani ed alla fine ci si sente rilassati.

Prima di analizzare il programma, però, diamo una rapida spiegazione del gioco per chi non dovesse conoscerlo.

Il gioco

Il gioco SUDOKU si basa su una griglia di 9 righe per 9 colonne, divise in 9 riquadri di 9 caselle per un totale di 81. Viene proposto uno schema precompilato con alcuni numeri che assume l’aspetto riportato a titolo di esempio nella seguente figura:

sudoku.jpg

I numeri presenti nello schema iniziale e la loro posizione variano in base al livello di difficoltà: facile, medio, difficile o diabolico. Il giocatore, partendo da tale schema iniziale, deve completarlo riempiendo tutte le caselle vuote con i numeri mancanti seguendo un’unica e semplice regola: ogni riga, ogni colonna ed ogni riquadro di 9 caselle, deve contenere tutti e solo i numeri da 1 a 9 in qualsiasi ordine. Essendo 9 le caselle presenti in ogni entità e 9 i numeri che deve contenere, ne consegue che non vi possono essere numeri doppi al suo interno.

Il programma

Il linguaggio usato con MATLAB è molto simile al C con una sostanziale differenza: in MATLAB qualsiasi variabile è considerata una matrice. Questa particolarità è proprio un punto di forza di MATLAB ed il nostro SUDOKU, guarda caso, è facilmente rappresentabile con una matrice di 9 righe e 9 colonne. Quindi il primo passo consiste nel copiare lo schema proposto da qualche giornale ed inserirlo in MATLAB.

1) Inserimento schema SUDOKU

a=[0 1 3 0 8 5 0 0 6; 
   0 0 0 0 3 1 0 0 0; 
   0 0 7 6 0 0 0 0 0; 
   0 0 6 9 0 0 0 0 3; 
   1 7 0 0 0 0 0 2 5;
   3 0 0 0 0 6 9 0 0;
   0 0 0 0 0 2 4 0 0;
   0 0 0 8 7 0 0 0 0;
   9 0 0 5 6 0 3 1 0];

dove notiamo che al posto delle caselle vuote abbiamo scritto uno zero. Ora la matrice a contiene lo schema di partenza del gioco:

a =
     0     1     3     0     8     5     0     0     6
     0     0     0     0     3     1     0     0     0
     0     0     7     6     0     0     0     0     0
     0     0     6     9     0     0     0     0     3
     1     7     0     0     0     0     0     2     5
     3     0     0     0     0     6     9     0     0
     0     0     0     0     0     2     4     0     0
     0     0     0     8     7     0     0     0     0
     9     0     0     5     6     0     3     1     0

2) Lancio del programma

Scrivere il sequente comando che esegue lo script contenente il programma:

[a,ncall,passi,esci,ab,num]=sudoku(a,0,0)

Le parentesi quadre racchiudono 6 variabili di output (il risultato dell'elaborazione) mentre le tonde racchiudono 3 variabili di input.

3) Variabili di input

Come si nota la prima variabile di input è proprio la matrice "a"; La seconda, valorizzata con zero, rappresenta il numero di chiamate ricorsive "ncall" che alla fine verrà restituito in output; La terza, anch'essa inizializzata a zero e restituita in output col nome "passi", rappresenta il numero di volte che il programma principale viene eseguito e per scrupolo, per evitare eventuali loop, controllo che non superi i 10.000 cicli:

   if passi > 10000 
      fprintf('elaborazione maggiore di 10 mila passi !!!');
      esci=1;
      return
   end

4) Elaborazione

Alla prima esecuzione il programma fa un minimo di controllo formale sulla matrice di input. Poi crea qualche matrice di appoggio e cerca, incrociando righe, colonne e quadranti, se vi sono caselle che possono contenere un unico numero.

Se le trova vi inserisce il numero e ripete la procedura col while principale:

while esci==0    
   passi=passi+1; 
   if passi > 10000 
   . . . . 

Qui l'algoritmo per trovare tali caselle è molto semplice e potrebbe essere implementato per rendere la ricerca più efficiente.

Se non le trova deve procedere a tentativi e qui entra in scena la ricorsione. Mi spiego meglio: ora vi sono caselle che ammettono 2 o più numeri per cui il programma cerca con

[i, n_val_disp, val]=cerca_inc_migliore(X,x);

la casella che ammette il minor numero di possibilità: conviene procedere a tentativi su una casella con sole 2 possibilità in modo da avere il 50% di probabilità di indovinare.

Individuata tale casella il programma non fa altro che richiamare se stesso (ecco la ricorsione) e ripetere tutto. Se ha indovinato, il programma procede, eventualmente con altre ricorsioni, fino al completamento del gioco altrimenti torna indietro e ritenta con l'altro valore.

5) variabili di output

Il programma termina ed emette i risultati:

a =
     2     1     3     4     8     5     7     9     6
     6     9     4     7     3     1     5     8     2
     8     5     7     6     2     9     1     3     4
     5     2     6     9     1     7     8     4     3
     1     7     9     3     4     8     6     2     5
     3     4     8     2     5     6     9     7     1
     7     3     5     1     9     2     4     6     8
     4     6     1     8     7     3     2     5     9
     9     8     2     5     6     4     3     1     7
ncall =
     2
passi =
    53
esci =
     1
ab =
     0     1     3     0     8     5     0     0     6
     0     0     0     0     3     1     0     0     0
     0     0     7     6     0     0     0     0     0
     0     0     6     9     0     0     0     0     3
     1     7     0     0     0     0     0     2     5
     3     0     0     0     0     6     9     0     0
     0     0     0     0     0     2     4     0     0
     0     0     0     8     7     0     0     0     0
     9     0     0     5     6     0     3     1     0
num =
    28

dove:

Conclusioni

Potrei dettagliare meglio il codice ma forse mi sono già dilungato abbastanza. Se qualcuno ha voglia di provarlo non si allarmi se impiega troppo tempo: con schemi complessi il programma dura anche decine di secondi.

Allegati

Ecco il programma, basta salvarlo nella directory work di MATLAB col nome sudoku.m.

function [a,ncall,passi,esci,ab,num]=sudoku(a,ncall,passi)

%    Programma ricorsivo per risolvere il gioco SUDOKU;  
%    Lanciare così: [a,ncall,passi,esci,ab,num]=sudoku(0,0,0) affinchè il pgm richieda l'inserimento del gioco;
%    Lanciare così: [a,ncall,passi,esci,ab,num]=sudoku(a,0,0) se si dispone della matrice iniziale del gioco;

%    input:
%        ncall:    va posto a zero, serve alle chiamate ricorsive per tenerne traccia;
%        passi:    idem a zero, conta i passi elaborativi totali di tutte le ricorsività;
%        a:            matrice 9*9 del gioco con zero al posto delle incognite;
%                    se a è posto a zero allora il programma ne chiede l'inserimento riga per riga;
%        Questi sono due giochi di prova:
%        a=[0 1 3 0 8 5 0 0 6; 0 0 0 0 3 1 0 0 0; 0 0 7 6 0 0 0 0 0; 0 0 6 9 0 0 0 0 3; 1 7 0 0 0 0 0 2 5; 3 0 0 0 0 6 9 0 0; 0 0 0 0 0 2 4 0 0; 0 0 0 8 7 0 0 0 0; 9 0 0 5 6 0 3 1 0 ];
%        a=[0 4 0 0 2 0 0 1 0; 0 0 0 6 0 0 0 2 0; 0 0 8 1 0 0 0 5 4; 0 8 0 0 0 0 0 0 7; 7 0 9 0 0 0 4 0 8; 4 0 0 0 0 0 0 3 0; 8 9 0 0 0 3 1 0 0; 0 6 0 0 0 7 0 0 0; 0 3 0 0 1 0 0 7 0 ];

%    elaborazione:
%    0    inserimento dello schema se manca la matrice a in input e relativo controllo;
%    1    trasformo ogni quadrante 3*3 di a in una riga lunga 9 della matrice Q:
%        servirà per togliere dall'incognita i valori già presenti nel quadrante;
%    2     determino la matrice delle incognite X: 
%        una riga per ogni zero che incontro in a, contenente tutti i valori possibili da 1 a 9;
%    3    tolgo dai valori possibili quelli già presenti: nella riga, nella colonna e nel quadrante(ovvero la riga di Q);
%    4    analizzo la matrice delle incognite X: se una incognita è rimasta senza valori possibili esco dalla routine
%        ricorsiva e torno alla precedente, se ve ne sono, altrimenti finisco e segnalo errore;
%    5    se vi è una incognita con un valore solo la inserisco nella matrice 'a' e ricomincio
%        altrimenti vuol dire che devo forzare una incognita;
%    6    cerco l'incognita con meno valori possibili perchè è più efficiente che prenderne una a caso;
%    7    i valori possibili di questa incognita sono i tentativi a disposizione finiti i quali esco dalla routine ricorsiva
%    8    salvo la matrice 'a' prima della forzatura nel caso che debba cambiare valore
%    9    chiamo la stessa routine passandogli la matrice con il valore forzato: se va bene non deve tornare più,
%        se torna devo cambiare il valore e riprovare.

%    output: 
%        ab            la matrice di partenza
%        a            la matrice completata
%        ncall        il numero di chiamate ricorsive
%        passi        il numero di elaborazioni totale
%        esci        se vale 1 l'elaborazione è corretta
%        num        numero di caselle piene presenti nello schema iniziale

%----------------------------    PROGRAMMA PRINCIPALE  ---------------------------------------
esci=0;    
% passo 0:  viene eseguito solo la prima volta
if ncall==0 & length(a)==1        % se sono alla prima ricorsione e la matrice non è in input, ne chiedo l'inserimento
   [a]=inserisci_schema;
end
if ncall==0                         % se sono alla prima ricorsione, controllo lo schema inserito
   ab=a;
   [esito,num]=controlla_schema(a);
   if esito == 1
       fprintf('schema SUDOKU ERRATO');
      return
   end
end

while esci==0    
   passi=passi+1; 
   if passi > 10000 
      fprintf('elaborazione maggiore di 10 mila passi !!!');
      esci=1;
      return
   end
   % passo 1: ricavo la matrice Q dei quadranti
   [Q]=matrice_Q(a);        
   
   % passo 2: ricavo la matrice delle incognite X contenente tutti i valori da 1 a 9 con la sua lunghezza x
   %          e la matrice P con la posizione delle incognite
   [X,P,x]=matrice_XP(a);
   
   % passo 3: tolgo da X i valori non possibili perchè già presenti
   [X]=elimina_valori(X,P,Q,a);
   
   % passo 4: analizzo X e    controllo che per ogni incognita vi sia almeno un valore possibile
    for i=1:x
       if sum(X(i,:))==0
          fprintf('incognita rimasta senza valori possibili!!!! \n')
          return            % uscita dalla routine principale ricorsiva per tornare alla routine precedente
       end
   end
   
   % passo 5: analizzo X e    se c'è una incognita con un solo vaore possibile la inserisco in a
   [inc_inserite,a]=inserisci(x,X,P,a);
   
   % passi 6, 7, 8, e 9: 
   if x==inc_inserite esci=1; 
    elseif inc_inserite==0     % forza una sostituzione con quella che ha meno valori disponibili
       [i, n_val_disp, val]=cerca_inc_migliore(X,x);
       while n_val_disp > 0
         for j=val
            n_val_disp = n_val_disp - 1;
             for ip=1:9
                 for jp=1:9
                   if P(ip,jp)==i        % ho trovato la posizione in a dell'incognita da forzare
                      af=a;                % forzo la matrice af e mi tengo buona la a per poter tornare indietro
                      af(ip,jp)=j;
                      ncall=ncall+1;
                     %fprintf('call %d    SOSTITUITA LA   %d   CON   %d  \n ', ncall, i, j ) %per eventuale DEBUG
                     %X(i,:) %per eventuale DEBUG
                     [anew, ncall, passi, esci]=sudoku(af, ncall, passi);
                     if esci==1 
                        a=anew;
                        return
                     end
                     %ncall=ncall-1; %per eventuale DEBUG
                      %fprintf('A T T E N Z I O N E    R I E N T R O  alla %d \n ', ncall) %per eventuale DEBUG
                   end
                    end
             end
         end
      end
      if ncall==0  % non dovrebbe mai succedere che la prima routine veda fallire tutte le possibilità su una incognita
         error('tentativi terminati !!!!!!!!!!!!!!!!!!!!!')
      end
      return
   end            
   %x %per eventuale DEBUG
   %pause %per eventuale DEBUG
end            % fine while

return
%----------------------------    FINE PROGRAMMA PRINCIPALE  ---------------------------------------

%----------------------------    SUB ROUTINE CHIAMATE DAL PROGRAMMA PRINCIPALE --------------------

%----------------------------    inserimento della matrice  ---------------------------------------
function [a]=inserisci_schema;
for i=1:9
   ok=0;
   while ok==0
      errore=0;
      msg=sprintf('Inserisci la %da riga : ',i);
      r=input(msg,'s');
      for k=1:9
         if r(k)==' ' r(k)='0'; end
         if r(k)=='0' | r(k)=='1' | r(k)=='2' | r(k)=='3' | r(k)=='4' | r(k)=='5' | r(k)=='6' | r(k)=='7' | r(k)=='8' | r(k)=='9'
            ok=1;
         else
            errore=1;
            disp('errore !!!!!!!!!!!!!! RIPETI e STAI ATTENTO !!')
         end
      end
      if errore==1 ok=0; end
   end
   for j=1:9 
      a(i,j)=sscanf(r(j),'%d');
   end
end
%keyboard %per eventuale DEBUG
return
%----------------------------    controllo formale della matrice appena inserita  ------------------
function [esito,num]=controlla_schema(a);
esito=0;
m=a; 
tipo='delle righe';
[esito,riga,colonna,num]=controlla(m,tipo);
if esito == 0
   m=a'; 
   tipo='delle colonne';
   [esito,riga,colonna,num]=controlla(m,tipo);
end
if esito == 0
   m=matrice_Q(a); 
   tipo='dei quadranti';    
    [esito,riga,colonna,num]=controlla(m,tipo);
end
return
%----------------------------    controllo che vi siano solo i numeri da 1 a 9 senza ripetizioni nella riga   -------
function [esito,riga,colonna,num]=controlla(m,tipo);
num=0;
esito=0;
riga=0;
colonna=0;
for i=1:9
   z=zeros(1,9);
   for j=1:9
      if m(i,j) == 1 | ...
         m(i,j) == 2 | ...
         m(i,j) == 3 | ...
         m(i,j) == 4 | ...
         m(i,j) == 5 | ...
         m(i,j) == 6 | ...
         m(i,j) == 7 | ...
         m(i,j) == 8 | ...
         m(i,j) == 9 
         if z(m(i,j))==0 
            z(m(i,j))=1;
            num=num+1;
         else 
            esito=1; riga=i; colonna=j;
            fprintf('Errore alla riga %d colonna %d nella matrice %s \n', riga, colonna, tipo)
            return
         end
      end
   end
end
return
%----------------------------    matrice Q dei quadranti: trasforma i quadranti in righe ------------
function Q=matrice_Q(a);
k=0;                                % contatore dei quadranti ed indice verticale di Q
Q=zeros(9);
for r=[1 4 7]                    % r è l'inizio di ogni quadrante orizzontale                
   for c=[1 4 7]                % c è l'inizio di ogni quadrante verticale
      k=k+1;
      q=0;                        % indice orizzontale di Q ovvero i 9 elementi del quadrante
      for i=r:r+2
         for j=c:c+2
            q=q+1;
            Q(k,q)=a(i,j);    % creo la riga di Q relativa al quadrante k
         end
      end
   end
end
return
%----------------------------    matrice X delle incognite e P delle posizioni  -----------------
function [X,P,x]=matrice_XP(a);
x=0;                                % indice delle incognite
P=zeros(9);                        % matrice contenente la sequenza delle incognite 
clear X;
for i=1:9
   for j=1:9
       if a(i,j)==0 
         x=x+1; 
         P(i,j)=x;
         X(x,1:9)=[1 2 3 4 5 6 7 8 9]; 
      end
   end
end
return
%-------------    per ogni incognita elimina i valori già presenti nella riga, nella colonna e nel quadrante  ----
function X=elimina_valori(X,P,Q,a);
k=0;                            % indice del quadrante
for r=[1 4 7]                            
   for c=[1 4 7]                
      k=k+1;
      for i=r:r+2
         for j=c:c+2
            if P(i,j)>0                                                    % individuo la posizione i e j dell'incognita
                  for j2=1:9                                                 % scorro la riga i
                     if a(i,j2)~=0 X(P(i,j),a(i,j2))=0; end        % per ogni elemento presente in a, 
                 end                                                        % azzero il corrispondente in X
                 for i2=1:9 
                     if a(i2,j)~=0 X(P(i,j),a(i2,j))=0; end        % idem per la colonna j
               end
               for j2=1:9 
                     if Q(k,j2)~=0 X(P(i,j),Q(k,j2))=0; end        % idem per il quadrante k
                 end
            end   
         end
      end
   end
end
return
%----------------------------    se c'è una incognita con un solo valore possibile la inserisco -------
function [inc_inserite,a]=inserisci(x,X,P,a);
inc_inserite=0;
i=0;
while i < x  & inc_inserite==0 
    i=i+1;
      conta_inc=0;
      for j=1:9
         if X(i,j)>0 
            jrisolta=j;
            conta_inc=conta_inc+1; 
         end
      end
      if conta_inc==1
         for ip=1:9
            for jp=1:9
               if P(ip,jp)==i
                  a(ip,jp)=X(i,jrisolta);
                  inc_inserite=inc_inserite+1;
               end
            end
         end
      end
end
return
%----------------------------    occorre forzare una incognita: scelgo quella con meno valori possibili -------
function [i,n_val_disp,val]=cerca_inc_migliore(X,x);
%    i                rappresenta l'incognita da forzare
%    n_val_disp     contiene il numero di valori possibili attribuibili alla incognita
%    val            vettore dei valori possibili
for i=1:x
   s(i)=0;
   for j=1:9
      if X(i,j)>0
         s(i)=s(i)+1;
      end
   end
end
[n_val_disp,i]=min(s);
k=0;
for j=1:9
   if X(i,j)>0
      k=k+1;
      val(k)=X(i,j);
   end
end
return
%----------------------------    FINE SUBROUTINE  ---------------------------------------

Download

Da qui si può scaricare il file