dimanche 3 juillet 2022

Résolution de Sudoku en C

Résolution d'une grille de sudoku par la méthode de backtraking (retour sur trace) en langage C.

Les règles du jeu de sudoku classique sont supposées connues (sinon voir Wikipedia/Sudoku).

La plus importante est celle qui dit que chaque chiffre entre 1 et 9, est présent une et une seule fois dans une ligne, une colonne ou une région (sous-grille 3×3).

Remarque

Dans toute la suite l'entrée est un fichier texte au format du fichier sdk-grid1

0 0 0  0 1 7  0 0 0 
0 8 0  0 0 0  5 0 0 
0 1 0  0 0 0  3 0 0 
 
2 5 4  7 0 0  0 0 3 
0 0 0  5 0 2  0 0 0 
3 0 0  0 0 4  2 5 9 
 
0 0 7  0 0 0  0 6 0 
0 0 9  0 0 0  0 1 0 
0 0 0  9 5 0  0 0 0 

où 0 représente une case vide.

Les espaces entre les colonnes et les lignes vides sont facultatifs. Ils ne sont là que pour faciliter la lecture visuelle. Un simple fichier contenant 81 chiffres délimités par un espace ferait l'affaire. Exemple :

0 0 0 0 1 7 0 0 0 0 8 0 0 0 0 5 0 0 ... 0 0 9 0 0 0 0 1 0 0 0 0 9 5 0 0 0 0 

Méthode simpliste

Fichiers source : sdk1.h et sdk1.c (1).

Pour compiler : gcc sdk1.c -o sdk1.

La grille est représentée en mémoire par un tableau de 81 caractères (char). Les 9 premiers pour la première ligne, les 9 suivants pour la deuxième, etc.

Un case vide est notée par le chiffre 0. ('0' en C).

Parce que ça me gonfle de parcourir la ligne, la colonne et le bloc de chaque cellule, à la recherche de doublons, j'ai fait une bonne fois pour toutes un tableau idx[81][20]. Une ligne idx[n] énumère les 20(2)indices des cellules où il faut chercher. C'est la fonction mkidx()(3)qui se charge de cette tâche.

La clé de voute étant une fonction récursive qui teste dans chaque cellule vide tous les chiffres de 1 à 9. Si ça marche on continue, sinon on revient en arrière.

Méthode améliorée

Fichiers : sdk2.h et sdk2.c

L'amélioration de rapidité consiste à :

1. associer à chaque cellule l'ensemble des choix restant disponibles compte tenu des contraintes.
2. construire la liste des indices des cellules ordonnée par le nombre de choix possibles

Ces données sont inscrites à la lecture du fichier de la grille et ne sont pas modifiées par la suite.

Une cellule est alors une structure :

typedef struct sdk
{
	char c; // le chiffre contenu dans la cellule, 0 si elle est vide
	char set[D + 1]; // ensemble des choix possibles dû aux contraintes
	int len; // longueur de l'ensemble
} sdk_t;

On dresse le tableau des indices des cellules à traiter dans int todo[81]; ordonné comme déjà dit.

On est quand même amené à contrôler les contraintes qui s'ajoutent avec les récursions.

Cette méthode est parfois cinq fois plus rapide que la précédente.

Méthode tordue

Fichiers : sdk3.h sdk3.c

Ici, à chaque récursion on recherche la cellule pour laquelle il reste le moins de choix possible avec un codage des chiffres et des ensembles de choix possibles en une représentation binaire.

Déception : malgré tous ces efforts, elle est à peine plus rapide que la méthode précédente sauf éventuellement pour les grilles les plus difficiles où elle se distingue franchement (presque 20 fois plus rapide que la première méthode)

Cadre mathématique

Notations

$C=\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$.

$P(C)$ est l'ensemble des parties de $C$ : $P(C)=\{\emptyset, \{1\}, ... , \{1, 2\}, ... , C\}$. $P(C)$ a $2^9$ éléments.

Définition

σ est la bijection de $P(C)$ dans $\{0, 1, 2, ... , 2^9-1\}$ définie par :

• $σ(\emptyset) = 0$
• $\forall P\in P(E), σ(P)$ est l'entier naturel dont les 9 bits de poids faible sont à 1 si un chiffre appartient à $P$ et nuls sinon (les bits forment en quelque sorte une fonction indicatrice).

