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)

sudoku.txt

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 !

SudokuResolution.c

#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);
}