Il programma riesce a risolvere un Sudoku di livello medio. Ovvero uno schema in cui si trova, via via che si inseriscono numeri, celle in cui è possibile inserire un solo numero. L'abile programmatore riuscirà a scrivere le istruzioni per risolvere anche sudoku di livello avanzato, ovvero sudoku in cui in ogni casella vuota ci sono più numeri inseribili, ma solo uno è quello corretto.
Alcune funzioni utili:
bool StampaGriglia()
è una funzione che ritorna un valore logico. Stampa la griglia e calcola la somma dei numeri presenti in ciascuna riga, la somma dei numeri presenti in ciasuna colonna e la somma dei numeri in ogni quadrante. Se nessun totale è diverso da 45 si ritorna il valore true, ad indicare che il gioco è risolto.
void Elimina(int r, int c, int numero)
La funzione non restituisce un valore, riceve tre parametri, che rappresentano la coordinata di riga r, la coordinata di colonna c, e il valore del numero. Questa funzione elimina numero da ciascuna lista dei numeri che si possono inserire nella stessa riga, nella stessa colonna e nello stesso quadrante in cui si trova la casella di coordinate (r, c).
bool compatibile(int r, int c, int numero)
La funzione non restituisce un valore, riceve tre parametri, che rappresentano la coordinata di riga r, la coordinata di colonna c, e il valore del numero. Questa funzione restituisce vero se il numero è lecito nella casella di coordinate (r, c), ovvero se il numero rispetta le regole.
la funzione main
crea l'elenco dei numeri leciti in ciascuna casella della griglia
Legge da un file di testo lo schema da risolvere, e mentre inserisce il numero nella casella della griglia, ne verifica il rispetto delle regole, se il numero è ammesso, lo elimina dall'elenco dei numeri disponibili nelle celle della riga, della colonna e del quadrante.
Stampa la griglia.
inizia un ciclo do, che si ripete se la funzione StampaGriglia ritorna falso
Quando si trova una casella in cui si può inserire un solo numero, lo si inserisce e si ripete il ciclo
Se non si trova nessuna casella, viene chiesto al giocatore di scegliere una casella
fine del ciclo
Scrittura su file dello schema risolto.
Dichiarare, come variabile globale, la matrice:
int Griglia[9][9];
Nel main dichiarare il puntatore al file:
FILE *pf;
Leggere lo schema del sudoku dal file:
pf=fopen("SudokuMedio.txt", "r");
for (Riga=0; Riga<9; Riga++) {
for (Colonna=0; Colonna<9; Colonna++) {
fscanf(pf, "%d", &Griglia[Riga][Colonna]);
...
In questa fase si è interessati a mostrare la griglia sullo schermo,
ma in seguito occorrerà individuare una struttura dati per verificare,
dopo aver letto il numero, che esso sia inseribile nella cella di coordinate
(Riga, Colonna)
e, in caso affermativo, eliminarlo dalla lista dei numeri inseribili nelle
celle della riga, della colonna e del quadrante.
...
}
}
fclose(pf);
Scarica il file di testo con lo schema del sudoku da risolvere (copiare, incollare in un file di testo e salvare con nome: SudokuMedio.txt).
Richiamare una funzione per stampare i numeri letti dal file:
StampaGriglia();
La funzione deve disporre i numeri sullo schermo mostrandoli in una griglia di 9x9 celle, secondo lo schema seguente:
------------------------------ | 4 0 7 | 0 2 9 | 3 0 8 | | 0 0 0 | 1 0 5 | 0 0 0 | | 0 0 9 | 0 7 3 | 6 0 0 | ------------------------------ | 3 2 6 | 0 0 0 | 0 7 0 | | 0 0 5 | 8 0 7 | 2 0 0 | | 0 7 0 | 0 0 0 | 1 9 5 | ------------------------------ | 0 0 1 | 7 6 0 | 4 0 0 | | 0 0 0 | 9 0 2 | 0 0 0 | | 2 0 8 | 3 0 0 | 9 0 7 | ------------------------------
Prima della funzione main e dopo la dichiarazione della variabile globale, dichiarare la funzione StampaGriglia()
Il bordo superiore e il bordo inferiore sono lunghi 30 caratteri e distano 2 spazi dal margine sinistro.
stampare due spazi (margine sinistro) stampare 30 trattini (bordo superiore) Portarsi all'inizio della riga successiva
È stato stampato il bordo superiore della griglia e ci si è preparati per stampare le 9 righe.
Il ciclo per stampare le 9 righe.
Valgono le seguenti osservazioni
Il bordo sinistro dista uno spazio dal margine sinistro.
Ogni cella è larga tre caratteri. Il numero nella cella, quindi, è delimitato da uno spazio prima ed uno spazio dopo.
Ogni tre celle orizzontali viene aggiunto un bordo di separazione
Ogni tre righe si inserisce un bordo di separazione tra i quadranti, che, come i bordi inferiore e superiore, dista 2 spazi dal margine sinistro.
Dalla Riga 0 alla Riga 8 (cioè le righe della matrice Griglia)
Se la Riga è 3 o 6 stampa due spazi seguiti da 30 trattini e vai a capo.
Stampa uno spazio, una linea verticale (|), uno spazio
Per tutte le colonne della matrice (da Colonna 0 a Colonna 8)
Se la Colonna è 3 o 6 stampa una linea verticale (|) seguita da uno spazio
Stampa il valore contenuto nella cella di coordinate (Riga, Colonna) della matrice Griglia.
Stampa due spazi.
Stampa la linea verticale (|), cioè il bordo destro della griglia.
Terminati i due cicli nidificati per la stampa della matrice, stampare il bordo inferiore della griglia:
Andare a capo. stampare 30 trattini.
Nel main, dopo la lettura da file e la chiusura del file, inserire la chiamata alla funzione StampaGriglia. Eseguire il programma per verificare il corretto funzionamento della funzione scritta.
Lo schema è risolto se la somma dei numeri nelle righe, la somma dei numeri nelle colonne e la somma dei numeri nei quadranti è 45.
Questo è uno dei possibili criteri per terminare il programma, quindi occorre apportare questa funzionalità alla funzione.
La stampa dei totali di riga, di colonna e dei quadranti può avvenire in concomitanza con la stampa dei numeri sullo schermo. Se almeno una somma non è 45, il sudoku non è risolto.
Modificare l'intestazione della funzione, affinchè restituisca vero se il sudoku è risolto, falso se almeno un totale è diverso da 45:
bool StampaGriglia()
La stampa che si vuole ottenere deve mettere in evidenza i tre totali, come nel seguente esempio:
------------------------------ | 4 0 7 | 0 2 9 | 3 0 8 | 33 | 0 0 0 | 1 0 5 | 0 0 0 | 6 | 0 0 9 | 0 7 3 | 6 0 0 | 25 ------------------------------ | 3 2 6 | 0 0 0 | 0 7 0 | 18 | 0 0 5 | 8 0 7 | 2 0 0 | 22 | 0 7 0 | 0 0 0 | 1 9 5 | 22 ------------------------------ | 0 0 1 | 7 6 0 | 4 0 0 | 18 | 0 0 0 | 9 0 2 | 0 0 0 | 11 | 2 0 8 | 3 0 0 | 9 0 7 | 29 ------------------------------ 9 9 36 | 28 15 26 | 25 16 20 Riquadro 1: 20 Riquadro 2: 27 Riquadro 3: 17 Riquadro 4: 23 Riquadro 5: 15 Riquadro 6: 24 Riquadro 7: 11 Riquadro 8: 27 Riquadro 9: 20
Dichiarare una variabile logica, una variabile per memorizzare il totale di riga, ogni volta che si termina la stampa di una riga, e due array di 9 elementi per memorizzare i totali di colonna e dei quadranti, da stampare al termine della stampa completa della griglia:
bool fine; int OrSomma, VerSomma[9], Riquadro[9];
Si conviene di inizializzare la variabile logica fine con il valore true, cioè si assume che lo schema sia risolto, poi, basta verificare se almeno un totale è diverso da 45 per modificarla a false. Inoltre bisogna azzerare tutti i totali:
fine = true; // si assume che lo schema sia risolto.
for(r=0; r<9; r++) { // azzeramento dei totali ...
VerSomma[r] = 0; // ... delle colonne
Riquadro[r] = 0; // e dei riquadri
}
Dove calcolare i totali.
Azzerare la variabile OrSomma appena si entra nel ciclo di stampa degli elementi di una riga. All'interno del ciclo di stampa degli elementi in colonna, aggiungere il numero ai tre totali.
Per semplificare si riporta il programma in pseudocodice, evidenziando le linee da aggiungere:
Dalla Riga 0 alla Riga 8 (cioè le righe della matrice Griglia)
OrSomma = 0;
Se la Riga è 3 o 6 stampa due spazi seguiti da 30 trattini e vai a capo.
Stampa uno spazio, una linea verticale (|), uno spazio
Per tutte le colonne della matrice (da Colonna 0 a Colonna 8)
OrSomma += Griglia[Riga][Colonna];
VerSomma[Colonna] += Griglia[Riga][Colonna];
Riquadro[((Colonna/3+1)+(Riga/3*3))-1] += Griglia[Riga][Colonna];
Se la Colonna è 3 o 6 stampa una linea verticale (|) seguita da uno spazio
Stampa il valore contenuto nella cella di coordinate (Riga, Colonna) della matrice Griglia.
Stampa due spazi.
Stampa la linea verticale (|), cioè il bordo destro della griglia. uno spazio e la variabile OrSomma
Se la variabile OrSomma è uguale a 45 assegnare il valore false alla variabile logica fine
La stampa dei totali di colonna e dei totali di quadrante, con il relativo controllo con il valore 45, è lasciata come esercizio.
Allo studente viene chiesto di interpretare la formula seguente:
((Colonna/3+1)+(Riga/3*3))-1
usata per calcolare l'indice del vettore Riquadro.
In questa espressione, le coordinate Riga e Colonna vengono combinate per individuare il numero del quadrante a cui appartiene la cella di coordinate Riga, Colonna
Si noti, infatti, che, mentre Colonna varia da 0 a 8, la divisione tra interi, Colonna/3, varia da 0 a 2, quindi aggiungendo 1 si individuano correttamente i primi tre quadranti. Per ottenere i numeri dei quadranti successivi, si deve tener conto che in ogni riga ci sono 3 quadranti. Anche in questo caso, mentre Riga varia da 0 a 8, il rapporto Riga/3 è un numero che varia da 0 a 2. Questo numero moltiplicato per i 3 quadranti che si trovano su ciascuna riga viene sommato al numero precedente per dare l'indice dell'array Riquadro.
Per ogni cella si vuole mantenere l'elenco dei numeri inseribili, ovvero si vogliono indicare, per ogni cella, come non disponibili i numeri che sono già presenti nella stessa riga, nella stessa colonna o nello stesso riquadro.
Dichiarare, come variabile globale, la seguente matrice tridimensionale:
int Possibili[9][9][10];
per ognuna delle 9x9 celle c'è una lista di 10 elementi, il primo dei quali riporta la quantità di numeri inseribili in quella cella, nei successivi elementi sono scritti quali numeri possono essere usati in quella cella
Nel main, prima di leggere lo schema dal file, bisogna preparare un array Possibili, associato alla griglia, nel quale si inseriranno, per ogni cella, tutti i numeri da 1 a 9:
for (Riga=0; Riga<9; Riga++) {
for (Colonna=0; Colonna<9; Colonna++) {
Possibili[Riga][Colonna][0] = 9; // in questa cella sono inseribili 9 numeri
for (z=1; z<10; z++) Possibili[Riga][Colonna][z] = z; // elenco dei numeri inseribili
}
}
I due array, Griglia e Possibili verranno usati in questo modo: prima di inserire un numero in una casella dell'array Griglia si legge nell'array Possibili se quel numero è lecito. Se il numero non è inseribile l'operazione viene impedita, se il numero è inseribile allora viene marcato come non disponibile in tutte le celle della riga, della colonna e del riquadro.
Per indicare che un numero non è disponibile in una casella, viene rappresentato con il segno negativo nell'array Possibili.
Scrivere una funzione che, riceve come parametri di ingresso le coordinate di una casella ed un numero, e restituisca un valore logico per indicare se quel numero è inseribile nella casella:
bool compatibile(int r, int c, int numero) {
if(Possibili[r][c][numero]<0) return false;
return true;
}
Ritornare al ciclo di lettura dal file di testo. Subito dopo aver letto un numero dal file e averlo inserito in una casella della griglia, verificare se quel numero è inseribile:
if (!compatibile(Riga, Colonna, Griglia[Riga][Colonna]) && Griglia[Riga][Colonna]>0) {
cout << endl << "numero incompatibile in " << Riga << ", " << Colonna;
system("PAUSE");
return 0;
}
Il test si assicura anche che non si tratti del numero 0, usato per indicare una casella vuota.
Se il numero è compatibile in quella casella, e non è lo 0 di una casella vuota, bisogna scriverlo con il segno negativo in tutte le liste dei numeri consentiti nelle celle della riga, della colonna e del quadrante.
A tale scopo si scriverà una funzione che ricevuti come parametri i valori delle coordinate di riga e di colonna e il valore del numero inserito, modificherà, anteponendogli il segno negativo, il numero in tutte le posizioni dell'array Possibili in cui il numero non potrà essere inserito. Quindi, prima di leggere un altro numero dal file richiamare l'apposita funzione:
if (Griglia[Riga][Colonna]!=0) Elimina(Riga, Colonna, Griglia[Riga][Colonna]);
Dopo aver letto tutto lo schema dal file, si passa alla fase risolutiva del gioco. Si scandisce la griglia, casella per casella e, appena si trova una casella in cui è ammesso inserire un solo numero, si inserisce il numero e si continua la scansione.
Se al termine della scansione non si è trovata nessuna casella con un unico numero inseribile, significa che il livello di difficoltà è avanzato e si chiede al giocatore di proporre una casella e un numero da inserirvi.
Nel main, subito dopo l'istruzione di chiamata della funzione fine = StampaGriglia inserire un ciclo:
do {
...
} while (!fine);
La variabile logica, ricevuta come parametro di ritorno della funzione StampaGriglia, indica che tutti i totali di riga, di colonna e di ogni quadrante sono uguali a 45 e pertanto il gioco si ritiene risolto.
Il ciclo scandisce tutte le celle dell'array Possibili e, per ognuna di esse, cerca, contandoli, i numeri inseribili:
Conta=0;
for (Riga=0; Riga<9; Riga++) {
for (Colonna=0; Colonna<9; Colonna++) {
if (Griglia[Riga][Colonna]==0) { // Se la casella è vuota
Stampare quanti numeri sono ammessi in questa cella
(l'informazione è disponibile in Possibili[Riga][Colonna][0]
stamapare anche le coordinate della cella)
Esaminare tutti gli elementi dell'array Possibili: for (k=1; k<=9; k++)
Se si trova un numero positivo stamparlo.
Se si può inserire un solo numero: if(Possibili[Riga][Colonna][0]==1) {
cercarlo,
memorizzarlo nella variabile k
Assegnare alla variabile Conta il valore 1
interrompere il ciclo.
}
}
}
Se si è usciti con il valore Conta==1 interrompere il ciclo do.
}
Il ciclo di scansione dell'array tridimensionale Possibili è terminato. Interrogare la variabile Conta. Se il suo valore è diverso da 1, si chiede al giocatore di proporre le coordinate di una cella ed un numero da inserirvi:
if (Conta!=1) { // se in tutta la griglia non si è trovata una cella con un solo numero ammesso
// si propone un Inserimento manuale.
do {
cout << endl << "inserisci in riga: (-1 per finire) ";
cin >> Riga;
if (Riga==-1) return 0;
cout << endl << "inserisci in colonna: ";
cin >> Colonna;
cout << endl << "numero; ";
cin >> Griglia[Riga][Colonna];
if (!compatibile(Riga, Colonna, Griglia[Riga][Colonna]) && Griglia[Riga][Colonna]>0) {
cout << endl << "numero incompatibile in " << Riga << ", " << Colonna;
}
} while (!compatibile(Riga, Colonna, Griglia[Riga][Colonna]));
Se invece si è trovata una casella in cui si può inserire un solo numero, si procede con l'inserimento:
} else
Griglia[Riga][Colonna] = k;
In ogni caso si annotano le celle in cui quel numero non è inseribile:
Elimina(Riga, Colonna, Griglia[Riga][Colonna]);
Il numero viene stampato, si mostra il nuovo schema della griglia e si ripete un altro ciclo.
cout << "inserito " << Griglia[Riga][Colonna] << " in " << Riga << "," << Colonna << endl;
fine=StampaGriglia(); // si stampa lo schema e si controlla se è risolto
system("PAUSE");
Quando lo schema è risolto, viene memorizzato in un file di testo:
pf=fopen("SudokuRisolto.txt", "w");
for (Riga=0; Riga<9; Riga++) {
for (Colonna=0; Colonna<9; Colonna++)
fprintf(pf, "%d ", Griglia[Riga][Colonna]);
fputc('\n', pf);
}
fclose(pf);
Dopo aver risolto uno schema si può ottenere un nuovo schema valido scambiando tra loro due righe o due colonne le cui celle appartengono ad uno stesso quadrante. Ad esempio si può ottenere un nuovo schema valido scambiando le righe 0 e 1.
Non si ottiene uno schema valido scambiando righe o colonne le cui celle appartengono a quadranti diversi. Ad esempio non è ammesso scambiare la riga 0 con la riga 3.
Dopo lo scambio, per ottenere un nuovo sudoku di livello medio si devono cancellare 40 caselle
In genere la cancellazione si effettua in modo che le celle vuote siano disposte simmetricamente rispetto al centro della griglia.
Per la costruzione del programma si può utilizzare lo stesso programma che risolve il gioco, ma eliminando il ciclo che risolve lo schema. Al suo posto bisogna inserire un procedimento di estrazione di 20 coordinate casuali Riga, Colonna e cancellando sia le caselle in coordinate Riga, Colonna sia quelle in coordinate 8-Riga, 8-Colonna.
Al termine lo schema viene salvato in un file di testo. La sua soluzione può essere verificata tramite il programma risolutore.
Ad esempio, dopo aver letto la griglia dal file, scambiare le prime due righe:
Riga=0;
for(int i=0; i<9; i++) {
tmp = Griglia[Riga][i];
Griglia[Riga][i] = Griglia[Riga+1][i];
Griglia[Riga+1][i] = tmp;
}
A questo punto si generano 20 coppie di numeri casuali compresi tra 0 e 8, verificando che non siano stati già estratti:
for (int i=0; i<20; i++) {
do {
tmp = rand()%81; // si genera un numero casuale tra 0 e 80
Riga = tmp/9; // il quoziente tra il numero e 9 rappresenta la coordinata di riga
Colonna = tmp%9; // il resto della divisione tra il numero e 9 rappresenta la coordinata di colonna
} while (Griglia[Riga][Colonna]==0); // si genera una nuova coppia se le coordinate sono già state estratte
A questo punto bisogna cancellare le due celle una coordinata (Riga, Colonna), l'altra, simmetrica rispetto al centro della matrice, in coordinate (8-Riga, 8-Colonna)
Griglia[Riga][Colonna]=0;
Griglia[8-Riga][8-Colonna]=0;
} // fine del ciclo for
Terminato il ciclo resta da salvare lo schema in un file di testo.
Allo studioso programmatore si chiede di scrivere una procedura che generi tutti gli schemi possibili, tenendo conto degli scambi consentiti, ad esempio è ammesso scambiare tra loro le righe 0 e 1, le righe 0 e 2, le righe 1 e 2, che coprono i primi tre quadranti, poi le righe 3 e 4, le righe 3 e 5 e le righe 4 e 5, che coprono i quadranti centrali, e così via per tutte le righe e le colonne.
Lo studioso programmatore, in particolare, deve individuare una regola per calcolare tutte le coppie di righe e colonne scambiabili e generare i file con i nomi "sudoku1.txt", sudoku2.txt, sudoku3.txt, ecc.