// nome prrogramma : Risolvi Sudoku
// creatore : Davide Zanin - Zani88
// versione : 1.1
// data di creazione : 11-06-06
// ultima modifica : 18-06-06
// Programma che permette la risoluzione di Sudoku anche complessi
//
// il programma è liberamente modificale e pubblicabile a patto che venga
// sempre indicato il mio nome tra i creatori.
// Per problemi, errori o miglioramenti contattami davidezanin@gmail.com
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
// per ora vengono gestiti solo sudoku 9x9 in futuro anche 16x16
#define n 9
// funzione che implementa la GotoXY per compilatori non Borland
// realizzata da cH!cus disponibile anche sul sito http://www.pierotofy.it/
void GotoXY(int x, int y) {
COORD CursorPos = {x, y};
HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleCursorPosition(hConsole, CursorPos);
}
// Funzione che restituisce il puntatore all'area di memoria riservata alla
// matrice nXn di int
int **AllocaMatrice(){
int i,**m;
m = (int **)malloc(n*sizeof(int *));
for( i = 0; i < n; i++)
m[i] = (int *)malloc(n*sizeof(int));
return(m);
}
// funzione che restituisce il numero del primo elemento del riquadro che fà
// parte x
void Riquadro(int *x){
switch (*x){
case 0 : *x = 0;
break;
case 1 : *x = 0;
break;
case 2 : *x = 0;
break;
case 3 : *x = 3;
break;
case 4 : *x = 3;
break;
case 5 : *x = 3;
break;
case 6 : *x = 6;
break;
case 7 : *x = 6;
break;
case 8 : *x = 6;
}
}
// Funzione che restituisce 1 se num non può essere inserito nella posizione
// del sudoku r,c altrimenti restituisce 0
int Esiste(int **S, int num, int r, int c){
int i,j;
// ciclo che controlla se num è presente nella riga r o nella colonna c
for(i = 0; i < n; i++)
if((num == S[r][i])||(num == S[i][c])) return(1);
// r e c vengono modificati in modo da contenere la psizione del primo riquadro
// a cui appartengono
Riquadro(&r);
Riquadro(&c);
// ciclo che controlla se num esiste già nel riquadro corrente
for(i = r; i < r+3; i++)
for(j = c; j < c+3; j++)
if(S[i][j]==num) return(1);
return(0);
}
// Funzione che legge da tastiera un sudoku
int **LeggiSudokuDaTastiera(){
int **S;
int i,j,x,y;
S = AllocaMatrice();
system("CLS");
printf(" Risolvi Sudoku 1.1 by Davide Zanin - Zani88\n\n"); printf("\n Inserisci il Sudoku (0 per lo spazio vuoto)\n\n");
y = 5;
for(i = 0; i < n; i++){
x = 2;
for(j = 0; j< n; j++){
GotoXY(x,y);
S[i][j] = (int)getch()-48;
GotoXY(x,y);
x += 2;
if(((j+1)%3 == 0)&&((j+1) != 9)){
GotoXY(x,y);
x += 2;
}
}
y++;
if(((i+1)%3 == 0)&&((i+1) != 9)){
GotoXY(2,y);
printf("---------------------\n"); y++;
}
}
return(S);
}
// Funzione che legge il sudoku dal file "Archivio.dat" e restituisce il puntatore
// alla matrice appena caricati dal file
int **CaricaSudokuDaFile(){
FILE *Archivio;
int **S,i,j;
char fine[1];
// apertura del file
Archivio = fopen("Archivio.dat","r");
if(Archivio == NULL){
system("CLS");
printf(" Risolvi Sudoku 1.1 by Davide Zanin - Zani88\n\n"); printf("\n Il file Archivio.dat non esiste\n"); printf("\n Premi un tasto per terminare \n ");
getch();
exit(1);
}
// allocazione della matrice
S = AllocaMatrice();
// lettura dei dati dal file
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
fscanf(Archivio,"%d ",&S[i][j]);
}
}
// chiusura del file
fclose(Archivio);
system("CLS");
printf(" Risolvi Sudoku 1.1 by Davide Zanin - Zani88\n\n"); printf("\n Sudoku caricato con successo\n"); printf("\n Premi un tasto per continuare \n ");
getch();
return(S);
}
int **CaricaSudoku(){
char scelta;
int **S;
scelta = 0;
while((scelta != 49)&&(scelta != 50)){
system("CLS");
printf(" Risolvi Sudoku 1.1 by Davide Zanin - Zani88\n\n"); printf("\n 1 - Per caricare il sudoku dal file 'Archivio.dat'\n "); printf("\n 2 - Per inserire il sudoku da tastiera\n"); scelta = getch();
switch (scelta){
case 49 : S = CaricaSudokuDaFile();
break;
case 50 : S = LeggiSudokuDaTastiera(S);
break;
}
}
return(S);
}
// funzione che stampa il sudoku
void StampaSudoku(int **S){
int i,j;
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
if(((j
+1
)%3
== 0
)&&((j
+1
) != 9
)) printf(" |"); }
if(((i
+1
)%3
== 0
)&&((i
+1
) != 9
)) printf(" ---------------------\n"); }
}
// funzione che copia S in S2
void Copia(int **S, int **S2){
int i,j;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
S2[i][j] = S[i][j];
}
// funzione che cerca i numeri che possono essere inseriti alla
// riga r e alla colonna c e li restituisce in vet. Restituisce 0 in caso
// non sia possibile inserire alcun numero
int TrovaNumeri(int **S, int r, int c, int vet[]){
int i,lun;
// variabile che tiene traccia di quanti numeri sono stati trovati
lun = 0;
for(i = 1; i < 10; i++){
if(Esiste(S,i,r,c)==0){
vet[lun] = i;
lun++;
}
}
return(lun);
}
// funzione che salva il sudoku nel file "soluzione.txt"
void SalvaSudoku(int **S){
FILE *file;
int i,j;
char fine[1];
file = fopen("soluzione.txt","w");
for(i = 0; i < n; i++){
for(j = 0; j < n; j++)
fprintf(file," %d",S[i][j]);
fprintf(file,"\n");
}
fclose(file);
}
// funzione che risolve il sudoku
int **RisolviSudoku(int **S){
int **S2,i,j,lun,num[9];
float t0,t1;
int fine;
float azzera;
if(S == NULL){
system("CLS");
printf(" Risolvi Sudoku 1.1 by Davide Zanin - Zani88\n\n"); printf("\n Devi prima caricare un Sudoku\n"); printf("\n Premi un tasto per continuare \n "); getch();
return(NULL);
}
system("CLS");
printf(" Risolvi Sudoku 1.1 by Davide Zanin - Zani88\n\n");
printf("\n Elaborazione in corso...");
// parte il cronometro
t0 = ((float)clock())/CLK_TCK;
// viene allocata la matrice che conterrà la soluzione
S2 = AllocaMatrice();
// S viene copiata in S2
Copia(S,S2);
i = 0;
azzera = 0;
while(i < n){
j = 0;
while(j < n){
if(S2[i][j] == 0){
lun = TrovaNumeri(S2,i,j,num);
// se lun = 0 allora vuol dire che il sudoku generato è sbagliato quindi...
if(lun == 0){
// ...vengono azzerati gli indici del ciclo e S2
i = 0;
j = -1;
Copia(S,S2);
azzera++;
}else S2[i][j] = num[rand() % lun];
}
j++;
}
i++;
}
system("CLS");
printf(" Risolvi Sudoku 1.1 by Davide Zanin - Zani88\n\n"); StampaSudoku(S2);
SalvaSudoku(S2);
// viene fermato il cronometro
t1 = ((float)clock())/CLK_TCK;
printf("\n Tempo per risolvere il sudoku: %3.0f\n", t1
-t0
); printf("\n Numero di Sudoku sbagliati generati: %7.0f\n",azzera
); printf("\n Soluzione salvata nel file soluzione.txt\n"); printf("\n Premi un tasto per continuare \n");
getch();
return(S2);
}
int main(){
int **S,i,j;
int scelta;
// viene inizzializata celta
scelta = 0;
S = NULL;
// viene inizzializato il generatore di numeri casuali
srand(time(NULL));
// il programma termina se si preme 3
while(scelta!=51){
system("CLS");
printf(" Risolvi Sudoku 1.1 by Davide Zanin - Zani88\n\n"); printf("\n 1 - Per caricare un Sudoku\n"); printf("\n 2 - Per risolvere il Sudoku\n"); printf("\n 3 - Per uscire\n"); scelta = getch();
switch (scelta){
case 49 : S = CaricaSudoku();
break;
case 50 : RisolviSudoku(S);
break;
}
}
return 0;
}
