// code by Salvatore Cerruto
// this code allow to solve sudoku with recursive approach
/* sudolib.h */
typedef enum{FALSE, TRUE} boolean;
FILE *aggancio_file(char nomefile[]);
int get_matrix(FILE *file, int ***matrice, char nomefile[]);
int genera_soluzione(int **matrice, int N, int riga, int colonna);
void stampa_soluzione(int **matrice, int N);
int controlla_sudoku(int **matrice, int N, int riga, int colonna);
/* sudolib.c */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "sudolib.h"
FILE *aggancio_file(char nomefile[])
{
FILE *file=NULL;
file=fopen(nomefile, "r");
return (file);
}
int get_matrix(FILE *file, int ***matrice, char nomefile[])
{
int temp, item=0, riga, colonna;
while(fscanf(file, "%d", &temp)!=EOF)
item++;
fclose(file);
file=aggancio_file(nomefile);
if(file!=NULL)
{
/** allocazione righe **/
*matrice=(int **) malloc(sqrt(item)*sizeof(int *));
for(riga=0; riga<sqrt(item); riga++)
{
/** allocazione colonne e scansione file **/
(*matrice)[riga]=(int *) malloc(sqrt(item)*sizeof(int));
for(colonna=0; colonna<sqrt(item); colonna++)
fscanf(file, "%d", &(*matrice)[riga][colonna]);
}
}
/** restituisco la dimensione della matrice **/
return (sqrt(item));
}
int controlla_sudoku(int **matrice, int N, int riga, int colonna)
{
/** is e js sono gli indici usati per evidenziare le sottomatrici **/
int i, j, is, js, k=floor(sqrt(N));
/** controllo che non ci siano elementi uguali sulla colonna **/
for(i=0; i<N; i++)
if((matrice[i][colonna]==matrice[riga][colonna])&&(i!=riga))
return 0;
/** controllo che non ci siano elementi uguali sulla riga **/
for(j=0; j<N; j++)
if((matrice[riga][j]==matrice[riga][colonna])&&(j!=colonna))
return 0;
/** controllo della sottomatrice corrente **/
is=(riga/k)*k;
js=(colonna/k)*k;
for(i=is; i<is+k; i++)
for(j=js; j<js+k; j++)
{
if((matrice[i][j]==matrice[riga][colonna])&&(i!=riga||j!=colonna))
return 0;
}
return 1;
}
int genera_soluzione(int **matrice, int N, int riga, int colonna)
{
int k;
if(riga>=N)
return 1;
/* se la casella è già presente deve saltarla */
if(matrice[riga][colonna]!=0)
{
if(colonna==N-1)
return genera_soluzione(matrice, N, riga+1, 0);
else
return genera_soluzione(matrice, N, riga, colonna+1);
}
for(k=1; k<=N; k++)
{
matrice[riga][colonna]=k;
/**system("cls");
stampa_soluzione(matrice, N);**/
if(controlla_sudoku(matrice, N, riga, colonna))
{
if(colonna==N-1)
{
if(genera_soluzione(matrice, N, riga+1, 0))
return 1;
}
else
{
if(genera_soluzione(matrice, N, riga, colonna+1))
return 1;
}
}
matrice[riga][colonna]=0;
}
return 0;
}
void stampa_soluzione(int **matrice, int N)
{
int i, j, k, cont_c=0, cont_r=0;
printf("+");
for(i=0; i<2*N+sqrt(N)-1; i++)
printf("-");
printf("+");
for(i=0; i<N; i++)
{
printf("\n|");
for(j=0; j<N; j++)
{
printf("%d ", matrice[i][j]);
cont_c++;
if(cont_c==sqrt(N)&&i!=N)
{
printf("|");
cont_c=0;
}
}
cont_r++;
if(cont_r==sqrt(N))
{
printf("\n+");
for(k=0; k<2*N+sqrt(N)-1; k++)
printf("-");
printf("+");
cont_r=0;
}
}
printf("\n");
return;
}
/* main.c */
#include <stdio.h>
#include <stdlib.h>
#include "sudolib.h"
#define MAX 20
int main()
{
int **matrice, N;
char nomefile[MAX];
FILE *filein;
printf("***** Sudoku *****\n");
printf("Inserire il nome del file schema: ");
scanf("%s", nomefile);
filein=aggancio_file(nomefile);
if(filein!=NULL)
{
N=get_matrix(filein, &matrice, nomefile);
if(genera_soluzione(matrice, N, 0, 0))
{
printf("\n***** Soluzione *****\n");
stampa_soluzione(matrice, N);
}
else
printf("\nSoluzione impossibile");
}
return 0;
}
/* example file */
6 0 0 0 0 0 4 3 0
0 0 0 0 7 0 5 1 0
0 0 0 3 0 4 0 0 9
0 0 3 0 0 8 9 0 0
0 2 0 0 0 0 0 8 0
0 0 8 5 0 0 2 0 0
2 0 0 4 0 7 0 0 0
0 1 4 0 6 0 0 0 0
0 6 9 0 0 0 0 0 7
