Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A program which resolves a Sudoku grid written down in a text file (only the first grid, at the head of the file, is computed)
1 0 0 0 0 7 0 9 0
0 3 0 0 2 0 0 0 8
0 0 9 6 0 0 5 0 0
0 0 5 3 0 0 9 0 0
0 1 0 0 8 0 0 0 2
6 0 0 0 0 4 0 0 0
3 0 0 0 0 0 0 1 0
0 4 0 0 0 0 0 0 7
0 0 7 0 0 0 3 0 0
Extreme #1: Resolved !
0 0 3 0 8 2 0 0 4
6 0 0 0 4 0 8 1 5
0 4 0 7 0 5 0 0 6
1 3 0 9 0 4 7 0 0
0 0 4 2 0 6 3 0 0
0 0 7 8 0 1 0 4 9
4 0 0 1 0 3 0 9 0
7 6 5 0 9 0 0 0 3
3 0 0 5 2 0 4 0 0
Easy: Resolved !
0 0 0 0 9 0 8 3 0
0 2 0 0 0 0 0 0 5
0 0 0 2 8 1 7 0 6
0 4 1 7 3 0 6 0 8
9 7 0 0 0 0 0 5 1
2 0 6 0 5 4 3 7 0
1 0 9 3 4 2 0 0 0
4 0 0 0 0 0 0 6 0
0 3 7 0 1 0 0 0 0
Medium: Resolved !
0 6 8 0 0 0 7 2 0
5 0 0 7 0 0 0 0 0
0 2 0 6 0 9 1 0 3
0 0 0 0 0 0 0 8 0
0 8 1 9 0 2 4 3 0
0 3 0 0 0 0 0 0 0
6 0 2 5 0 3 0 7 0
0 0 0 0 0 7 0 0 5
0 7 5 0 0 0 3 9 0
Hard: Resolved !
0 4 0 6 0 0 0 1 0
0 9 8 0 0 4 0 0 0
1 2 0 0 0 8 5 0 0
0 0 0 0 3 0 0 0 1
3 0 2 0 0 0 6 0 7
4 0 0 0 5 0 0 0 0
0 0 5 2 0 0 0 8 3
0 0 0 1 0 0 9 6 0
0 3 0 0 0 5 0 2 0
Devilish: Resolved !
8 0 0 0 0 0 0 0 0
0 0 3 6 0 0 0 0 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
0 0 0 0 4 5 6 0 0
0 0 0 1 0 0 0 3 0
0 0 1 0 0 0 0 6 8
0 0 8 5 0 0 0 1 0
0 9 0 0 0 0 4 0 0
Extreme #2: Resolved !
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define SIZE 9
#define MINNBVALUES 17
#define FIRST -9999
enum BORNE
{
INF1,
SUP1,
INF2,
SUP2
};
bool grilleValide(short int matrice[SIZE][SIZE], short int bornesBoucles[]);
bool chiffreValide(short int i, short int j, short int chiffre, short int copieMatrice[SIZE][SIZE], short int bornesBoucles[]);
bool verification(short int copieMatrice[SIZE][SIZE], short int bornesBoucles[]);
void bornes(short int i, short int j, short int bornesBoucles[]);
void copie(short int matrice[SIZE][SIZE], short int copieMatrice[SIZE][SIZE]);
void remplissage(short int indiceBranche, short int valeursPossibles[SIZE][SIZE][SIZE], short int matrice[SIZE][SIZE], short int copieMatrice[SIZE][SIZE], short int bornesBoucles[]);
void resolution(short int matrice[SIZE][SIZE], short int bornesBoucles[]);
int main(int argc, char const *argv[])
{
short int temp;
short int matrice[SIZE][SIZE] = {{0}, {0}}, i = 0, j = 0;
short int bornesBoucles[4] = {0};
FILE *file = fopen("sudoku.txt", "r");
if(file == NULL)
{
printf("\033[31m\nCan\'t open the \"sudoku.txt\" file.\n\n\033[0m");
exit(EXIT_FAILURE);
}
for(i = 0; i < SIZE; i++)
{
for(j = 0; j < SIZE; j++)
{
fscanf(file, "%hd", &temp);
matrice[i][j] = temp;
}
}
fclose(file);
if(grilleValide(matrice, bornesBoucles))
{
resolution(matrice, bornesBoucles);
file = fopen("sudoku_resolved.txt", "w");
if(file != NULL)
{
for(i = 0; i < SIZE; i++)
{
for(j = 0; j < SIZE; j++)
{
fprintf(file, "%hd ", matrice[i][j]);
}
fprintf(file, "\n");
}
fclose(file);
}
}
printf("\033[0m");
return 0;
}
void bornes(short int i, short int j, short int bornesBoucles[])
{
if(j < 3)
{
bornesBoucles[INF2] = 0;
bornesBoucles[SUP2] = 3;
if(i < 3)
{
bornesBoucles[INF1] = 0;
bornesBoucles[SUP1] = 3;
}
else if(i >= 3 && i < 6)
{
bornesBoucles[INF1] = 3;
bornesBoucles[SUP1] = 6;
}
else
{
bornesBoucles[INF1] = 6;
bornesBoucles[SUP1] = 9;
}
}
else if(j >= 3 && j < 6)
{
bornesBoucles[INF2] = 3;
bornesBoucles[SUP2] = 6;
if(i < 3)
{
bornesBoucles[INF1] = 0;
bornesBoucles[SUP1] = 3;
}
else if(i >= 3 && i < 6)
{
bornesBoucles[INF1] = 3;
bornesBoucles[SUP1] = 6;
}
else
{
bornesBoucles[INF1] = 6;
bornesBoucles[SUP1] = 9;
}
}
else
{
bornesBoucles[INF2] = 6;
bornesBoucles[SUP2] = 9;
if(i < 3)
{
bornesBoucles[INF1] = 0;
bornesBoucles[SUP1] = 3;
}
else if(i >= 3 && i < 6)
{
bornesBoucles[INF1] = 3;
bornesBoucles[SUP1] = 6;
}
else
{
bornesBoucles[INF1] = 6;
bornesBoucles[SUP1] = 9;
}
}
}
bool chiffreValide(short int i, short int j, short int chiffre, short int copieMatrice[SIZE][SIZE], short int bornesBoucles[])
{
static short int ligne = 0, colonne = 0, c1 = 0, c2 = 0;
for(ligne = 0; ligne < SIZE; ligne++)
{
if(chiffre == copieMatrice[i][ligne] && ligne != j)
{
return false;
}
}
for(colonne = 0; colonne < SIZE; colonne++)
{
if(chiffre == copieMatrice[colonne][j] && colonne != i)
{
return false;
}
}
bornes(i, j, bornesBoucles);
for(c1 = bornesBoucles[INF1]; c1 < bornesBoucles[SUP1]; c1++)
{
for(c2 = bornesBoucles[INF2]; c2 < bornesBoucles[SUP2]; c2++)
{
if(chiffre == copieMatrice[c1][c2] && c1 != i && c2 != j)
{
return false;
}
}
}
return true;
}
bool verification(short int copieMatrice[SIZE][SIZE], short int bornesBoucles[])
{
short int i, j;
for(i = 0; i < SIZE; i++)
{
for(j = 0; j < SIZE; j++)
{
if(!chiffreValide(i, j, copieMatrice[i][j], copieMatrice, bornesBoucles))
{
printf("\033[31m\nIncorrect grid.\n\n\033[0m");
return false;
}
}
}
printf("\033[32m\nCorrect grid.\n\n\033[0m");
return true;
}
bool grilleValide(short int matrice[SIZE][SIZE], short int bornesBoucles[])
{
short int i, j, nbValeurs = 0;
for(i = 0; i < SIZE; i++)
{
for(j = 0; j < SIZE; j++)
{
if(matrice[i][j] != 0)
{
if(!chiffreValide(i, j, matrice[i][j], matrice, bornesBoucles))
{
printf("\033[31m\nEmpty grid: Bad place for value ([%d;%d]: %d).\n\n\033[0m", i, j, matrice[i][j]);
return false;
}
nbValeurs++;
}
}
}
if(nbValeurs >= MINNBVALUES)
{
printf("\033[32m\nEmpty grid: Ok.\n\n\033[0m");
return true;
}
else
{
printf("\033[31m\nEmpty grid: Not enough values to resolve the puzzle.\n\n\033[0m");
return false;
}
}
void copie(short int matrice[SIZE][SIZE], short int copieMatrice[SIZE][SIZE])
{
short int i, j;
for(i = 0; i < SIZE; i++)
{
for(j = 0; j < SIZE; j++)
{
copieMatrice[i][j] = matrice[i][j];
}
}
}
void remplissage(short int indiceBranche, short int valeursPossibles[SIZE][SIZE][SIZE], short int matrice[SIZE][SIZE], short int copieMatrice[SIZE][SIZE], short int bornesBoucles[])
{
static short int i = 0, j = 0;
static short int nbValeursPossibles[SIZE][SIZE] = {{0}, {0}};
static short int dernierIndice[SIZE][SIZE] = {{1}, {1}};
static bool backtracking = false;
if(indiceBranche == FIRST) /* We fill the array for each case only if it's the first iteration */
{
short int t = 0;
for(i = 0; i < SIZE; i++)
{
for(j = 0; j < SIZE; j++)
{
for(t = 1; t < SIZE; t++)
{
if(valeursPossibles[i][j][t] != 0)
{
nbValeursPossibles[i][j]++;
}
}
}
}
i = 0;
j = 0;
indiceBranche = 1;
}
while(i < SIZE)
{
while(j < SIZE)
{
if(copieMatrice[i][j] == 0 || backtracking) /* If the case is empty OR if we backtrack */
{
backtracking = false;
while(indiceBranche <= nbValeursPossibles[i][j]) /* We browse the available branches */
{
if(chiffreValide(i, j, valeursPossibles[i][j][indiceBranche], copieMatrice, bornesBoucles)) /* If the value of this branch is coherent with the whole grid... */
{
printf("\033[32m[%hd, %hd]: %hd\n\033[0m", i, j, valeursPossibles[i][j][indiceBranche]);
copieMatrice[i][j] = valeursPossibles[i][j][indiceBranche];
dernierIndice[i][j] = indiceBranche;
j++;
if(j == SIZE && i != SIZE)
{
i++;
if(i == SIZE)
{
i = SIZE;
j = SIZE;
}
else
{
j = 0;
}
}
remplissage(1, valeursPossibles, matrice, copieMatrice, bornesBoucles);
}
else
{
printf("\033[31m[%hd, %hd]: %hd\n\033[0m", i, j, valeursPossibles[i][j][indiceBranche]);
indiceBranche++;
if(indiceBranche > nbValeursPossibles[i][j]) /* We have browsed all the values for that branch --> Backtracking ! */
{
do
{
dernierIndice[i][j] = 1; /* We NEVER browsed this branch, NEVER :D */
if(matrice[i][j] == 0) /* If there was a '0' in this case... */
{
copieMatrice[i][j] = 0; /* ... we put again one ! */
}
j--;
if(j < 0)
{
i--;
if(i < 0)
{
i = 0;
j = 0;
}
else
{
j = SIZE - 1;
}
}
dernierIndice[i][j]++; /* We chose the next index of the previous case */
} while(dernierIndice[i][j] > nbValeursPossibles[i][j]); /* We check the validity of this index, else we backtrack again */
backtracking = true; /* We backtrack because this case is full ! */
remplissage(dernierIndice[i][j], valeursPossibles, matrice, copieMatrice, bornesBoucles);
}
}
}
}
else /* In this case, next case ! */
{
dernierIndice[i][j] = 1; /* We have never browsed the branches of this case ! */
j++;
if(j == SIZE && i != SIZE)
{
i++;
if(i == SIZE)
{
i = SIZE;
j = SIZE;
}
else
{
j = 0;
}
}
}
}
}
}
void resolution(short int matrice[SIZE][SIZE], short int bornesBoucles[])
{
short int copieMatrice[SIZE][SIZE] = {{0}};
short int valeursPossibles[SIZE][SIZE][SIZE] = {{{0}}};
short int i, j, v, test;
for(i = 0; i < SIZE; i++)
{
for(j = 0; j < SIZE; j++)
{
for(test = 1, v = 1; test <= SIZE; test++)
{
if(matrice[i][j] == 0 && chiffreValide(i, j, test, matrice, bornesBoucles))
{
valeursPossibles[i][j][v] = test;
v++;
}
}
}
}
copie(matrice, copieMatrice);
remplissage(FIRST, valeursPossibles, matrice, copieMatrice, bornesBoucles);
verification(copieMatrice, bornesBoucles);
copie(copieMatrice, matrice);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment