Last active
October 11, 2016 18:04
-
-
Save HorlogeSkynet/08e88775d49b35b5c7ef to your computer and use it in GitHub Desktop.
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)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 ! |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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