Solveur de Sudoku en C

Dans le programme de mes études de Master Cryptologie à Bordeaux 1, j’étudie la programmation en C. Le projet de ce semestre était de créer un solveur/générateur de sudokus.

Je vous laisse donc deux fichiers, un contenant les sources du programme, et l’autre étant mon rapport de projet, expliquant un peu le programme.

Rapport-Sudoku

Si vous avez des questions, n’hésitez pas.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include "preemptive_set.h"
#include 

bool verbose = false;
bool generate = false;
char* executable;
FILE* output;
size_t grid_size = MAX_SIZE;
int iteration=0;
int backtracking=0;
int solution = 0;
bool strict = false;
bool find_nb_solution = false;
double level=0.66;//percent of empty cells

//********************Usage fonctions********************
static void usage (int status)
{
 if (status == EXIT_SUCCESS)
 {
 fprintf (stdout, "Usage: %s [OPTION] FILE...\n"
 "Solve Sudoku puzzle's of variable sizes(1-4).\n\n"
 "\t-o, --output=FILE\t\twrite result to FILE\n"
 "\t-g, --generate[grid_size]"
 "\tgenerate a grid of grid_size (default 9)\n"
 "\t-v, --verbose\t\t\tverboseoutput\n"
 "\t-V, --version\t\t\tdisplay version and exit\n"
 "\t-h, --help\t\t\tdisplay this help\n\n", executable);
 exit (EXIT_SUCCESS);
 }
 else
 {
 fprintf (stderr, "Try '%s --help' for more information.\n\n", executable);
 exit (EXIT_FAILURE);
 }
}

static void version( )
{
 fprintf (stdout, "%s %d.%d.%d\n This software is a sudoku solver.\n\n",
 executable, VERSION, SUBVERSION, REVISION);
 exit (EXIT_SUCCESS);
}

//********************Print grid********************
//Print grid
void print_grid (pset_t **grid)
{
 char temp [grid_size];

 for (size_t i = 0; i < grid_size; i++)
 {
 for (size_t j = 0; j < grid_size; j++)
 {
 if (generate)
 {
 if (pset_count (grid [i] [j]) != 1)
 {
 temp [0] = '_';
 temp [1] = '\0';
 }
 else
 pset2str ( (char*) &temp, grid [i] [j]);
 }
 else
 pset2str ( (char*) &temp, (grid [i] [j]|FIXED)^FIXED);
 if (output != NULL)
 fprintf (output, "%s ", temp);
 else
 printf ("%s ", temp);
 }

 if (output != NULL)
 fprintf (output, "\n");
 else
 printf ("\n");
 }
}

//********************Grid creation fonctions********************
//Check characters input
static bool check_input_char (char c)
{
 bool test;
 switch (grid_size)
 {
 case 25:
 test = ((c >= '1' && c <= '9') || (c >= 'A' && c <= 'P') || c == '_');
 break;

 case 16:
 test = ((c >= '1' && c <= '9') || (c >= 'A' && c <= 'G') || c == '_');
 break;

 case 9:
 test = ((c >= '1' && c <= '9') || c == '_');
 break;

 case 4:
 test = ((c >= '1' && c <= '4') || c == '_');
 break;

 case 1:
 test = (c == '1' || c == '_');
 break;

 default:
 test = false;
 }
 return test;
}

//Allocation of memory for the grid
static pset_t **grid_alloc (char first_line[])
{
 //Allocation of vector with pointers
 pset_t **grid = calloc (grid_size, sizeof(pset_t*));
 if (grid == NULL)
 {
 usage (EXIT_FAILURE);
 }

 //Allocation of lines
 for (size_t i = 0; i < grid_size; i++)
 {
 grid[i] = calloc (grid_size, sizeof(pset_t));
 if (grid[i] == NULL)
 {
 usage (EXIT_FAILURE);
 }
 }

 //Copy first line
 for (size_t j = 0; j < grid_size; j++)
 {
 if (first_line[j] == '_')
 pset_init (&grid [0] [j], grid_size);
 else
 pset_set (&grid [0] [j], first_line[j]);
 }

 return grid;
}

//Free memory of the grid
void grid_free (pset_t **grid)
{
 //Free each line
 for (size_t i = 0; i < grid_size; i++)
 free (grid[i]);

 //Free vector with pointers
 free (grid);
}

//Copy grid
void grid_copy (pset_t **grid_dest, pset_t **grid_src){
 for (size_t  i = 0; i < grid_size; i++)
 memcpy (grid_dest [i], grid_src [i], grid_size * sizeof (pset_t));
}

