Sudoku est un utilitaire "ligne de commande" (console) qui permet de résoudre ou créer des grilles de Su-do-ku.

J'ai écrit ce programme en C. Il est compilable sous MS-DOS (Turbo-C) ou Unix (cc).

Source: sudoku.c

Exécutables: sudoku.exe (pour Windows) et sudoku pour Mac OS X.

Une grille de Su-do-ku est une grille de 9x9 cases, qu'il faut remplir avec des chiffres de 1 à 9 de telle manière à ce qu'il n'y ait aucun double dans chacune des 9 lignes, colonnes, ou régions. On appelle régions les carrés de 3x3 cases (la grille est donc divisée en 9 régions).

Pour la résolution, on procède donc par élimination et déduction, et on comble les cases vides de proche en proche.

Il y a 3 niveaux de difficulté dans les grilles, en fonction du nombre de cases connues:

• facile: plus de 32 cases connues
• moyen: 29, 30 ou 31
• difficile: moins de 28

Il y a même un 4ème niveau (diabolique), selon qu'on est amené à poser des hypothèses. En effet, une grille ayant peu de valeurs connues ne permet pas de trouver la solution, on est bloqué car toutes les cases vides restantes acceptent plus d'une valeur. On est alors obligé de décider arbitrairement d'une valeur (on fait une hypothèse), et on peut alors continuer à résoudre, jusqu'à résolution, ou nouveau bloquage, ou contradiction. Dans ce dernier cas, on reprend à l'hypothèse (on est alors obligé de gommer toutes les cases trouvées depuis) et on fixe une autre valeur. Dans le cas d'un nouveau bloquage, on peut être amené à poser une hypothèse supplémentaire, etc... Plusieurs niveaux d'hypothèses peuvent alors se superposer. Attention, ne pas confondre niveau d'hypothèse et niveau (de difficulté).

Le site www.websudoku.com propose des millions de grilles de ces 4 niveaux de difficulté.

La méthode de résolution est la suivante. On ne fixe une valeur que lorsqu'on en est sûr:

- élimination: pour chaque case vide, on élimine les valeurs possibles en regardant sa ligne, colonne et région. S'il ne reste plus qu'une valeur, c'est celle-ci. S'il y a 0 valeur, le problème est impossible (sauf si on a posé une hypothèse, il faut alors en changer).

- déduction: parmi les valeurs possibles qu'une case peut prendre (après élimination), il peut y en avoir une qui n'apparaît qu'une seule fois dans la ligne, colonne ou région. La case doit donc avoir nécessairement cette valeur. Souvent cette méthode permet de débloquer lorsque la méthode d'élimination ne donne plus rien.

Pour résoudre une grille, on alterne donc successivement entre ces 2 phases ou passes. On appelle tour l'ensemble de ces 2 passes.

Si aucune des 2 méthodes ne donne plus rien et que la grille n'est pas terminée, il faut alors faire une hypothèse. Ce n'est que dans le cas de grilles très difficiles, très rares en su-do-ku, car énervent la plupart des gens.

- hypothèse: on choisit de préférence parmi les cases vides n'ayant que 2 valeurs possibles. Ainsi, si on arrive à une contradiction, on sera sûr que ce sera la 2ème valeur qui est la bonne. On écrit au crayon les valeurs calculées à partir de cette hypothèse, qui seront donc faciles à gommer si on arrive à une impossibilité. On repasse au stylo dès qu'on en est sûr. Si on doit faire plusieurs niveaux d'hypothèses, il faut distinguer les cases calculées avec ce 2ème niveau afin de les effacer, sans effacer celles du 1er niveau. Vous voyez que ce n'est pas simple.

Une case est repérée par sa ligne et colonne.

Exemple: case (3,5) signifie 3ème ligne à partir du haut, 5ème colonne.

On peut repérer les régions de manière similaire. Par exemple, les 3 régions du bas de la grilles sont (3,1), (3,2) et (3,3).

On peut soumettre des grilles à résoudre à l'utilitaire sudoku de 3 manières différentes:

• entrée clavier
• fichier texte
• grille prédéfinie

