Università degli Studi di Perugia

LAUREA SPECIALISTICA IN INFORMATICA

Anno Accademico 2007/2008

Programmazione Avanzata

Progetto:

OSudoku

Studenti:

Manfucci Andrea

Ciambelli Davide

1

Introduzione

Sudoku è un gioco di logica nel quale al giocatore o solutore viene proposta una griglia di 9×9

celle, ciascuna delle quali può contenere un numero da 1 a 9, oppure essere vuota; la griglia è suddivisa in 9 righe orizzontali, 9 colonne verticali e, da bordi in neretto, in 9 "sottogriglie", chiamate regioni, di 3×3 celle contigue. Scopo del gioco è quello di riempire le caselle bianche con numeri da 1 a 9, in modo tale che in ogni riga, colonna e regione siano presenti tutte le cifre da 1 a 9 e, pertanto, senza ripetizioni.

Problema

Data una istanza di Sudoku (griglia proposta o matrice incompleta) trasformarla in modo da ottenere

una matrice completa (matrice priva di celle bianche).

Studio della soluzione

Come primo passo andiamo a definire le strutture dati per l'implementazione del programma. Il programma è composto da 6 funzioni principali:

Definzione Matrice: 

let matrice = Array.init 9 (fun _ ­> input_line stdin)

Tipo: val matrice : string array =    [|"520083070"; "308070000"; "170000003";

"060004700"; "403701506"; "001600040"; "600000017"; "000010205"; "010260034"|] 

La scacchiera del Sudoku è rappresentata da un array di stringhe mantenuto in una variabile globale

matrice. Inizialmente il programma legge 9 linee di input composte da 9 caratteri ciascuna per riempire la scacchiera con i valori classici del Sudoku (numeri da 1 a 9). Ad ogni cella vuota corrisponde uno zero.

Definizione Stampa:

let stampa() = Array.iter print_endline matrice;;

Tipo: val stampa : unit ­> unit = <fun> 

Questa è la funzione che permette di visualizzare in output sia la matrice di partenza che quella

risultante. Da notare le parentesi su stampa perchè nonostante sia senza parametri gli viene passato

implicitamente l'array matrice.

2

Definzione Controllo:

let rec controllo ?(i=0) colonna riga n =   i<9 && (matrice.(riga).[i] = n 

|| matrice.(i).[colonna] = n  || matrice.(riga/3*3 + i/3).[colonna/3*3 + i mod 3] = n || controllo ~i:(i+1) colonna riga n);;

Tipo: val controllo : ?i:int ­> int ­> int ­> char ­> bool = <fun> 

Questa è una delle funzioni più importanti del programma perchè verifica se il numero che si vuole inserire nella scacchiera rispetta i vincoli del gioco (relativi all'unicità del numero in questione su

una singola colonna, una singola riga e all'interno della � sottogriglia� 3x3). La funzione controllo

accetta in ingresso due parametri di tipo intero (colonna e riga) e un char n che rappresenta il numero da controllare.

Definizione Ferma:

let rec ferma fx corretto inf sup = if (inf = sup) then corretto else ferma fx (fx corretto inf) (inf+1) sup

Tipo: val ferma : ('a ­> int ­> 'a) ­> 'a ­> int ­> int ­> 'a = <fun> 

La funzione ferma permette l'inserimento di un numero nella scacchiera sostituendo il numero

precedentemente inserito poiché errato. La funzione accetta in input 4 parametri: una funzione fx,

un char che rappresenta il numero al passo precedente, due interi inf ed sup e restituisce il numero corretto da inserire nella scacchiera.

Definizione Cerca:

let rec cerca ?(colonna=0) ?(riga=0) f soluzioni = match colonna, riga with     9, riga ­> cerca ~colonna:0 ~riga:(riga+1) f soluzioni   | 0, 9 ­> f soluzioni   | colonna, riga ­>       if matrice.(riga).[colonna] <> '0' then cerca ~colonna:(colonna+1) ~riga f soluzioni 

else ferma (fun attuale n_intero ­>                 let n_char = Char.chr (n_intero + 48) 

in if controllo colonna riga n_char then attuale else (matrice.(riga).[colonna] <­ n_char; 

                   let back = cerca ~colonna:(colonna+1) ~riga f attuale in matrice.(riga).[colonna] <­ '0'; back)) soluzioni 1 10;;

Tipo: val cerca : ?colonna:int ­> ?riga:int ­> ('a ­> 'a) ­> 'a ­> 'a = <fun> 

3

Cerca è la funzione che esamina tutte le posizioni della scacchiera in successione provando i numeri da 1 a 9 in ogni cella vuota. Verifica tre possibili casi:

● il caso in cui la riga è finita e quindi effettua la ricorsione sulla riga successiva;● il caso in cui la scacchiera è stata visionata completamente e quindi si è trovata una

soluzione;● l'ultimo caso è quello generale in cui riga e colonna hanno dei valori diversi dai precedenti.

Definizione:

let () = Printf.printf "%d soluzione(i)\n" (cerca (fun i ­> stampa(); i+1) 0);;

Quest'ultima funzione è quella relativa alle chiamate di cerca e stampa che mostrano in sostanza tutte le possibili soluzioni del gioco.

Esempio

Il programma da noi realizzato, una volta lanciato, attende in input una griglia del tipo:

520083070

308070000

170000003

060004700

403701506

001600040

600000017

000010205

010260034

dove a celle vuote corrisponde il valore 0. L'output proveniente da questa particolare griglia è il seguente:

526483179

348179652

179526483

265834791

483791526

791652348

652348917

834917265

917265834

Si può notare facilmente che la griglia restituita dal programma è una soluzione corretta del gioco.

4