//Read characters, test them and copy them
static pset_t **grid_parser (FILE *file)
{
 char current_char;
 int column = 0;
 int line = 0;
 pset_t **grid;
 char first_line [MAX_SIZE];

 while (fscanf (file, "%c", &current_char) != EOF)
 {
 switch (current_char)
 {

 case ' ':
 case '\t':
 break;

 case '#': //Comment
 if (line != (int) grid_size)
 {
 fprintf (stderr, "%s error: Nb lines must be %d and it is %d.\n",
 executable, grid_size, line);
 usage (EXIT_FAILURE);
 }
 while (fgetc (file) != '\n') //End of line
 continue;
 break;

 case '\n':
 if (column == 0) //Empty line
 break;

 if (line == 0) //First line
 {
 if (sqrt (column) == (int) sqrt (column)) //Error grid size
 grid_size = column;
 else
 {
 fprintf (stderr, "%s error: Incorrect grid size.\n",
 executable);
 usage (EXIT_FAILURE);
 }
 for (size_t i = 0; i < grid_size; i++)
 check_input_char (current_char);

 grid = grid_alloc(first_line);
 }
 else
 {
 if (column != (int) grid_size)//Error nb cells
 {
 fprintf (stderr, "%s error: "
 "Nb cells must be %d and it is %d at line %d.\n",
 executable, grid_size, column,line+1);
 usage (EXIT_FAILURE);
 }
 }

 column = 0;
 line++;
 break;

 default:
 if (line < (int) grid_size)
 {

 if (check_input_char (current_char))
 {

 if (line != 0)
 {
 if (current_char == '_')
 pset_init (&grid [line] [column], grid_size);
 else
 pset_set (&grid [line] [column], current_char);
 }

 else
 first_line [column] = current_char;
 column++;
 }

 else
 {//Error wrong character
 fprintf (stderr, "%s error: "
 "wrong character '%c' at line %d column %d.\n",
 executable, current_char, line+1,column);
 usage (EXIT_FAILURE);
 }
 break;
 }
 else
 {//Error nb lines
 fprintf (stderr, "%s error: "
 "Nb lines must be %d and it is more.\n",
 executable, grid_size);
 usage (EXIT_FAILURE);
 }
 }
 }

 if (line != (int) grid_size)
 {
 fprintf (stderr, "%s error: Nb lines must be %d and it is %d.\n",
 executable, grid_size, line);
 usage (EXIT_FAILURE);
 }

 return grid;
}

//********************Fonctions to scan grid********************
void enumerate_lines (pset_t **grid, int line, pset_t *subgrid [grid_size])
{
 for (size_t i = 0; i < grid_size; i++)
 {
 subgrid [i] = &grid [line] [i];
 }
}

void enumerate_columns (pset_t **grid, int column, pset_t *subgrid [grid_size])
{
 for (size_t  i = 0; i < grid_size; i++)
 {
 subgrid [i] = &grid [i] [column];
 }
}

void enumerate_blocs (pset_t **grid, int bloc, pset_t *subgrid [grid_size])
{
 int n = sqrt (grid_size);
 int compteur = 0;

 for (int i = (int)(bloc / n) * n; i < (int)(bloc / n) * n + n; i++)
 {
 for (int j = (bloc % n) * n; j < (bloc % n) * n + n ; j++)
 {
 subgrid [compteur] = &grid [i] [j];
 compteur++;
 }
 }
}

//********************Fonctions to test solutions********************
bool one_color_by_subgrid (pset_t *subgrid [grid_size])
{
 bool test = true;

 for (size_t i = 0; i < grid_size; i++)
 {
 if (((*subgrid [i] | FIXED) == FIXED))
 return false;
 if (pset_is_singleton (*subgrid [i]))
 for (size_t  j = 0; j < grid_size; j++)
 if (i != j)
 test = test && !((*subgrid [i] | FIXED) == (*subgrid [j] | FIXED));
 }

 return test;
}

bool check_consistency (pset_t **current_grid)
{
 bool verify = true;
 pset_t* subgrid [grid_size];

 for (size_t i = 0; i < grid_size; i++)
 {
 enumerate_lines (current_grid, i, subgrid);
 verify = (verify & one_color_by_subgrid (subgrid));

 enumerate_columns (current_grid, i, subgrid);
 verify = (verify & (one_color_by_subgrid (subgrid)));

 enumerate_blocs (current_grid, i, subgrid);
 verify = (verify & (one_color_by_subgrid (subgrid)));
 }

 return verify;
}

bool grid_resolved (pset_t **current_grid)
{
 for (size_t i = 0; i < grid_size; i++)
 for (size_t j = 0; j < grid_size; j++)
 if (!pset_is_singleton (current_grid [i] [j]))
 return false;

 return true;
}

