// 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