Le site de DarkOli - Programmation - Sudoku
Sudoku
J'ai découvert les Sudokus grâce au journal 20 minutes qui en publie un chaque jour depuis le 7 novembre 2005. Je ne vais pas faire une présentation détaillée car cela est très bien fait sur Wikipédia. Il existe beaucoup d'autres sites traitant du sujet. J'ai eu l'impression, après avoir fait quelques recherches avec google, que tout le monde connaissait les sudokus sauf moi !
Les premiers sudokus proposés par le journal "20 minutes" sont très simples. Il est possible de les résoudre en utilisant des raisonnements logiques basiques. Mais pour deux sudokus (sur les 9 que j'ai pu me procurer) il est nécessaire de tester plusieurs solutions avant d'en arrvier à bout (sudokus #3 et #4). Malheureusement certains sudokus n'ont pas de solution unique (sudokus #3, #4 et #7).
Pour vérifier les sudokus que je remplissais, j'ai écris un petit programme (en C) qui les résouds. Pour cela j'ai codé trois méthodes différentes.
Pour illustrer les explications que je donne ci-dessous je vais utiliser un sudoku que j'ai repris du journal "20 minutes" du 02/12/2005. C'est le 19° sudoku publié par ce journal, il est typé "difficile".
Numérotation : les lignes sont numérotées de 1 à 9 de haut en bas. Pour les colonnes il en est de même mais de gauche à droite. Enfin les régions sont aussi numérotées de 1 à 9, de la façon suivante :
Méthode des candidats : pour chaque case vide je liste tous les candidats possibles. Au départ je considère que tous les chiffres sont candidats, puis je retire les chiffres qui sont sur la même ligne, puis ceux qui sont sur la même colonne et enfin ceux qui sont dans la même région. S'il n'en reste qu'un seul et bien c'est la solution. Cette méthode est très simple à programmer.
Cette méthode n'est pas très efficace pour cet exemple car il est possible de mettre à jour une case seulement ! Je désire lister les candidats possibles pour la case 4,4 (case avec un point d'interrogation). Au départ tous les candidats sont possibles. Puis je retire les chiffres déjà présents sur la quatrième ligne (en vert). Il me reste les candidats de 2, 3, 4, 5, 6 et 8. Puis je retire aussi les chiffres présents sur la 4° colonne (en brun). Il me reste donc les candidats 4 et 8. Les chiffres 1 et 8 sont dans la région #5 (en bleu), ils ne peuvent donc pas être candidat. Finalement, seul le chiffre 4 peut être candidat pour la case 4,4. Cette méthode peut être utilisée à l'envers, c'est à dire en listant directement les chiffres qui n'apparaissent ni sur la ligne, ni sur la colonne ni dans la région qui correspondent à la case à mettre à jour.
Méthode des possibilités : pour une région donnée, je liste les cases dans lesquelles je peux mettre le chiffre 1 (je ferai la même chose avec les autres chiffres plus tard) en éliminant les cases qui appartiennent à une ligne où se trouve déjà le chiffre à placer. Parfois il est possible d'éliminer deux lignes sur les trois que compte la région. Dans cette situation, il ne reste que trois cases possibles pour le chiffre. Si une seule est vide nous pouvons y placer notre chiffre. Si ce n'est pas suffisant je fais de même avec les cases qui appartiennent à une colonne où se trouve déjà le chiffre à placer. S'il ne reste plus qu'une seule case vide possible et bien c'est la solution. Cette méthode est très simple à appliquer par un humain !
Cette méthode fonctionne parfaitement pour cet exemple, il est possible de le remplir entièrement uniqement à l'aide de celle-ci. Prenons par exemple le chiffre 1. La première région contient déjà ce chiffre nous passons donc à la deuxième région. Il y a déjà un 1 sur les lignes 5 et 6 donc le 1 ne peut se trouver que sur la ligne 4. Il n'y a qu'une seule case vide donc elle ne peut contenir que le chiffre 1. Si un autre chiffre est utilisé pour occuper cette case, le sudoku serait faussé puisqu'il serait alors impossible de trouver une case valide pour le chiffre 1 dans cette région.
Méthode "force brute" : la première étape consiste à lister pour chaque case vide tous les candidats possibles. Ensuite il suffit de tester toutes les possibilités. Manuellement cette méthode est très laborieuse alors qu'un ordinateur n'aura aucun problème à faire "bêtement" des millions de tests.
Le programme C
À FAIRE : explication du code pour chacune des trois méthodes ...
Comment créer des sudokus ?
À FAIRE : solution unique, faut-il partir d'un sudoku complet puis retirer des chiffres un à un, combien faut-il en retirer ?
La page respecte le standard XHTML 1.0 Strict.
-- Darkoli, dernière mise à jour le 11 décembre 2005 [21:11] --
