Rapport sur Sudoku Solver
Table of Contents
Présentation du problème
Sudoku Solver est un problème du site Codingame. Il consiste en la création d’un programme permettant la résolution d’une grille de Sudoku. Voici tout d’abord un point sur ce qu’est un Sudoku:
Le sudoku, est un jeu en forme de grille, créé en 1979 par l’Américain Howard Garns qui s’est inspiré de jeux plus anciens afin de le créer. Le but du jeu est de compléter la grille selon les règles suivantes (on décrira ici les règles pour une grille classique de 9*9):
- Chaque ligne doit contenir de façon unique les nombres de 1 à 9.
- Chaque colonne doit contenir de façon unique les nombres de 1 à 9.
- Chaque carré de 3*3 délimité sur la grille doit contenir de façon unique les nombres de 1 à 9.
Alors, suivant ces règles, notre programme doit compléter et renvoyer la grille de Sudoku donnée en entrée, ligne par ligne. Chaque ligne est donnée sous la forme d’un tableau de caractère. Les cases restantes à compléter sont représentées par des 0.
Métode de résolution
Description de la stratégie
Afin de résoudre ce probème, j’ai décidé de procéder de la manière suivante. Il me fallait créer une fonction récursive qui allait me permettre de compléter le tableau, et une fonction me permettant de vérifier si le nombre sélectionné pouvait être ajouté au tableau. C’est-à-dire, vérifier si il respecte bien les règles du Sudoku. Pour cela, j’ai découpé mon code en plusieurs parties présentées ci dessous.
Partie 1: Fonction test
int test(int y, int x, int n) { // Définition de la fonction int x0=0, y0=0; // Définition des variables int count=1; while (x0 < 9 && count==1) { // Vérifie si le nombre testé est déja sur la ligne if (tab[y][x0] == n) { count=0; } x0++; } while (y0 < 9 && count==1) { // Vérifie si le nombre testé est déja sur la colonne if (tab[y0][x] == n) { count=0; } y0++; } x0 = (x / 3) * 3; // Vérifie si le nombre testé est déja dans le carré de 3 par 3 y0 = (y / 3) * 3; int i=0; while (i < 3 && count==1) { int j = 0; while (j < 3 && count==1) { if (tab[y0+i][x0+j] == n) { count=0; } j++; } i++; } return count; }
Dans cette première partie, je définie une fonction test, qui va me permettre de tester la validité des nombre que je souhaite ajouter à la grille. Cette fonction prend en argument les coordonnées de la position à laquelle on souhaite ajouter le nombre, ainsi que le nombre que l’on souhaite ajouter. Premièrement, la fonction va tester si le nombre testé est présent sur la ligne où l’on souhaite l’ajouter. Si c’est le cas, on renverra le code 0 qui, dans le cadre de ce code représentera un échec. Ensuite, la fonction va tester de la même manière, si le nombre que l’on souhaite ajouter est déjà présent sur la colonne. Enfin, dans une troisième boucle, qui est une double boucle while, on va parcourir le tableau afin de vérifier si le nombre est déjà présent dans le cube de 3*3. A la fin de tout ces test, on renverra 1 si tout les tests sont passés, sinon la fonction renverra 0.
Partie 2: Fonction solve
void solve() { // Défition de la récursion int y, x, n; for (y = 0; y < 9; y++) { // On parcour le tableau for (x = 0; x < 9; x++) { if (tab[y][x] == 0) { // Si on tombe sur une case non remplie for (n = 1; n < 10; n++) { if (test(y, x, n)) { // Test les nombres qui peuvent aller dans la case tab[y][x] = n; // Mise à jour du tableau solve(); // On relance la fonction tab[y][x] = 0; // Remise à 0 de la case si mauvais choix } } return; } } }
Dans cette partie, on retrouve la fonction solve, utilisant le mécanisme de récursion, qui va nous permettre de trouver la solution à la grille de Sudoku.
Partie 3: Fonction solve affichage
for (int i = 0; i < 9; i++) { // Parcour de chaque case for (int j = 0; j < 9; j++) { printf("%d", tab[i][j]); // Affichage de chaque case } printf("\n"); } exit(0); }
Enfin, à l’intérieur de la fonction récursive, lorsque la grille sera complète, on l’affichera à l’aide d’une double boucle qui parcourera le tableau. Il ne me restait plus qu’à coder la boucle principale du programme.
Partie 4: Boucle principale
int i, j; char line[10]; for (i = 0; i < 9; i++) { // Récupération des entrées scanf("%s", line); for (j = 0; j < 9; j++) { tab[i][j] = line[j] - '0'; // Conversion des entrées en caractère } } solve(); return 0;
Dans le programme principal, on va simplement récupérer les entrées fournies par Codingame, puis on va appeler la fonction solve, qui va résoudre le Sudoku.
Détail algorithmique de la méthode
Ce programme se base essentiellement sur le principe de récursion. Je vais donc décrire plus en détail son fonctionnement à l’aide du schéma ci dessous.
Cliquez ici pour agrandir
Dans le schéma ci dessus, les flèches rouges représentent un test négatif, et les vertes un test positif.
Tout d’abord revenons sur ce qu’est un mécanisme de récursion. Ce mécanisme consiste en l’appel d’une fonction à l’intérieur d’elle même. Une fonction récursive mal définie/codée peut donc engendrer un nombre infini d’appel. Mais ce mécanisme bien utilisé peut être très puissant et extrémement utile.
C’est le cas de cette fonction qui l’utilise afin de trouver la solution au Sudoku de manière brute. C’est-à-dire qu’elle teste toutes les solutions possibles jusqu’à trouver la bonne. Dans cette fonction (solve()), on parcour le tableau, et dès que l’on trouve un 0, on essaye de remplir la case. Alors, on test tout les nombres de 1 à 9 à l’aide de la fonction décrite précedement. Dès que l’on trouve un nombre qui fonctionne, on le place dans la grille, puis on appelle à nouveau la fonction, jusqu’à ce que la grille soit remplie. Alors, si les nombres placés bloquent la grille de Sudoku par la suite, les cases précedement remplies seront remises à 0, et le test sera fait avec d’autres nombres. Alors, la fonction ne s’arrétera que lorsque toute la grille sera remplie.
Voici un exemple:
L’étape 1 représente la grille initiale, vide. Lors de l’étape 2, on observe le remplissage du sudoku jusqu’à ce que le programme soit bloqué. En effet, à la place du ?, on ne peut mettre aucun nombre respectant les régles du sudoku. Alors après une série d’étapes intermédiaires qui ne sont pas représentées, où l’on va progressivement revenir en arrière dans la grille, le programme assigne à la troisième case en haut à gauche la valeur 3 (étape 3). En effet, c’est l’unique possibilitée dans cette case. Alors, le programme va continuer de tourner selon le même principe, jusqu’à trouver la solution affichée à l’étape 4.
Code commenté ayant résolu le problème
Voici ci dessous le code complet m’ayant permis de résoudre le problème.
#include <stdio.h> #include <stdlib.h> int tab[10][10]; int test(int y, int x, int n) { // Définition de la fonction int x0=0, y0=0; // Définition des variables int count=1; while (x0 < 9 && count==1) { // Vérifie si le nombre testé est déja sur la ligne if (tab[y][x0] == n) { count=0; } x0++; } while (y0 < 9 && count==1) { // Vérifie si le nombre testé est déja sur la colonne if (tab[y0][x] == n) { count=0; } y0++; } x0 = (x / 3) * 3; // Vérifie si le nombre testé est déja dans le carré de 3 par 3 y0 = (y / 3) * 3; int i=0; while (i < 3 && count==1) { int j = 0; while (j < 3 && count==1) { if (tab[y0+i][x0+j] == n) { count=0; } j++; } i++; } return count; } void solve() { // Défition de la récursion int y, x, n; for (y = 0; y < 9; y++) { // On parcour le tableau for (x = 0; x < 9; x++) { if (tab[y][x] == 0) { // Si on tombe sur une case non remplie for (n = 1; n < 10; n++) { if (test(y, x, n)) { // Test les nombres qui peuvent aller dans la case tab[y][x] = n; // Mise à jour du tableau solve(); // On relance la fonction tab[y][x] = 0; // Remise à 0 de la case si mauvais choix } } return; } } } for (int i = 0; i < 9; i++) { // Parcour de chaque case for (int j = 0; j < 9; j++) { printf("%d", tab[i][j]); // Affichage de chaque case } printf("\n"); } exit(0); } int main(){ int i, j; char line[10]; for (i = 0; i < 9; i++) { // Récupération des entrées scanf("%s", line); for (j = 0; j < 9; j++) { tab[i][j] = line[j] - '0'; // Conversion des entrées en caractère } } solve(); return 0; }
Présentation des tests
Afin de coder ce programme et de le valider, il a fallut passer plusieurs tests. Alors voici ci dessous les tests qui m’ont permi de résoudre ce problème.
Test 1
Test 2
Test 1 à 4
Remarques sur les tests précedents
Les tests précedents n’ont rien d’original, il permettent juste de tester l’efficacitée du code dans différents cas, ce qui m’a permi de me rendre compte que le programme n’était pas assez efficace. Malheuresement, je n’arrivais pas à diminuer son temps d’execution.
Je me suis donc aidé de la vidéo de Foxxpy sur Youtube, ce qui m’a permi d’ajouter le exit(0) à la fin de la fonction solve. Ainsi, cela a résolu mes problèmes liés au temps d’execution. Mon programme fonctionnait alors pour chaque test.
Valgrind
Afin d’être certain de ne pas avoir de problèmes de mémoire et autres, que le compilateur n’aurait pas détecté, on utilise valgrind.
valgrind ./sudoku < sudokutest/test4
Cliquez ici pour agrandir
Le programme présenté passe bien valgrind pour tout les tests.
Description d’une autre solution au problème
J’ai choisi de présenter la solution de l’utilisateur JuanMv94 car elle est très différente de la mienne. En effet, elle n’utilise pas de fonction récursive contrairement à beaucoup de solutions que j’ai pu trouver. Son code est donc assez particulier, et n’est présent que dans la fonction principale. On peut tout de même diviser ce code en plusieurs parties qui vont être présentées ci dessous.
Partie 1: Définition de structure
typedef struct { unsigned char val : 4; unsigned char pred : 1; } scell;
Dans cette première partie, l’utilisateur va définir une structure qui servira tout au long de son programme. Elle est composée de deux variables caractère.
Partie 2: Récupération des entrées
scell s[9][9]; // Définition de la grille de sudoku for (int i=0;i<9;i++) { // Boucle qui récupère les entrées for (int j=0;j<9;j++) { s[i][j].val=getchar()-'0'; s[i][j].pred=s[i][j].val?1:0; } getchar(); }
Dans cette seconde partie, l’utilisateur va simplement récupérer les entrées qui sont fournies par le site Codingame.
Partie 3: Boucle principale
int p=0; while(p<9*9) { // Tant que p est inférieur à 81 int i=p/9,j=p%9; if (s[i][j].pred) p++; // Si la case est deja rempli, on passe aux coordonées suivantes else { while (++s[i][j].val<=9) { // Test toutes les valeurs possibles int t; for(t=0;t<9;t++) { int si=i/3*3+(t%3); int sj=j/3*3+(t/3); if ((t!=i && s[t][j].val==s[i][j].val) || (t!=j && s[i][t].val==s[i][j].val) || ((si!=i || sj!=j) && s[si][sj].val==s[i][j].val)) break; // Si le nombre respecte les règles du sudoku } if (t>=9) break; } if (s[i][j].val>=10) { // Si les valeurs déja positionnées ne permettent pas de finir le sudoku s[i][j].val=0; // Alors on les retire et on ré essai do {p--;} while (s[p/9][p%9].pred); } else p++; } }
Cette partie constitue le coeur du programme. C’est elle qui remplace les fonctions récursives qui sont géneralament utilisées dans ce type de problème. Le code se base sur une double boucle while et parcourt les différentes cases du tableau. Il va d’abord détecter si la case que l’on regarde est vide. Si tel est le cas, il testera les différentes valeurs que l’on peut mettre à l’intérieur, grace à diverses conditions. Enfin, si les valeurs deja placées ne permettent pas de finir la grille, alors on revient en arrière et on test d’autres valeurs.
Partie 4: Affichage de la solution
for (int i=0;i<9;i++) { // Affichage de la solution for (int j=0;j<9;j++) putchar(s[i][j].val+'0'); putchar('\n'); } return 0;
Dans cette dernière partie, on utilise simplement une double boucle for afin d’afficher la grille de sudoku résolue.
On retrouve ci-dessous le code complet de la solution de l’utilisateur Juanmv94.
#include <stdio.h> typedef struct { unsigned char val : 4; unsigned char pred : 1; } scell; int main(){ scell s[9][9]; // Définition de la grille de sudoku for (int i=0;i<9;i++) { // Boucle qui récupère les entrées for (int j=0;j<9;j++) { s[i][j].val=getchar()-'0'; s[i][j].pred=s[i][j].val?1:0; } getchar(); } int i, j; char line[10]; for (i = 0; i < 9; i++) { // Récupération des entrées scanf("%s", line); for (j = 0; j < 9; j++) { tab[i][j] = line[j] - '0'; // Conversion des entrées en caractère } } solve(); return 0; for (int i=0;i<9;i++) { // Affichage de la solution for (int j=0;j<9;j++) putchar(s[i][j].val+'0'); putchar('\n'); } return 0; }
Bilan de ce travail
Ce problème m’a permis de redécouvrir le jeu du Sudoku et de comprendre les bases des programmes résolvant les sudoku automatiquement. Cela me sera utile lors d’autres problèmes de ce type, plus complexe, que vous pouvez retrouver sur mon site personnel. Ce puzzle m’a également permi de revoir le principe de récursion, outil très utile en programmation.