SUDOKU

La réduction des candidats

fj — 2007-08-06T23:21:14Z

A l'issue de l'étape 3 (approche globale), normalement toute la grille est remplie et les cases contiennent généralement de 1 à 4 candidats (quelques cases peuvent exceptionnellement soit rester vides, soit contenir plus de 4 candidats)

En général, je laisse vides les cases associées à des listes trop longues car une case de plus de 4 candidats n'apporte aucune information utile.

Quand l'approche globale est bloquée ou quand le diagramme est rempli de listes de candidats mais où rien ne semble se décanter, voici quelques techniques utiles à connaître :

le report de marque : cela ressemble au balayage mais l'objectif est plus modeste, il s'agit simplement de compléter les marques de proximités (dans les régions) en examinant les lignes et colonnes. C'est très souvent la solution miracle !

le XY-Wing : c'est une technique finalement assez simple pour réduire la taille des listes de candidats,

le marquage à distance : la démarche ressemble au report de marque mais il s'agit maintenant de repérer des duos de candidats identiques par ligne ou colonne qui ne sont pas dans la même région (sinon ce serait justement un report de marque). Le marquage à distance est une excellente technique pour trouver des X-Wing voire même des Swordfish. Par contre, j'ai renoncé à rechercher les extensions diverses (Jellyfish, Squirmbag ...). La théorie n'est pas si compliquée que cela mais la recherche du motif en question me semble inextricable.

le double pari. C'est une technique souvent très efficace mais il faut bien choisir le couple de départ. Certains pensent que cette technique est à proscrire. C'est tout à fait faux naturellement et elle est beaucoup plus subtile qu'il n'y parait quand on mène vraiment les deux paris contraires en parallèle : même si on ne parvient pas à déterminer quel est le bon choix, on réussit souvent :
- à effectuer des placements inattendus (quand les deux paris sont d'accord),
- à supprimer des candidats (quand les deux paris les refusent).

Exploitation des particularités géométriques

fj — 2007-08-01T00:11:09Z

Cette étape est facultative si l'étape 1 s'est bien déroulée.

Mais il arrive parfois que l'étape 1 ne permette pas d'effectuer beaucoup de placements définitifs. Or, quand il y a moins de 30 cases résolues, l'approche globale est souvent difficile, voire inefficace. Il faut compléter la grille par d'autres moyens avant que l'approche globale ne puisse démarrer.

Cette étape numéro 2 est l'application d'une série de techniques visant à trouver des placements nouveaux, ou au moins des cases remplies de listes courtes de candidats.

Attention : durant cette étape, vous devez appliquer scrupuleusement la règle suivante : toute case commencée doit être terminée, même si vous vous apercevez soudain qu'il y a beaucoup trop de candidats à y placer. Tant pis : mieux vaut trop que pas assez ! Je ne compte plus le nombre de SUDOKU que j'ai sabotés simplement parce qu'une case était incomplète.

Si vous avez saboté un SUDOKU (sur papier), alors il n'y a guère qu'un seul conseil valable : reprenez le à zéro (en recopiant la position de départ sur une feuille quadrillée) car il est rarissime qu'on arrive à réparer l'erreur.

Voici les techniques à appliquer quand l'approche globale ne peut pas démarrer (par ordre de priorité) :

le placement direct : recherche des cases à liste de candidats courte (au plus trois candidats), l'objectif avoué étant de trouver des placements directs et à défaut de mettre en évidence des doublés ou des triplés ; j'appelle cette technique La pêche au gros,
l'examen des points d'intersections des rangées à doublon ou triplé avec celles où des placements ont déjà été effectuées (il faut se souvenir des caractéristiques géométriques principales de la grille),
le bouchage de trous ,
Le balayage des lignes et colonnes : analyse ligne par ligne et candidat par candidat puis colonne par colonne et candidat par candidat. C'est le pendant de l'étape 1 (région par région et candidat par candidat) mais appliqué aux lignes et aux colonnes. En général, c'est assez pénible à effectuer c'est pourquoi j'ai mis cette technique en dernier.

Prenons un exemple concret où il n'est pas si facile de choisir entre l'étape 2 (exploitation géométrique) et l'étape 3 (analyse globale) :

Il s'agit ici de la position obtenue après l'étape 1. Cette dernière semble s'être plutôt bien passée puisque l'alignement h1 est pratiquement résolu. Pourtant ce n'est pas si simple : il n'y a pas de zone à 2 ou 3 trous où pourrait commencer l'approche globale. Même les zones à 4 trous sont rares (région 5 et colonne H). Enfin, deux régions sont très peu remplies (R4 et R6) ...

Dans une position de ce genre, il faut rechercher des placements supplémentaires. Même un joueur moyen devrait être capable de repérer rapidement la case G6 :

4 candidats sur la ligne 6,
trois candidats supplémentaires différents sur la colonne G,
un 8ème candidat dans la région R6 (le 6).

Notez au passage qu'il ne faut pas oublier les conséquences sur marques de choix supplémentaires du 8.

Ceci dit, le résultat obtenu ne résout pas grand chose. L'approche globale est toujours trop précoce bien qu'une nouvelle zone à 4 trous soit apparue : la ligne 6. Objectivement, il serait cependant possible et correct de compléter dès maintenant la région R5, la ligne L6 et la colonne H pour voir. Mais je suis d'humeur "géométrique" et je préfère continuer la pêche aux listes très courtes (2 candidats pas plus), quitte à perdre du temps (l'approche globale est beaucoup plus rapide que l'analyse case par case quand il s'agit de remplir les cases de listes de candidats) :