Pour l'entrée clavier, répondre 0 à la 1ère question, et entrer les lignes de la grille une par une, en mettant des blancs pour les cases vides.

Exemple:
Ligne 1: 123456789
Ligne 2: 3 56 8
etc...

Pour une grille prédéfinie: il y a 25 grilles définies en dur dans le programme, réparties en 5 niveaux: facile, moyen, difficile, diabolique, inconnu.

Donner un nombre de 1 à 5 pour ce niveau de difficulté, puis de 1 à 5 pour le numéro de grille.

On peut directement appeler par exemple la 3ème grille du niveau moyen avec la commande:

Vous pouvez aussi saisir tranquillement une grille à soumettre dans votre éditeur de texte favori.

Ecrire les valeurs comme on les entrerait au clavier. On peut écrire des commentaires après la fin de la grille, ou en fins de lignes, ou dans des lignes commençant par #.

Si la 1ère ligne contient ---, elle est sautée et indique que chaque case occupera 2 espaces. Ainsi on peut recycler des grilles affichées (par exemple lors du mode création - voir plus loin). Exemple:

|------------------|
| 2         4   6 9|
| 1         6   4  |
|   4         7    |
|         3   8 5  |
| 8 1     2        |
| 9                |
|     7 1         2|
|           2 3   4|
| 5   2            |
|------------------|
Niveau estime: difficile (24 cases connues)

Si on appelle ce fichier toto.txt, on lance la résolution avec:

Les cases calculées s'affichent en couleur pour les distinguer des cases données:

• bleu: case calculée par élimination
• magenta: case calculée par déduction
• jaune: case calculée par hypothèse
• blanc: case donnée initialement

Dans le cas des cases jaunes, on distingue celles de départ d'hypothèse (jaune vif) de celles calculées à partir (jaune).

Exemple: sudoku 2 3

Niveau: moyen (29 cases connues)
Resolu en 2 tours (11 passes)
|------------------|
| 8 1 5 3 2 7 9 4 6|
| 6 9 3 8 4 5 2 1 7|
| 4 7 2 6 1 9 8 3 5|
| 3 2 1 7 8 6 5 9 4|
| 5 6 4 1 9 2 3 7 8|
| 7 8 9 5 3 4 6 2 1|
| 9 4 8 2 5 1 7 6 3|
| 1 3 6 9 7 8 4 5 2|
| 2 5 7 4 6 3 1 8 9|
|------------------|

Remarque: pour que la grille s'affiche en couleur dans une fenêtre d'invite de commande MS-DOS sous Windows, il faut que le fichier C:\config.sys contienne la ligne:

(redémarrer Windows)

La grille s'affiche aussi dans une page Web (format HTML): sudoku.htm, dans le répertoire courant. On peut ainsi l'imprimer :

On peut examiner chaque étape de résolution en mettant l'option -v ou -p.

L'option -p permet de faire une pause clavier (taper Entrée) à chaque étape. L'option -v affiche tout, mais ne s'arrête pas. On peut rediriger la sortie vers un fichier ou un pipe. Exemple:

(on ajoute l'option -n pour pas que les couleurs s'affichent; en effet, elles sont sous la forme de séquences Escape et nuisent à la lisibilité de la grille)

L'option -p est pratique, car elle permet de débloquer une grille que vous résolvez par vous-même sur un magazine si vous êtes bloqué. En effet, vous pouvez avoir manqué une valeur dans votre raisonnement, et cette option affiche chaque case résolue, dans l'ordre.

Pour avoir la syntaxe et toutes les options, taper
sudoku/?
ou bien:
sudoku -h

S'affiche alors la syntaxe:

Resolution ou creation de grilles de SU-DO-KU

Syntaxes:
  sudoku [-v|p|m] [-i] [-n] [-h n] [-t n] [-f fichier | [niveau] [num_grille]]
  sudoku -s [-f fichier | [niveau] [num_grille]]
  sudoku -c [niveau | nb_cases_connues]