Exemples d'images par σ

$σ(\{1\}) = 1$ : $000000001_2$ en binaire.

$σ(\{2, 3, 5\}) = 22$ : $000010110_2$ en binaire.

$σ(C) = 2^9-1=511$ : $111111111_2$ en binaire.

Propriétés

L'image d'un singleton $\{c\}$ par σ est une puissance de 2 : $σ(\{c\})=2^c-1$.

Mise en œuvre en C

Grille

Un grille de sudoku est traduite en un tableau à une dimension de longueur 81 :int g[81]; de la façon suivante :

• Si une case est vide alors g[n] = 0;
• Sinon, si elle contient un chiffre c, alors g[n] reçoit l'image de c par σ.

g[n] = c ? 1 << (c - 1) : 0;

Avec ce codage une cellule contient un nombre qui désigne soit un chiffre soit un ensemble de chiffres :

• C'est un chiffre unique si le nombre est une puissance de 2.
• C'est un ensemble autrement

Ensemble des choix possibles

Pour une cellule vide donnée, l'ensemble $P$ des possibiltés de choisir un chiffre est l'ensemble des chiffres de 1 à 9 qui ne figurent pas dans sa zone d'exclusivité. $P$ est codé avec un nombre $bs$ utilisant le concept vu dans le paragraphe Grille. Le bit $b$ sera annulé si l'on rencontre le chiffre de rang $b - 1$. On initialise $bs$ avec $0$ (ensemble vide), on ajoute les chiffres rencontrés avec bs |= x puis on fait l'opération de complémentation 511 & \~bs. C'est là que réside l'intérêt de ce codage. Voir la fonction possibles dans le source sdk.c. Par rapport aux fonctions de string.h c'est nettement plus rapide.

Parcours de la grille

Une fonction int next(int *g) permet de calculer à chaque récursion l'indice de la cellule à laquelle il reste le moins de choix possibles.

Conclusion

Finalement la méthode 2 est un bon compromis entre vitesse d'excécution et simplicité de mise en œuvre.

Version html css js

Pour finir deux versions html à afficher dans un navigateur.

Version hybride avec un code C adapté

Le fichier sdk.html est un fichier simple avec du html, du css et du javascript qui produit sur un navigateur l'affichage d'une grille de sudoku et sa solution (par la première méthode). Il est statique car il n'affiche qu'une grille et sa solution.

Le fichier sdk-html.c permet de contourner la lecture d'un fichier en javascript. Il va modifier dans le fichier sdk.html les lignes :

let g = new Array(0, 0, 0, 0, 0, 3, 2, 0, ... , 0, 0, 0, 0, 2, 0, 0, 0);
let s = new Array(6, 8, 1, 9, 7, 3, 2, 4, ... , 1, 4, 9, 7, 6, 2, 5, 8, 3);

par les nouvelles valeurs de tableaux qu'il a lu et résolu.

L'algorithme est simple. On lit le fichier sdk.html, ligne par ligne qu'on recopie dans un fichier temporaire sdk.tmp. Cette recopie s'arrête dès que l'on renconctre une ligne qui commence par let g . On saute la ligne suivante. On insère dans le fichier temporaire les tableaux de la nouvelle grille et de sa solution. Puis on finit en recopiant le reste. Il ne reste plus qu'à supprimer le fichier sdk.html et renommer le fichier temporaire.

Ainsi pour changer de grille pendant que sdk.html est affiché on lance dans une console :

sdk <nouvelle grille> 

puis on rafraîchit la page.

Ce qui m'a incité à écrire ces codes, c'était le défi du css d'une grille de sudoku. Quand on est retraité et qu'on a rien d'urgent à faire, on s'occupe comme on peut.

Pour voir le résultat cliquez sur sdk.html.

Version javscript

Fichiers :

• sdk-js.html le fichier html
• sdk.js le code source principal
• grid.js contenant une ligne de définition de la grille
• sdk.sh un script bash pour produire le fichier précédent à partir d'un fichier texte. C'est une sorte de «back-end» pour se passer de php ou de node.js.

La différence avec la méthode hybride est qu'on se passe du fichier C, et on fait tout en js.

Pour voir le résultat cliquez sur sdk-js.html.

Notes