Toutes les cases à deux candidats ont été trouvées. Et ici on trouve deux doublons 16, l'un sur la ligne 8 (le plus intéressant) et l'autre sur la colonne I.

Remarquez bien que si vous aviez oublié, durant la première étape, les marques de choix du 4 dans la région v3, la case I8 contiendrait maintenant 146 et aucun doublon ne serait apparu !

Maintenant, la case G8 doit être examinée d'urgence : elle est à la fois dans la colonne du dernier placement et dans la ligne du doublon (il faut toujours examiner en priorité le voisinage des placements précédents).

Un nouveau placement est apparu suivi d'un second et de quelques marques de choix. De plus, deux zones à trois trous sont enfin disponibles : la ligne 8 et la colonne H. Ici il serait parfaitement logique d'attaquer l'approche globale. Mais pour exploiter le second doublon 16 en colonne I, je décide d'étudier d'abord le contenu de la région 9, en particulier les colonnes H (trois trous) et I (doublon) : c'est encore l'approche "géométrique" qui domine !

Et un triplet 458 apparaît dans cette région. Une belle surprise qui met en évidence aussi deux nouveaux doublons 16 et 59 en colonne G. Notons ces doublons et attaquons le remplissage de L8 :

Cette fois, c'est un doublon 23 en colonne B qui est mis en évidence. Naturellement, la priorité est l'étude de la case B6 : elle est à l'intersection de la ligne du tout premier placement et de la colonne du nouveau doublon (le maître mot est géométrie !) :

Et c'est un nouveau placement direct qui débloque entièrement la situation :

Le reste n'est plus qu'une affaire de routine.

Vous venez d'assister à la résolution d'un SUDOKU de niveau 6 qui n'était pas du tout facile : un remplissage précoce des listes de candidats aurait conduit à une grille trop chargée et très difficile à résoudre.

Analyse globale

fj — 2007-08-01T00:09:50Z

L'analyse globale consiste à traiter d'un coup tous les candidats manquant dans une ligne, une colonne ou une région. Le résultat principal est le remplissage ultra rapide des trous par des listes courtes de candidats.

L'efficacité de l'analyse globale est dûe au fait :