Grille a resoudre dans un fichier texte, ou grilles internes (niveau: 1 a 5)
Options:
 -v : montre chaque etape de resolution.
 -p : fait une pause clavier a chaque etape de resolution.
 -m : completement muet
 -n : sans les couleurs (utile pour redirections)
 -f : lit la grille depuis un fichier texte.
 -i : insiste dans Phase 2 de resolution autant que dans Phase 1
 -h n : s'efforce de ne pas poser plus de n hypotheses simultanees
 -t n : modifie le nombre de tours maximum pour trouver (def: 1000); 0=infini
 -s : ne cherche pas la solution (utile pour imprimer)
 -c : cree une grille automatiquement
Voir:
  sudoku.doc pour une documentation (format RTF)
  http://www.websudoku.com pour des millions de grilles.

L'option -i permet d'insister dans la phase de déduction. En effet, par défaut, la phase de déduction ne sert qu'à débloquer lorsque la phase d'élimination ne donne plus rien. L'option -i permet de reboucler la phase de déduction tant que celle-ci donne des résultats (comme pour la phase d'élimination). L'avantage est que la solution tombe au bout d'un nombre moindre de tours, mais c'est moins naturel.

L'option -h permet de forcer à rester à un faible niveau d'hypothèse. Par défaut, lors de la résolution d'une grille très dure, le programme fixe la 1ère case candidate à une hypothèse, qui n'est pas forcément la plus directe (le programme peut en effet être amené à poser d'autres hypothèses). L'option -h permet de rester à un niveau. Exemple:

Ça forcera à invalider l'hypothèse posée si celle-ci doit amener à poser d'autres hypothèses, et le programme fixera donc l'hypothèse à la case candidate suivante. En étant trop exigeant, le problème peut bien sûr ne pas avoir de solution.

Par exemple la grille suivante:

|------------------|
|                 5|
| 8 4       5 6    |
| 1     4     3    |
|     9       1    |
|   6 2   7 1     3|
|         5        |
|   5     8     9  |
|             4    |
|   2     1 7      |
|------------------|
Niveau estimé: difficile (24 cases connues)
soluble avec 4 hypothèses ou 1
si (1,5)=9, soluble directement

Dans ce cas, l'option -h 1 forcera à trouver que la case (1,5) vaut 9.

À noter que cette dernière grille peut avoir plusieurs solutions différentes. En toute rigueur, ce n'est pas une vraie grille de Su-du-ko. En effet, même si on doit poser des hypothèses, une grille de Su-do-ku ne doit avoir qu'une solution possible.

Par défaut, la résolution affiche quelques informations, par exemple lorsqu'on est obligé de poser des hypothèses. L'option -m (mode muet) permet de désactiver tout affichage (sauf celui de la solution).

Par défaut, le nombre de tours lors de la résolution est limité à 1000 (on abandonne et on dit qu'il n'y a pas de solution). On peut modifier ce nombre avec cette option. Si on met -t 0, le programme cherche indéfiniment tant qu'il n'a pas trouvé. Exemple:

Cet exemple cherche sans limite de nombre de tours la grille n°6 de difficulté diabolique (niveau 4), mais en limitant le nombre d'hypothèses simultanées à 5. On met en mode "muet" car l'affichage est énorme et ralentit la résolution.

Taper:

et ça crée une grille à résoudre.

La grille créée par défaut est de niveau difficile: elle est soluble sans avoir à poser d'hypothèse, mais le nombre de cases connues est faible.

En d'autres termes, si on s'amuse à supprimer n'importe quelle case, le programme sera amené à poser des hypothèses (aucune case n'est redondante).

Pour rendre la grille plus facile (ajout automatique de cases de la solution), ajouter le niveau ou le nombre de cases connues souhaité. Exemples :

sudoku -c 2     (crée une grille de niveau moyen)

sudoku -c 35    (crée une grille de 35 cases connues, niveau facile)

La grille s'affiche à l'écran, mais aussi dans un format imprimable: sudoku.htm :

Le programme crée une grille aléatoirement, on ne retombera donc jamais sur la même grille, recommencer autant de fois que vous voulez jusqu'à adopter une grille.

La grille créée est aussi dans un fichier texte: sudoku.log :

