 |
| Home | Chi sono | Mappa del sito | Contatti |
|
Giochi in PHP: SudokuIn questo paragrafo verrà spiegato come implementare un algoritmo che risolve il famoso gioco del sudoku.Per chi non lo conosce, il gioco consiste in un matrice 9X9 di numeri da completare. La matrice completata deve soddisfare il seguenti criteri: ogni riga e ogni colonna, deve avere tutti i numeri da 1 a 9 senza ripetizioni; inoltre suddividendo la matrice in 9 quadranti 3X3 più piccole, ognuna di queste ultime deve avere tutti i numeri da 1 a 9 senza ripetizioni. La variabile ($matrice) contenente lo schema, è un array di 81 elementi dove gli indici sono impostati nel modo seguente
Inoltre definiamo che una posizione [X, Y] (con X e Y da 0 a 8) di uno schema corrisponda come indice di matrice a [X+Y*9], cioè ad esempio la posizione [3, 4] corrisponde all’indice [39]. La funzione che andremo ad implementare cerca di calcolare tutti gli elementi che rispettano le regole del soduku su una posizione di una data matrice. In pratica prende in ingresso una matrice semi-completa e una posizione (x, y) di una matrice, e restituisce un array di elementi che possono essere inseriti in quella posizione. La funzione calcola questa lista per esclusione, parte quindi con un array contenente tutti gli elementi (da uno a nove), quindi cerca di scartare gli elementi presenti nella riga y, nella colonna x e nel quadrante dove si trova la posizione. Vediamo il codice Vediamo un esempio di come funziona ListaPoss(). Consideriamo il seguente schema
Prendiamo la casella di posizione [1, 0] e calcoliamo gli elementi ammissibili. Inizialmente abbiamo il vettore ($risultato) contenente tutti gli elementi [1, 2, 3, 4, 5, 6, 7, 8, 9]. Nella colonna numero 1 sono presenti gli elementi [6, 1, 2], da cui per esclusione di questi elementi otteniamo il vettore [3, 4, 5, 7, 8, 9]; Nella riga numero 0 abbiamo gli elementi da scartare [5, 6, 1, 9] da cui si ottiene [3, 4, 7, 8]; infine gli elementi presenti nel primo quadrato sono [5, 1, 6, 3] da cui si ottiene come risultato finale l’array ($risultato) composto da [4, 7, 8]. Si osservi che data una posizione vuota (x, y) di una matrice semi-completa, se la funzione ListaPoss() restituisce un solo elemento, allora quest’ultimo può essere inserito nella matrice in quanto rappresenta una scelta obbligata. L’ambiente grafico del gioco permette all’utente di inserire i numeri nella matrice. Di seguito il codice Ovviamente occorre una funzione di verifica dei dati immessi dall’utente. Infine vediamo il controllo del gioco. Risolvere schemi facili Per risolvere degli schemi semplici, è sufficiente implementare una funzione che tenta di aggiornare la matrice cercando per ogni posizione (vuota) l’elemento che può essere inserito. Questa funzione restituisce vero se inserisce almeno un elemento, altrimenti torna falso. Si noti che la funzione array_pop() estrae dal vettore l’unico elemento trovato (in quanto count() restituisce uno). Se come esempio, prendiamo lo schema visto in precedenza, a seguito della chiamata di RisolviFacile() si ottiene il seguente schema e come valore di ritorno si ottiene uno.
Iterando la chiamata alla funzione RisolviFacile() si ottengono gli altri numeri fino ad arrivare alla soluzione dello schema di seguito il codice. Di seguito la soluzione dello schema
Nel caso precedente avevamo uno schema facile, ma con lo schema successivo le cose cambiano.
Con questo schema, la funzione RisolviFacile() non riesce a trovare nessun elemento da inserire e restituisce zero. E necessaria quindi una funzione, che sia in grado di dirci se lo schema è stato risolto. Il meccanismo è molto semplice, e consiste nel determinare se tutte le posizioni sono state risolte. Di seguito il codice. Risolvere schemi difficili Per risolvere uno schema difficile occorre effettuare dei tentativi di risoluzione sulle soluzioni ammissibili. La funzione successiva, per ogni posizione vuota, calcola la lista degli elementi ammissibili, e per ognuno di essi esegue un tentativo di risoluzione. In pratica per ogni tentativo, viene costruita una matrice temporanea $matrice_temp, da cui si cerca di trovare una soluzione, quando se ne trova una, allora abbiamo terminato. Vediamo il sorgente. Conviene richiamare la funzione RisolviDifficile() solo dopo che è già stato tentato il metodo semplice. Di seguito la funzione per risolvere gli schemi difficili. Di seguito la soluzione dello schema
Si noti che in presenza di schemi diabolici, questa funzione non è sufficiente a determinare la soluzione. Risolvere schemi diabolici Uno schema diabolico è lo schema con il più basso numero di elementi, che dà una soluzione unica. Vediamo un esempio di questo schema.
Per la soluzione di questi schemi abbiamo bisogno di algoritmi che tentano le varie combinazioni ricorsivamente. Occorre premettere, che in questo caso, il tempo necessario per effettuare tutti i calcoli, aumenta esponenzialmente, quindi sono necessari diversi accorgimenti per limitare il numero dei calcoli ridondanti. Le funzioni che andremo a implementare rispetto a quelli visti in precedenza sono molto più difficili da comprendere, quindi richiedono una maggiore attenzione. Vediamo alcune osservazioni che sono alla base dell’algoritmo di risoluzione di questi schemi: Per effettuare il primo punto, occorre avere una lista delle posizioni da controllare ordinata in base al numero di combinazioni ammissibili ($lista); per il secondo ed il terzo punto, occorre memorizzare in una matrice, la lista delle combinazioni per ogni casella ($matrice_comb). Un'altra matrice utile ai calcoli è quella che memorizza il numero di combinazioni per ogni posizione ($matrice_pos). Di seguito il codice relativo alla creazione di questi array. Nell’array $matrice_pos, poiché il numero massimo di combinazioni è 9, per i numeri fissi viene indicato con il numero 10. Come vedremo più in avanti con 1 indichiamo che il valore di questa posizione è stato ottenuto mediante i calcoli: distinguere i numeri fissi da quelli calcolati è importante per determinare la validità dello schema calcolato. Di seguito la matrice $matrice_pos relativo allo schema diabolico visto in precedenza.
La funzione successiva serve per aggiornare la matrice ($matrice_comb), a seguito della scelta di posizionare il numero ($numero) nella posizione ($casella). Poiché la matrice $matrice_comb, contiene per ogni posizione, la lista delle suzione ammissibili, allora nel momento che si decide che nella posizione [$x, $y] viene inserito il numero ($numero), allora questo numero deve essere scartato dalle eventuali soluzioni situate nella colonna ($x), riga ($y) e nello stesso quadrante della matrice. Dal controllo vengono esclusi la stessa posizione ($casella), e i numeri fissi. Se in una casella, il numero di combinazioni rimanente è uno allora abbiamo trovato una numero da inserire nella matrice. Se il numero di combinazioni è zero allora la matrice calcolata non è valida. Quest’ultima verifica è importante per scartare il numero ($numero) dalla posizione ($casella). Vediamo di seguito il codice. Prima di spiegare il metodo ricorsivo, vediamo il funzionamento della seguente funzione Riduzione() L’array ($lista) contiene la lista delle posizioni da calcolare, e per ogni posizione, è memorizzato il numero di combinazioni potenzialmente ammissibili. Se in una determinata posizione ($casella) c’è una sola combinazione (cioè $elementi è uguale a uno), allora viene aggiornata la matrice delle combinazioni mediante la funzione vista in precedenza AggiornaComb(). Se a seguito di questo aggiornamento si verifica che la matrice non è valida allora la funzione termina restituendo un numero negativo. Tutte queste posizioni, una volta che vengono utilizzati, vengono anche tolti dall’array ($lista). Si noti che quando si incontra una posizione avente più di una combinazione, il ciclo si ferma e la funzione restituisce il numero di posizioni che sono state utilizzati in AggiornaComb(); è ovvio che prima di chiamare la funzione Riduzione(), l’array deve essere ordinato in base al numero delle combinazioni. Si noti che ad ogni chiamata di AggiornaComb(), vengono ridotte le combinazioni in altre posizioni, quindi se a seguito della chiamata della funzione Riduzione() abbiamo ottenuto alcuni numeri risolti, allora riordinando l’array $lista possiamo tentare di ripetere l’operazione. Di seguito il codice. Si noti che senza un metodo ricorsivo, questo codice ottiene lo stesso risultato del metodo visto in precedenza (RisolviFacile()) per risolvere schemi facili. Per ottenere una ricorsione occorre modificare la funzione Riduzione() in modo da considerare i le posizioni aventi più combinazioni e per ognuno di loro tentare di trovare una soluzione o eventualmente di scartane qualcuna. Per controllare il livello di profondità dell’albero di ricorsione abbiamo anche bisogno della variabile ($livello): se una posizione ($casella) contiene più di un elemento allora in base al livello di profondità, si ottiene una nuova ricorsione oppure la terminazione della funzione. Di seguito la funzione Riduzione() modificata. Si osservi che quando la variabile $livello contiene il valore zero, allora ci si trova nella profondità massima dell’albero di ricorsione (nodo foglia). Se non ci si trova nel nodo foglia, allora per ogni posizione contenente più combinazioni, occorre eseguire un tentativo di ricerca per ogni combinazione, da cui per ognuno di essi: se il tentativo porta ad una matrice non valida, possiamo scartarlo dalla lista delle combinazioni nella matrice ($matrice_comb) e quindi possiamo ricondurlo ad una posizione risolta parzialmente (o totalmente se il numero delle combinazioni rimanti è pari a uno); se il risultato porta a svuotare la lista temporanea ($lista_temp), allora la soluzione trovata può essere considerata quella valida. Il codice successivo mostra come viene impiegata la funzione Riduzione(). In pratica la funzione viene richiamata fino a quando si ottengono delle posizioni risolte. La scelta di tentare con vari livelli di profondità, permette di calcolare velocemente schemi semplici, mentre per schemi diabolici, il tempo perso da un tentativo fallito su una bassa profondità è da considerarsi trascurabile. Si noti che ad ogni tentativo occorre riordinare l’array ($lista). Si noti che la variabile $livello_max viene utilizzato per impedire che schemi con un numero troppo basso di numeri fissi possa generare tempi molto lunghi (il caso peggiore è con uno schema vuoto). Una volta ottenuta la soluzione occorre aggiornare la matrice per la visualizzazione del risultato. La matrice viene aggiornata in base alle combinazioni rimaste nella matrice ($matrice_comb) che in caso di soluzione valida, sono tutte a uno. Possiamo riscrivere la funzione RisolviSudoku() in questo modo. Di seguito la soluzione dello schema diabolico.
Scarica documento e sorgenti  (235 Kb)
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||