qu'on évalue une seule fois une petite liste de candidats qui concerne plusieurs cases d'une même zone,
que l'étude d'une case à compléter consiste simplement à réduire cette liste déjà courte en analysant les autres zones contenant cette case,
qu'implicitement, on considère donc l'interaction de tous les candidats de la liste (ce n'est plus une analyse candidat par candidat),

Commencez par les lignes, colonnes ou régions où il manque le moins de candidats à moins que vous n'ayez remarqué une particularité géométrique intéressante :

il manque un candidat dans un ligne : placez le immédiatement.
il en manque deux ? C'est une doublette à inscrire dans les deux trous ... et il n'est pas rare qu'en fait on arrive à placer ces deux candidats directement quand l'un deux est interdit dans un des deux trous,
il en manque 3 ? c'est une triplette qui mérite d'être notée. Très souvent, l'un des chiffres se placera automatiquement à cause d'un bouchage de trou (voir la technique des murs troués).
il en manque 4 ? Ne désespérez pas : vous pouvez avoir une bonne surprise.
il en manque 5 ? Aïe aïe aïe : soit vous avez manqué quelque chose, soit vous avez affaire à un diabolique pervers (typique d'un 6 ou 7 étoiles). Dans ce dernier cas, il faut parfois en passer par là (voir les exemples de résolution de problèmes diaboliques).

Le plus difficile, au début, c'est de bien lister dans sa tête les candidats manquants. Mais ensuite c'est très efficace car vous n'avez plus à considérer que cette liste pour chaque trou de la zone étudiée. Ensuite il faut évidemment tenir compte du contexte pour savoir si tous les candidats apparaissent dans tous les trous (c'est heureusement rarement le cas).

Durant cette étape, il faudra être vigilant :

ne pas mettre inutilement un candidat dans une case alors qu'il est déjà présent (parfois virtuellement seulement via une marque de choix directionnelle) dans la ligne perpendiculaire,
essayer de repérer des doublettes et triplettes qui pourraient apparaître soudainement dans la zone étudiée ou dans les autres zones contenant les trous,
exploiter ces doublettes et triplettes en supprimant les candidats inutiles,
répercuter les suppressions de candidats sur les marques de choix. C'est souvent cette technique là, appelée "report de marque", qui débloque les SUDOKU complexes,
ne pas oublier de remarquer la formation de murs encore que ce soit généralement moins important que pendant l'étape 1,
penser au Swing qui peut survenir à tout moment.

Reprenons l'exemple employé pour décrire l'étape 1. A l'issue de cette première étape, voici la position normalement obtenue :

Cette position est convenable pour démarrer l'étape 3 en omettant l'étape 2 car le diagramme montre pas mal de lignes, de colonnes et de régions où il manque deux, trois ou quatre valeurs. Dans le cas où le diagramme ne montrerait que très peu (voire pas du tout) de lignes, colonnes ou régions suffisamment remplies, alors la stratégie correcte serait d'essayer les techniques de l'étape 2 qui sont justement prévues pour trouver des placements astucieux supplémentaires.

En attendant, commençons par la ligne L2 où il manque (68) pour poursuivre par R5 (478), L8 (146) et la colonne A (1467) :

Ici on est un peu chanceux car on détecte une triplette 478 sur la ligne L4 dès le remplissage de la première zone à quatre tous. Naturellement, on aurait pu choisir de remplir une autre zone à quatre trous (lors de la résolution de ce problème, j'avais commencé par la région R7 qui ne montre rien de spécial). Mais tôt ou tard, la triplette serait apparu lors du remplissage de la colonne A.

Il s'agit maintenant de compléter immédiatement la ligne L4 et d'en tirer toutes les conséquences possibles :

Évidemment, la ligne est complétée par le doublon 39. Mais ce n'est pas la conséquence principale. Il est absolument fondamental de mettre en évidence que le 8 de la ligne L4 se situe dans la région R5. C'est ce que j'appelle un report de marque des listes de candidats vers les marques de choix . Une fois établie la place approximative du 8 dans la région R5, il devient évident que le candidat 8 de la case F6 n'a plus sa place et peut être rayé. Par ailleurs, ce report de marque localise aussi le 8 dans la région R6.

On voit que chaque succès obtenu avec la technique principale de l'étape 2 doit être complété par un report de marque suivi d'une propagation des nouvelles marques de choix (technique typique de l'étape 1).

Et maintenant comment poursuivre ? On pourrait bien sûr continuer l'approche globale. Mais la réalisation rapide d'un SUDOKU demande de l'astuce. En particulier, la victoire obtenue par le report de marque précédent semble vraiment bien mince (suppression du candidat 8 de la case F6) ... à moins qu'il n'existe, dans la ligne 6 ou la colonne F, une surprise agréable.

Et un bon joueur se doit de jeter un oeil sur les cases correspondantes (c'est typiquement une technique normalement réservée à l'étape 2). La première case à analyser est sans doute la case F3 mais la liste des candidats associés (168) ne donne rien. Il faut chercher une case avec peu de candidats. Or une seule case de la ligne 6 est intéressante : celle sur la colonne H. En effet, les autres cases contiennent soit un 6, soit un 8 (ce sont les marques de choix qui l'indiquent) qui ne font pas bon ménage avec le doublon 47 ... Et, miracle, la case H6 ne peut contenir que 4 ou 7.

Naturellement, la ligne L6 doit d'être complétée d'urgence :

Le doublon 47 de la ligne L6 permet le placement direct du 6 en B6 avec un effet en cascade. Même l'essai de la case F3 se trouve récompensé par l'apparition du triplé 168 en colonne F, ce qui donne E4=8. La suite est un jeu d'enfant : il suffit de continuer l'approche globale méthodiquement.

Au passage, vous venez d'assister aux moments clés de la résolution d'un SUDOKU classé diabolique (5 étoiles au crash test).

Analyse chiffre par chiffre et section par section

fj — 2007-07-31T23:35:00Z

C'est l'étape numéro 1 de la résolution d'un SU DOKU. Il s'agit d'essayer de positionner au mieux chaque chiffre dans chaque région.

Voci les techniques principales utilisées par ordre d'importance :

balayage des régions par tous les candidats,
placement d'un maximum de marques de choix quand un balayage de région ne parvient pas au placement direct,
remplissage des cases avec 1 candidat (case résolue), 2 ou 3 candidats : doublettes ou triplettes dans les régions, détectées facilement grâce aux marques de choix,
formation des murs (voir les techniques des murs complet ou troué) qui modifient le positionnement des marques de choix déjà placées,
repérage des S-wing qui ajoutent des marques de choix.

Pour les débutants, je conseille de passer en revue les chiffres de 1 à 9. Pour les habitués, il est souvent plus efficace de commencer par les chiffres qui ont la plus grande occurrence.

Une fois un chiffre sélectionné, examinez chaque région où ce chiffre est absent et rayez par la pensée (éventuellement au crayon pour les débutants) les cases interdites en tenant compte de la présence de ce chiffre dans les autres régions alignées avec celle que vous examinez. Voici par exemple un placement direct du 9 en région 2 :

Ensuite, soit vous avez trouvez l'emplacement du chiffre et vous le notez immédiatement en grand dans sa case, soit vous utilisez les marques de choix. Ces marques sont fondamentales dans mon système. Elles permettent de noter économiquement les cases pouvant contenir le chiffre.

N'utiliser jamais plus de 2 marques pour repérer les cases potentielles d'un chiffre dans une région. Il est possible de repérer 4 cases d'un coup (une marque sur le coin commun aux quatre cases) mais c'est très rarement intéressant. Pourtant, c'est une marque de ce genre qui m'a permis un jour de débloquer un SUDOKU particulièrement récalcitrant en mettant en évidence un S-wing ...

N'oubliez jamais que les marques de choix ont un souvent aspect directionnel : c'est le cas en particulier des marques qui désignent une série de cases alignées. Dans les deux autres régions de l'alignement, tout ce passe comme si le chiffre était placé dans la région considérée. Regardez comme les marques de choix du 9 en région R9 agissent sur les régions R7 et R8 comme si le 9 était vraiment placé dans la région R9 :

Apprenez à noter immédiatement les doublettes ou triplettes qui apparaîtront dès ce stade dans les régions. Pour cela, utilisez la notation des candidats qu'il ne faut jamais confondre avec les marques de choix. Voici par exemple la notation d'un doublon 29 en région 3 car les marques de choix indiquent en effet que le 2 et le 9 ont les mêmes cases possibles : G1 et H1. Aucun autre candidat ne peut plus s'incruster dans ces deux cases ! Pour les matheux, c'est comme un système de deux équations à deux inconnues bien conditionné : il n'a qu'une seule solution, le couple (2,9). Cela est valable aussi quand 3 candidats occupent 3 cases (triplé ou triplette) ou 4 candidats occupent quatre cases (quadruplé). Je n'ai encore jamais rencontré de quintuplé mais ce doit sans doute survenir dans des SUDOKU bizarres.

Sachez prendre garde à la formation de murs qui remettent en cause les marques de choix dans l'alignement contenant le mur. Regardez par exemple l'effet du mur R31 (région 3 ligne 1) du diagramme précédent (les cases G1 et H1 sont des briques du mur pour tout candidat qui n'est ni 2 ni 9). Voici les marques de choix du 3 avant l'apparition du mur si on traite les candidats dans l'ordre 1 2 3 :

Et voici ce qui se passe pour le 3 quand le mur apparaît pendant le traitement du 9 :

Si on traite les chiffres dans l'ordre 123459, regardez comme le placement du 5 en D9 remet en cause les marques de la région 8 :

le 3 est "poussé" dans la case D8,
le 2 à l'intérieur de la case D9 est tout simplement écrasé et il ne reste alors que la marque 2 en F7 => F7=2.

Et toutes ces modifications sont "automatiques" car les marques de choix ont permis de placer tous les éléments sous les yeux dans une seule région ! Mais il y a encore du travail car il faut exploiter maintenant ces trois nouveaux placements ...

Croyez vous que tout est dit ? Nous avons pourtant oublié deux choses :

l'effet du 5 en I7 : il interfère avec une marque de choix du 9 en région R9.
l'effet du 3 en D8 : il interfère avec une marque de choix du 1 en région R8.

Considérons attentivement le premier cas. Il y a une marque de choix du 9 dans le même alignement vertical en région 3 (frontière entre G1 et H1) : c'est un S-wing typique qui localise le 9 de la troisième région de l'alignement (région 6) dans la troisième colonne (I).

Le deuxième cas est un peu plus complexe : La région R2 contient un mur troué 7-9 sur la colonne D. Mais ce mur est "bouché" par le 1 situé en H2 (voir l'article sur les murs troués). Cela signifie que le 1 de la région R2 ne peut se trouver que sur les colonnes E ou F. Or il en est de même maintenant du 1 de la région R7. C'est encore un S-wing (swing pour les intimes) qui permet de placer le 1 de la région R5 sur la colonne D. Et comme, il n'y a qu'un emplacement valide ...

Évidemment le jeu continuera par le placement du 4 en D2 mais c'est une autre histoire ... racontée à l'étape 3 !