SUDOKU - Methode de résolution du sudoku sur www.Sudoku-land.com.

Règles et terminologie

La plupart du temps, le puzzle est proposé sous la forme d'une grille de 9×9, et composé de sous-grilles de 3×3, appelées « régions ». Quelques cellules contiennent des chiffres, dits « dévoilés ». Le but est de remplir les cellules vides, un chiffre dans chacune, de façon à ce que chaque rangée, chaque colonne et chaque région soient composées d'un seul chiffre allant de 1 à 9. En conséquence, chaque chiffre dans la solution apparaît une seule fois selon les trois « directions », d'où le nom « chiffre unique ». Lorsque qu'un chiffre peut s'inscrire dans une cellule, on dit qu'il est candidat.

Voir la vidéo présentant les règles de base du sudoku.

Méthode de résolution

La résolution de ce casse tête utilise conjointement 3 processus différents : la recherche, la candidature et l'analyse.

La recherche

Voir la technique de la recherche en images

La recherche est faite au début du jeu et périodiquement pendant le remplissage de la grille. Plusieurs recherches sont souvent nécessaires entre deux moments d'analyse. Cette recherche fait appel à deux techniques simples :

Réduction par croix : il s'agit, pour chaque chiffre, d'éliminer les cellules où il ne peut pas se trouver. Pour cela, le chercheur trace un trait, imaginaire, sur chaque colonne et chaque ligne où le chiffre apparaît déjà. Les cases qui ne sont pas traversées par un trait sont celles où le chiffre peut encore être inséré. Cette méthode peut être utilisée pour remplir les cellules « les plus simples » en premier. Pour gagner du temps, le chercheur peut commencer par les chiffres les plus nombreux parmi les dévoilés, mais il est important de l'appliquer à chaque chiffre. Pour minimiser le temps de recherche aux autres étapes, cette étape doit être faite de façon systématique, en vérifiant pour tous les chiffres.

La région en haut à droite doit contenir un 5. En éliminant les rangées et les colonnes en regard qui contiennent un 5, le joueur élimine toutes les cellules vides qui ne peuvent contenir ce 5. Il ne reste donc qu'une seule cellule d'accueil, en vert.

Décompte de 1 à 9 pour chaque région, chaque rangée et chaque colonne. Cette étape permet de trouver les chiffres manquants. (Le faire selon le dernier chiffre trouvé peut rendre plus rapide la recherche.) Dans les puzzles difficiles, le chiffre à inscrire peut être déterminé en faisant un décompte inversé, c'est-à-dire en tentant de trouver les chiffres qui ne peuvent apparaître dans la cellule, ce qui permet de connaître les chiffres candidats.

Les joueurs experts recherchent les « contingences » pendant la recherche, c'est-à-dire qu'ils tentent de déterminer les cellules candidates (au nombre de deux ou trois) pour un chiffre en particulier. Quand ces cellules sont toutes dans la même rangée (ou colonne), et une région, elles sont mises à profit pendant la réduction par croix et le décompte. Les puzzles les plus difficiles demandent de reconnaître les multiples contingences, souvent dans des directions différentes ou aux intersections. Ce qui oblige les joueurs à inscrire les candidats (méthode décrite ci-dessous).

Les puzzles que l'on peut résoudre par la réduction par croix seulement sont considérés comme faciles, les plus difficiles exigent de faire appel à d'autres techniques.

Candidature

Voir la technique de la candidature en images

La recherche cesse lorsqu 'aucun nouveau chiffre n'est inscrit. C'est à partir de ce moment qu'une autre technique doit prendre place. Plusieurs joueurs trouvent utiles d'inscrire les chiffres candidats dans les cellules vides. Il y a deux notations utilisées : indicée et pointée.

Pour la notation indicée, les candidats sont inscrits dans une cellule, chaque chiffre occupant ou non une place précise. L'inconvénient de cette méthode est que les journaux publient des grilles de petite taille, ce qui rend difficile l'inscription de plusieurs chiffres dans une même cellule. Plusieurs joueurs reproduisent à plus grande échelle de telles grilles ou ont recours à un crayon à pointe fine.

Pour la notation pointée, les joueurs inscrivent des points dans les cellules vides. La position relative du point indique le chiffre manquant. Par exemple, pour indiquer 1, un point apparaît en haut à gauche dans la cellule. Cette notation permet de jouer directement avec une grille imprimée dans un journal. Cependant, elle demande une certaine dextérité, il est possible de mal placer un point dans un moment d'inattention et une petite marque faite par erreur peut mener à de la confusion. Certains joueurs préfèrent utiliser un stylo pour limiter les fautes.