//********************Fonctions to solve grid********************
//Fonction with heuristics applies to subgrids
//Cross-hatching
bool cross_hatching(pset_t *vector[ ])
{
 bool test=false;

 for (size_t  i =0; i < grid_size; i++)
 {
 if (pset_is_singleton (*vector [i]))
 {
 for (size_t  j = 0; j < grid_size; j++)
 {
 if (i != j && pset_is_included (*vector [i], *vector [j] | FIXED))
 {
 *vector [j] = pset_exclusive_union (*vector [j], *vector [i]);
 test = true;
 }
 }
 }
 }
 return test;
}

//Lone-number
bool lone_number (pset_t *vector[ ])
{
 bool test=false;

 pset_t temp;
 for (size_t  i = 0; i < grid_size; i++)
 {
 if (!pset_is_singleton (*vector [i])){
 temp = (*vector [i]);
 for (size_t j = 0; j < grid_size; j++)
 {
 if (i != j)
 temp = pset_exclusive_union
 (temp, pset_intersection (temp, *vector [j]));
 }
 if (pset_is_singleton (temp))
 {
 *vector [i] = temp;
 test = true;
 }
 }
 }
 return test;
}

//Naked subset
bool naked_subset(pset_t *vector[ ])
{
 bool test=false;

 size_t count;
 size_t size;

 for (size_t  i = 0; i < grid_size; i++)
 {
 if (!pset_is_singleton (*vector [i]))
 {
 size = pset_count (*vector [i]);
 count = 0;
 for (size_t j = i; j < grid_size; j++)
 {
 if ((*vector [i]) == (*vector [j])){
 count ++;
 }
 }
 if (count == size && (count != 1))
 {
 for (size_t j = 0; j < grid_size; j++)
 {
 if (pset_is_included (*vector [i], *vector [j])
 && ((*vector [j]) != (*vector [i])))
 {
 test = true;
 *vector [j] = pset_exclusive_union
 (*vector [j], *vector [i]);
 }
 }
 }
 }
 }
 return test;
}

bool subgrid_heuristics (pset_t *vector[ ])
{
 bool test = false;

 test = cross_hatching(vector);
 test = test | lone_number(vector);
 test = test | naked_subset(vector);
 return test;
}

//Fonction who solves grid
bool grid_solver (pset_t **current_grid)
{
 pset_t* subgrid [grid_size];
 bool fixpoint = false;

 //While changes are made
 while (!fixpoint)
 {
 if (verbose)
 {
 fprintf (stdout, "%d appel(s) heuristiques\n", ++iteration);
 if(output==NULL)
 print_grid (current_grid);
 fprintf (stdout,"\n");
 }
 fixpoint = true;
 for (size_t i = 0; i < grid_size; i++)
 {
 //Apply heuristics on line i
 enumerate_lines (current_grid, i, subgrid);
 fixpoint = (fixpoint ^(subgrid_heuristics (subgrid)));
 //Apply heuristics on column i
 enumerate_columns (current_grid, i, subgrid);
 fixpoint = (fixpoint ^(subgrid_heuristics (subgrid)));
 //Apply heuristics on block i
 enumerate_blocs (current_grid, i, subgrid);
 fixpoint = (fixpoint ^(subgrid_heuristics (subgrid)));
 }
 //If grid isn't consistent, we can't stop
 if (!check_consistency (current_grid))
 return false;
 }

 pset_t **grid_temp = grid_alloc("");
 char temp[grid_size];
 int color = 0;

 //Backtracking
 while (!grid_resolved (current_grid))
 {
 if (verbose)
 {
 fprintf (stdout, "Niveau %d pour backtracking\n", ++backtracking);
 fprintf (stdout, "\n");
 }

 //Save grid
 grid_copy(grid_temp,current_grid);

 //Choice of pset and color to set
 int c_backup = 0;
 int l_backup = 0;
 int taille = (int)grid_size;
 for (size_t l = grid_size-1; l >0; l--)
 {
 for (size_t c = grid_size-1; c >0; c--)
 {
 if (!pset_is_singleton (grid_temp [l] [c]))
 if (pset_count (grid_temp [l] [c]) <= taille){
 c_backup = c;
 l_backup = l;
 taille = pset_count (grid_temp [l] [c]);
 if(taille==2)
 break;
 }

 }
 }

 pset2str ((char *)&temp, grid_temp [l_backup] [c_backup]);

 //If generate choice of color is random
 if(generate)
 color = rand() % strlen (temp);

 //Delete color in pset
 grid_temp [l_backup] [c_backup] = char2pset (temp [color]);

 //Solve with new grid
 if (grid_solver (grid_temp))
 {
 //Grid resolved
 if (verbose)
 {
 fprintf (stdout, "Niveau %d pour backtracking\n", --backtracking);
 fprintf (stdout, "\n");
 }
 if (find_nb_solution)
 {
 solution++;
 grid_free(grid_temp);
 return (solution>1);
 }
 else
 {
 //Copy grid resolved and quit
 grid_copy(current_grid,grid_temp);
 grid_free(grid_temp);
 return true;
 }
 }
 else
 {
 //Wronf choice of color in pset
 if (verbose)
 {
 fprintf (stdout, "Niveau %d pour backtracking\n", -- backtracking);
 fprintf (stdout, "\n");
 }
 //If it left no solution, free and quit
 if (pset_is_singleton (current_grid [l_backup] [c_backup]))
 {
 grid_free (grid_temp);
 return false;
 }

 //Delete color in pset because it give no solutions
 pset_discard (¤t_grid [l_backup] [c_backup], temp [color]);

 //Test if grid is always consistent
 if (!check_consistency(current_grid))
 {
 grid_free (grid_temp);
 return false;
 }
 }

 }

 solution++;
 grid_free (grid_temp);
 return true;
}