|------------------|
|     1         3 4|
|   7     1 9 6 5  |
| 5     4 8 7      |
|         7 4     9|
|     7 5 9   2    |
| 3     1 2 6   7  |
|     2 6     9   7|
|           8 4 2  |
| 6   8       5   3|
|------------------|

ce qui permet de lancer la résolution:

(attention, la solution sera aussi dans le .htm; pour retrouver le sudoku.htm vierge afin de le réimprimer, utiliser l'option -s avec sudoku.log -voir ci-dessous).

Pour imprimer une grille, la grille initiale ou la grille solution se trouve dans le fichier sudoku.htm.

Ouvrir ce fichier en double-cliquant dessus sous l'explorateur, ça lance l'impression couleur.

Pour l'ouvrir on peut aussi taper, dans la fenêtre MS-DOS:
start sudoku.htm
ou sous fenêtre Terminal de Mac OS X:
open sudoku.htm

Cette option permet d'avoir la grille initiale comme version imprimable en mode résolution.

Exemples:
sudoku -s 4 4
sudoku -s -f toto.txt
sudoku -s -f sudoku.log

Le sudoku.htm produit est alors la grille brute, non résolue.

Pour chaque case vide, on élimine les valeurs possibles en regardant la ligne, colonne et région. Si une seule valeur reste, on fixe la case à cette valeur. Après avoir fait toute la grille, on recommence au début tant qu'on a eu des résultats.

Pour chaque ligne, colonne et région, on regarde les valeurs possibles des cases vides. Si une valeur n'apparaît qu'une fois, on la fixe. Après avoir fait tout fait, on recommence au début tant qu'on a eu des résultats et si l'option -i est activée.

On boucle entre ces 2 passes tant qu'on a eu des résultats dans une des passes, et tant que la grille n'est pas terminée.

Si un tour ne donne aucun résultat, on cherche d'abord les cases candidates pour poser une hypothèse: parmi celles qui ont le moins de valeurs possibles. On incrémente le niveau d'hypothèse (il passe de 0 à 1), on fixe la valeur de la case choisie (la 1ère candidate). Toutes les valeurs calculées par la suite auront ce niveau d'hypothèse. On note aussi, pour ce niveau d'hypothèse, la case qu'on a fixée et à quelle valeur (dans un tableau indexé par le niveau d'hypothèse).

Si on arrive à une impossibilité (case vide à 0 valeur possible), on efface toutes les valeurs calculées à partir de l'hypothèse, y compris l'hypothèse de départ, et on passe à l'hypothèse suivante: valeur suivante de la case, ou case suivante (seulement dans le cas de l'option -h). On se repère grâce au tableau.

Lorsqu'on a épuisé toutes les hypothèses, on efface l'hypothèse précédente (sauf s'il n'y en a pas, auquel cas la grille est impossible).

Par ailleurs, on se fixe aussi un total limite de tours (1000) à partir duquel on abandonne la recherche de la solution (souvent trop d'hypothèses à poser, grille vraiment trop lâche).

D'abord, on crée aléatoirement une grille avec 2 séries de chiffres 1 à 9, de telle manière à ce qu'il n'y ait aucun double dans chaque ligne, colonne et région.

On résout cette grille. Nécessairement, il y aura des hypothèses. Très rarement, la grille sera impossible (auquel cas on en recrée une).

On repart ensuite de cette grille initiale, qu'on enrichit avec 1 case de la solution, puis 2, etc... jusqu'à tant qu'on n'ait plus besoin de poser des hypothèses pour résoudre.

Ensuite on épure cette grille: on supprime (aléatoirement) des valeurs tant que la grille reste soluble sans poser d'hypothèse. Le résultat est une grille de niveau "difficile" (22 à 27 cases connues).

Ensuite, éventuellement, le programme ajoute autant de cases de la solution qu'il le faut pour arriver à un niveau de facilité souhaité (nombre de cases connues, ou niveau).

Le programme évite la difficulté de créer des grilles solubles par hypothèses, car il faudrait être sûr que la solution est unique (faisable mais long à implémenter puis à calculer, en projet...).