Un exemple de notation pointée

L'analyse

Voir la technique de l'analyse en images

Les deux thèmes de ce procédé sont l'élimination et l'hypothèse.

Élimination : la recherche de la solution se fait en éliminant successivement les candidats d'une cellule de façon à ne retenir qu'un seul candidat. Une fois ce candidat trouvé, une autre recherche devrait être effectuée de façon à déterminer les conséquences sur les autres cellules. Il y a plusieurs techniques d'élimination qui s'appuient sur les règles ci-dessous, lesquelles ont d'utiles corollaires :
Un ensemble donné de n cellules dans une rangée, une colonne ou une rangée, ne peut recevoir que n chiffres différents. Cette règle est à la base de la technique d' « élimination du candidat orphelin », discutée ci-dessous.
Chaque candidat doit ultimement appartenir à un modèle auto-consistant et indépendant. Cette règle est à la base des techniques d'analyse avancées, lesquelles demandent d'inspecter l'ensemble de toutes les possibilités pour un candidat. Il n'y a qu'un nombre fini de « circuits fermés » ou possibilités de grilles « n×n » qui existent. Si un tel modèle est identifié, alors l'élimination de candidats est souvent possible.
L'une des techniques les plus utilisées est l' « élimination du candidat orphelin ». Les cellules avec un même ensemble de candidats sont dites couplées si le nombre de candidats dans chacune d'elle est égal au nombre de cellules qui peuvent les accueillir. Par exemple, deux cellules sont couplées si elles contiennent une paire unique de candidats (p,q) dans une rangée, une colonne ou une région; trois cellules sont dites couplées si elles contiennent un triplet unique de candidats (p,q,r). Ces chiffres ne peuvent apparaître ailleurs, car il y aurait conflit selon la rangée, la colonne ou la région. Pour cette raison, les candidats (p,q,r) qui se trouvent dans les autres cellules sont à éliminer. Ce principe vaut avec des sous-ensembles de candidats : si trois cellules ont seulement { (p,q,r), (p,q), (q,r) }, ou { (p,r), (q,r), (p,q) }, tous les candidats de cet ensemble qui se trouvent dans les autres cellules sont à éliminer.
Un deuxième principe découle du principe précédent. Si le nombre de cellules dans une rangée, une colonne ou une région, est égal à la taille d'un ensemble de candidats, les cellules et les chiffres sont couplés et seulement ces chiffres apparaîtront dans les cellules. Tous les autres candidats sont à éliminer. Par exemple, si (p,q) peut seulement apparaître dans deux cellules (d'une rangée, d'une colonne ou d'une région), les autres candidats sont à éliminer.
Le premier principe s'appuie sur le concept de « chiffres couplés uniquement », alors que le second s'appuie sur le concept de « cellules couplées uniquement ». Les techniques avancées s'appuient sur ces concepts et englobent de multiples rangées, de multiples colonnes et de multiples régions.
Avec l'approche par hypothèse, une cellule avec seulement deux candidats est choisie et l'un des deux chiffres est inscrit dans la cellule. Les étapes précédentes sont répétées et mènent soit à une contradiction (chiffre dupliqué ou cellule sans candidat), soit à une proposition valide. Évidemment, dans le cas d'une contradiction, le deuxième chiffre fait partie de la solution. L'algorithme de Nishio est une forme épurée de cette approche : Pour chaque candidat d'une cellule, est-ce qu'insérer un chiffre en particulier prévient l'inscription de ce candidat ailleurs dans la grille ? Si la réponse est oui, alors le candidat est éliminé.
L'approche par hypothèse demande d'utiliser un crayon et une gomme à effacer. Les puristes la rejettent, car elle est une approche par essais et erreurs, alors que la plupart des grilles publiées font appel à la logique seulement pour être résolues. Cependant, cette approche a le mérite de souvent mener à la solution plus rapidement.

C'est à chaque joueur de trouver une méthode qui lui donne les meilleurs résultats. Certains développeront une méthode qui réduisent les inconvénients des propositions précédentes. Par exemple, certains trouveront ennuyeux de devoir inscrire tous les candidats dans toutes les cellules. L'approche par hypothèse demande d'être organisé. L'idéal est de trouver une façon de faire qui minimise le décompte, le nombre de candidats et le nombre d'hypothèses.

Article de Wikipédia, l'encyclopédie libre.

Page d' Accueil | Signaler un bug | Plan du Site | Webmaster | Livre d'or