void generate_grid (pset_t **grid)
{
 pset_t **grid_temp = grid_alloc("");
 pset_t **grid_backup = grid_alloc("");

 //Initialise grid
 for (size_t i = 0; i < grid_size; i++)
 {
 for (size_t j = 0; j < grid_size; j++)
 {
 pset_init (&grid [i] [j], grid_size);
 }
 }

 grid_solver (grid);

 if(strict){
 find_nb_solution = true;
 level=0.5;
 }

 generate = false;

 int nb_cells_empty = 0;
 int hasard;

 pset_t *tab [grid_size * grid_size];
 int taille = 0;

 //Add cells to tab
 for (size_t  i = 0; i < grid_size; i++)
 for (size_t  j = 0; j < grid_size; j++){
 tab[taille] = &grid [i][j];
 taille ++;
 }

 while (taille != 0)
 {
 hasard = rand() % (taille) - 1;
 if (hasard == -1)
 hasard=0;
 if (strict)
 //Backup grid
 grid_copy(grid_backup, grid);

 //Delete cell in grid
 pset_init (tab[hasard], grid_size);

 tab[hasard] = tab[taille - 1];
 taille --;

 if (strict)
 {
 //Backup grid to resolve
 grid_copy (grid_temp, grid);

 solution = 0;
 grid_solver (grid_temp);
 }

 //Test nb of solutions
 if (solution != 1)
 //Recopy backup in grid
 grid_copy (grid, grid_backup);

 else
 {
 nb_cells_empty++;
 //Test if nb_cells_empty is sufficient
 if (nb_cells_empty > (int)(level * (grid_size * grid_size)))
 break;
 }
 }

 generate = true;
 grid_free (grid_temp);
 grid_free (grid_backup);
}

//********************Main********************
int main (int argc, char* argv[ ]){
 FILE *file;
 int optc;
 srand (time (NULL));
 executable = basename (argv [0]);

 //Array with options
 static struct option long_options[ ] =
 {
 {"help", 0, 0, 'h'},
 {"output", 1, 0, 'o'},
 {"version", 0, 0, 'V'},
 {"verbose", 0, 0, 'v'},
 {"generate", 2, 0, 'g'},
 {"strict", 0, 0, 's'},
 {0, 0, 0, 0}
 };

 //Gestion arguments
 while ((optc = getopt_long
 (argc, argv, "ho:Vvg::s", long_options, NULL)) != -1)
 {
 switch (optc)
 {
 case 'h': /*h option -> help*/
 usage (EXIT_SUCCESS);
 break;
 case 'V': /*V option -> version*/
 version (argv [0]);
 break;
 case 'v': /*v option -> verbose*/
 verbose = true;
 break;
 case 'o': /*o option -> outputfile*/
 //Open file to  write in
 output = fopen (optarg, "w");
 if (output == NULL)
 usage (EXIT_FAILURE);
 break;
 case 'g': /*g option -> generate*/
 generate = true;
 grid_size = 9;
 if (optarg != NULL){
 grid_size = (size_t) atoi (optarg);
 if (grid_size != 1 && grid_size != 4 && grid_size != 9
 && grid_size != 16 && grid_size != 25)
 usage (EXIT_FAILURE);
 }
 break;
 case 's'://Grid with only one solution
 strict=true;
 break;
 default:
 usage (EXIT_FAILURE);
 }
 }

 //Creation of the grid
 if(generate)
 {
 pset_t**grid = grid_alloc("");
 generate_grid (grid);
 print_grid (grid);
 grid_free(grid);
 }
 else
 {
 //Test of file argument
 if (argc != optind + 1)

 usage (EXIT_FAILURE);

 //Open file with grid
 file = fopen (argv [argc - 1], "r");
 if (file == NULL)
 usage (EXIT_FAILURE);

 pset_t **grid = grid_parser (file);

 if(grid_solver (grid))
 {
 print_grid(grid);
 }
 else
 {
 printf("Grille sans solution\n");
 }

 //Free memory of grid
 grid_free (grid);
 //Close file
 fclose (file);
 }
 exit (EXIT_SUCCESS);
}