SUDOKU

Les autres techniques

fj — 2007-08-14T22:28:45Z

Internet regorge de techniques de SUDOKU. Cependant, dans la cadre de mon système de résolution, certaines ne sont pratiquement jamais employées. Cela ne signifie pas qu'elles soient mauvaises mais je n'en ai pas l'usage, tout simplement.

Les groupes de candidats cachés

Il s'agit de chercher, dans une zone où toutes les cases sont remplies de listes de candidats :

un candidat seul dans la zone. On l'appelle le candidat unique bien qu'il ne soit pas seul dans sa case (sinon ce serait trop facile). Evidemment, son placement est immédiat.
deux candidats présents dans exactement deux cases (ils forment un doublon caché). Tous les autres candidats présents dans ces deux cases peuvent être supprimés.
idem pour 3 candidats dans trois cases ou 4 candidats dans 4 cases.

En pratique, seul le premier cas présente de l'intérêt, le second pouvant toutefois survenir exceptionnellement. En effet, les marques de choix repèrent très rapidement les doublés et les triplés et dans mon système. De plus, il est très rare qu'une case contienne plus de 4 candidats : les groupes se cachent donc difficilement.

Swordfish, Jellyfish, Squirmbag, Burma

Ce sont tous des X-Wing étendus. Les motifs sont trop compliqués à rechercher. Le double pari est nettement plus efficace.

XYZ-Wing

Il s'agit d'une variante du XY-Wing mais elle est, elle aussi, trop difficile à repérer. Comme j'ai déjà bien du mal à remarquer un XY-Wing ...

Coloriage, Turbo fish, XY-chain, coloriage XY, 3D medusa, candidat forcé en chaîne, nishio

Ce sont des méthodes de réduction de liste basées sur un pari limité. Je préfère de loin le double pari qui est plus efficace car il permet souvent de trouver des placements et de réduire sérieusement les listes de candidats dans plusieurs cases alors même qu'aucun des deux paris n'est encore résolu (c'est cela la vraie beauté d'un double pari).

Le bouchage de trou

fj — 2007-08-08T23:36:27Z

On a déjà étudié l'effet d'un mur troué qui peut être "bouché" par un candidat particulier présent dans la rangée perpendiculaire au trou. La méthode de bouchage de trou est tout à fait comparable mais le but est différent : il ne s'agit pas d'expoiter un mur avec un "double rebond" mais d'effectuer un placement direct ou à defaut l'inscription d'une marque de choix dans la rangée trouée.

Voici le motif à repérer :

On peut vérifier que ce motif n'est pas détecté par les techniques mises en oeuvre lors de l'étape 1. Il est en effet assez rare et ne doit être pris en compte que si l'étape 1 se passe mal. Dans ce cas, il convient de rechercher des placements par des méthodes nouvelles (elles font partie de l'étape 2).

Le bouchage de trou est l'une de ces méthodes. Le repérage du motif est juste une question d'habitude. Ce n'est toutefois pas la méthode principale de l'étape 2 : je lui préfère La pêche au gros.

Le double pari

fj — 2007-08-07T22:36:19Z

Il existe de nombreuses techniques basées implicitement sur un pari comme le nishio (essai d'un candidat en espérant qu'il échoue), les candidats forcés en chaîne, les méthodes de coloring ou le 3D medusa.

Mais pourquoi se farcir l'esprit de méthodes aussi astucieuses soient-elles quand il existe une méthode plus générale et pratiquement toujours efficace : le double pari.

Conditions de lancement d'un pari

La mise en oeuvre d'un pari suppose généralement que toutes les cases soient remplies de listes exhaustives de candidats. En fait ce n'est pas absolument indispensable. Il peut rester quelques cases vides mais ces dernières devront être résolues si le déroulement du pari conduit à mettre des placements dans ces cases (si on ne les résout pas, on se heurte alors à des difficultés de notation).

Le but d'un bon pari n'est pas du tout de réussir : c'est beaucoup plus simple quand une contradiction est rapidement mise en évidence. En effet, un pari qui semble réussir peut tout à fait être une tromperie et on ne sait jamais quand on doit s'arrêter : l'incertitude est bien pire que l'échec.

C'est d'ailleurs une des raisons pour lesquelles je mène les paris en duo : je suis sûr que l'un d'eux est faux !

Notations d'un pari

Contrairement à ce qu'on peut penser, organiser un pari n'est pas difficile du tout ... à condition d'adopter des notations légères. Si on adopte des paris simplifiés (nishio, coloring ...), on peut se passer de notation car tout se fait de tête avec un peu (beaucoup) d'habitude. Mais si on opte, comme moi, pour le cas général, alors les notations sont obligatoires car nous ne sommes pas des ordinateurs à mémoire infaillible.

Il m'arrive d'enchaîner plusieurs paris dans des SUDOKU de niveau 6 et plus. Pour ne pas confondre un pari en cours avec un pari ancien (je ne me sers jamais de gomme), j'adopte les notations suivantes :

le premier pari est marqué d'un petit point au dessus du candidat sélectionné au départ et des candidats qui seront déduits par la suite,
le second pari est un noté d'un petit trait vertical,
le troisième pari est noté d'une petite croix,
le 4ème pari est noté par un rond vide,
le 5ème pari est noté par un rond plein,
le 6ème pari est noté par un carré plein.

Ce choix n'est pas innocent : le point est la plus petite marque possible, le trait peut surcharger le point, la croix peut surcharger autant le point que le trait vertical, le rond peut entourer une croix, un trait ou un point ...

Pour le site, le logiciel que j'utilise marque les candidats simplement en leur changeant leur couleur. Le premier pari sera "vert" et le second "rouge" quand la couleur normale est le bleu.

Le choix de départ

Un double pari consiste souvent à choisir une case contenant exactement deux candidats. Soit cette case contient le premier candidat (premier volet du double pari), soit elle contient le second (second volet). Encore faut-il que la grille de SUDOKU contienne effectivement une telle case.

Heureusement, ce n'est pas la seule possibilité. On peut aussi se baser sur une marque de choix désignant deux cases possibles pour un même candidat. Soit le candidat en question se place dans la première case, soit dans la seconde. Notez ici que le nombre effectif de candidats dans ces deux cases n'a strictement aucune importance.

Je n'ai jamais rencontré de grille de SUDOKU où était impossible d'effectuer un double pari.

Mais ce n'est pas tout : il ne faut pas se tromper de point de départ. Je conseille de choisir un point de départ qui permette effectivement de débloquer la situation pour les deux paris contraires. Il faut en effet que les paris soient les plus équilibrés possible. Sans quoi, un seul pari permettra de décanter la situation et vous n'avez plus qu'à espérer qu'il mène rapidement à une contradiction.

Enfin, un dernier conseil. Quand vous avez choisi un point de départ qui semble satisfaisant, vérifiez qu'il n'existe pas un autre qui implique le premier. Auquel cas, ce dernier sera certainement meilleur.

Les effets d'un double pari

Une des premières fonctions d'un double pari est d'arriver à une contradiction sur l'un des deux. Dans ce cas, c'est l'autre pari et tous les placements qui s'en déduisent et que vous avez déjà repérés qui sont justes.

Mais un double pari, même avant la détection d'une contradiction, peut obtenir des résultats probants gràce à quatre théorèmes puissants :

les deux paris désignent soudain le même placement : validez ce placement !
les deux paris désignent dans une même case deux candidats différents. Si cette case contient trois candidats ou plus, supprimez tous les candidats non sélectionnés !
un pari sélectionne un candidat dans une case d'une zone donnée (ligne, colonne ou région) et l'autre sélectionne ce même candidat dans une autre case de la même zone : placez une marque de choix entre ces deux cases et naturellement, calculer la propagation de cette marque de choix (suppression du candidat dans toutes les autres cases de la zone concernée puis prise en compte des interactions entre zones).
les deux paris sélectionnent chacun un candidat différent dans deux cases différentes d'une même zone. Il est amusant de voir que le candidat sélectionné par le premier pari peut être supprimé de la liste de candidats dans la case du second et réciproquement. Démonstration :
- supposons que le premier pari soit juste : il est évident que le candidat sélectionné doit être supprimé dans toutes les autres cases de la zone, en particulier dans la case du second pari.
- par ailleurs, comme le candidat sélectionné est supposé être le bon, tous les autres candidats de la liste sont supprimés sans remord et donc, en particulier, celui désigné par l'autre pari.
- le même raisonnement s'applique à l'autre case du second pari.
- dans les deux cas, on constate que le théorème proposé est effectivement appliqué. Ceci mérite un diagramme :

Exemple de double pari

Voici un exemple sur un problème classé 7 étoiles dans le recueil "TAZUKU SUDOKU ULTRA N01" ; c'est aussi mon classement personnel avec un nombre de coups élémentaires pour le résoudre de l'ordre de 300 environ. Après un début assez facile, il a fallu découvrir un bon nombre de doublés et de triplés pour obtenir :

Dans une telle position, on peut essayer de trouver un motif particulier comme un XY-WING ou essayer une méthode de coloring. Je décide de ne pas me casser la tête et je choisis la case E5 comme double pari :

elle est centrale et donc je ne risquerai pas de l'oublier,
et comme il y a plusieurs 79, je sais que les deux paris vont progresser, du moins au début.

Evidemment, il était possible de choisir une autre case, comme par exemple un des duos 24 de l'alignement v1 .

Commençons par E5=7 et essayons d'aller un peu plus loin que la simple résolution des duos 79. Il faut en particulier noter que si H2=7 (propagation directe sur les duos 79), alors G2=9 (on exploite la marque de choix du 9 en R3) ce qui résout entièrement la colonne G : G4=8, G8=4. La ligne 8 s'en déduit aussi puis les placements successifs remontent (résolution des duos 24) dans l'alignement V1 pour revenir dans la région centrale avec D5=1.

A noter que ce pari a beaucoup progressé sans mettre en évidence de contradiction immédiate. Pourtant, l'application du principe de Murphy au SUDOKU (voir plus loin "le coup du désespoir") me ferait plutôt préférer l'autre pari car la progression a été trop facile. Et on peut sûrement progresser encore !

Passons cependant au pari opposé. Il semble se bloquer assez vite (résolution des duos 79) mais si on fait attention aux marques de choix, on découvre facilement I2=7, I3=2 et G4=9.

Pour prolonger ce second pari, il faut réfléchir un peu. Par exemple, la case I4 n'a pas de 7 et comme il n'y avait que deux 7 en ligne 4 (I4 et D4) on a donc obligatoirement D4=7. On en déduit D6=2 (marque de choix), et donc B4=2 (balayage de la région 2 par le candidat 2).

Ici c'est fort intéressant car les deux paris donnent le même résultat dans la case B4 (B4=2) ! Ce placement est donc parfaitement sûr ainsi que tous les placements qui s'en déduisent :

Notez au passage que même si on a raté un XY-Wing, un X-wing ou un Swordfish, la technique du double pari permet très bien de pallier cet oubli. Et ce n'est pas fini :

Et c'est l'apparition du duo 28 sur la colonne I (I3/I8) qui montre que c'était le pari "rouge" qui était le bon (la bonne vieille loi de Murphy se vérifie encore) ! Ce qui permet de finir en roue libre :

Le coup du désespoir

Lorsque vous êtes désespérés (impossible de lancer un double pari équilibré et aucune contradiction n'apparaît sur le pari qui décante la situation), alors tentez le vrai pari de la dernière chance : placez directement le candidat du pari qui ne progresse pas.

C'est tout simplement l'application, au SUDOKU diabolique, de la célèbre loi de Murphy : le bon candidat est celui qui vous arrange le moins !

Vous croyez que c'est idiot ? Détrompez vous : cela se vérifie à plus 70% d'après mes statistiques personnelles. Cela peut s'interpréter comme suit : le choix du candidat qui débloque très rapidement une situation a de grandes chances d'aboutir à une contradiction car "il relâche trop de contraintes" (le SUDOKU est un problème mathématique d'optimisation "sous contrainte") .

Report de marque

fj — 2007-08-07T14:03:01Z

Pendant l'approche globale, on remplit un grand nombre de cases de listes de candidats. Mais on oublie souvent de noter des marques de choix dans les régions. En général, j'essaie de le faire dans la foulée, à chaque remplissage de rangée, mais il m'arrive d'oublier.

Il est donc bon, quand l'approche globale est terminée, de repasser en vue les lignes et les colonnes et de rechercher si un candidat, placé exactement en deux endroits différents de la rangée étudiée, ne serait pas placé dans une région particulière.

Une fois une rangée sélectionnée, on se s'intéresse qu'aux candidats non placés qui sont dans des listes et qui n'ont pas de marque de choix associée. Pendant cette étape , on a intérêt à ajouter non seulement des Marques de choix (marques désignant des cases dans une même région) mais aussi des Marques à distance (pour le répérage ultérieur des X-Wing éventuels).

Voici un exemple où l'ajout d'une petite marque permet d'effectuer plusieurs placements :

Dans cet exemple très simple, seules la ligne 4 et la région 5 sont considérées. Tout part de l'analyse des candidats dans la ligne 4. Il suffit de remarquer que le candidat 2 de cette ligne est uniquement positionné dans la région 5, ce qui se traduit par l'ajout d'une marque de choix :

Cette petite marque a des conséquences étonnantes sur la grille :

tout d'abord elle interdit le candidat 2 dans la région 5 en dehors de la ligne 4 ce qui permet le placement direct E5=3,
ce placement supprime le candidat 3 des autres cases de la région, si bien qu'un doublon 57 apparaît soudain,
ce doublon élimine le 5 de la case D4. Mais comme la ligne 4 ne proposait au départ que deux emplacements pour le 5, un nouveau placement est possible : C4=5,
ce dernier placement supprime une des deux seules cases possibles pour le 8 en ligne 4 donc : I4=8.
enfin l'apparition du doublon 12 en R54 élimine les candidats 1 en R64 :

Evidemment, il est préférable de penser au report de marque durant toute la partie. En effet, n'importe quel placement peut modifier le marquage et il faut toujours tenir à jour les marques. Dès qu'une marque bouge dans une région, vous devez faire attention (d'autant plus attention que le SUDOKU est difficile).

Unicité

fj — 2007-08-07T12:14:27Z

Le fait qu'un SUDOKU n'ait normalement qu'une seule solution peut être exploité dans certains cas. Il existe en effet des motifs géométriques annonçant plusieurs solutions. Comme ces motifs géométriques ne doivent jamais apparaître réellement, cela fournit parfois des indices précieux.

Le motif typique annonçant plusieurs solutions est la présence de quatre cases en X (motif "X-Wing") contenant le même doublon :

Ce motif est interdit. Cela signifie que lorsqu'il se dessine, il faut empêcher son apparition. Voici un exemple simple :

Si le 7 de la case C2 venait à disparaître, le SUDOKU aurait au moins deux solutions. En conclusion, le 7 de la case C2 ne peut pas disparaître ce qui signifie simplement B2=7 (placement direct du 7 en case 2).

On n'arrive pas toujours à effectuer un placement. Mais dès qu'un motif de "non unicité" se dessine en filigrane, il y a souvent une conséquence pratique utile :

Les deux 7 des cases C2 et C3 ne peuvent disparaître simultanément. Il y a donc une marque de choix du 7 à la frontière entre les cases 2 et 3. Il ne reste plus qu'à exploiter cette marque de choix :

Le balayage de région

fj — 2007-08-06T23:04:46Z

Le balayage des régions est la technique majeure utilisée pour résoudre les SUDOKU. Elle intervient à tout moment, dès qu'un nouveau placement est effectué ou qu'une nouvelle marque directionnelle est inscrite.

Le balayage d'une région par un candidat consiste :

à sélectionner un candidat particulier,
à sélectionner une région,
à supprimer (par la pensée) toutes les cases de la région interdite pour ce candidat en espérant qu'il ne reste qu'une case possible. Cette suppression doit prend en compte la présence éventuelle du candidat dans les trois lignes et les trois colonnes dont l'intersection forme la région.

La technique des Marques de choix améliore notablement le balayage de région en permettant de noter astucieusement des informations importantes même quand un placement direct n'est pas possible.

Voici quelques situations usuelles où un placement direct est possible :

Voici une autre position où le placement direct du 1 dans la région 7 n'est pas possible. Cependant, il est possible d'y inscrire une marque directionnelle qui permet le placement du 1 dans une autre région (R1). Deux régions ne reçoivent aucune information (R5 et R8) car la position du 1 n'est pas déterminée avec suffisamment de précision (trop de cases possibles).

La pêche au gros

fj — 2007-08-06T14:58:00Z

Lorsque l'analyse par région ne permet pas d'effectuer suffisamment de placement définitifs, il faut changer son fusil d'épaule et rechercher des placements directs.

Le placement direct est la méthode préférée du débutant : un seul candidat convient à une telle case qu'on appelle souvent une case forcée.

Mais trouver une telle case n'est pas du tout simple. On peut bien sûr examiner toutes les cases une par une (c'est parfois ce que je fais) mais c'est long et fastidieux (15s par case et 60 cases à analyser c'est un minimum de 10 mn). C'est pourquoi je préfère aller à la pêche.

Le problème est de trouver rapidement les bons coins de pêche et là il faut de l'expérience et du feeling. Pour l'expérience, je commence à en avoir mais le feeling n'a jamais été mon fort. J'essaie donc de faire des recherches plus ou moins méthodiques :

l'idée maîtresse est de rechercher des points d'intersection ligne+colonne+section ayant peu de candidats en commun.

avant de remplir une case, j'essaie d'évaluer rapidement combien de candidats vont s'y loger. S'il semble y en avoir trop j'abandonne. Mais si je décide d'approfondir, je vais jusqu'au bout (il faut que le travail fournisse un résultat), c'est à dire que je remplis toujours la case avec sa liste exhaustive de candidats, laquelle est d'ordinaire limitée à 3 valeurs ... sauf quand je me trompe de case, auquel cas il pourra y en avoir 4 voire 5.

Il est rare que je mette directement le doigt sur une case forcée mais l'expérience m'a montré que quand l'analyse d'une case a donné une liste courte, il faut souvent analyser les cases voisines pour voir ! (voisinage = même ligne, même colonne ou même région)

De la même manière, quand une case forcée a été trouvée, les cases voisines doivent être analysées d'urgence.

Exemple :

Voici un diagramme après l'étape 1. Le balayage des régions n'a rapporté que deux placements et un doublé. C'est maigre ! Attaquer dès maintenant l'approche globale est risqué car il n'y a aucune zone de trois trous et une seule de quatre trous et encore : la colonne D en considérant le doublé 45 comme placé. Non franchement c'est plutôt l'heure de la pêche.

Par où commencer ? C'est là que le feeling est utile. Moi je n'en ai pas alors je cherche un peu au hasard une ligne, une colonne et une section qui semblent avoir un maximum de candidats différents. Naturellement, le point d'intersection de la ligne et de la colonne est étudié en priorité.

Sur le diagramme ci-dessus, la colonne H, la région 9 et la ligne 9 me semblent intéressantes (surtout la case H9 évidemment). Calculons la : on y trouve deux candidats possibles 1 et 5.

Et soudain je m'aperçois que Ligne 2 et colonne H n'ont que des chiffres différents. La case d'intersection donne H2=5 (gràce au 9 de la région 3). Et voilà, la seconde tentative est la bonne. Et la première tentative sert aussi : H9=1. Exploitons ces deux placements directs avec un balayage de région : E1=1 et C3=5.

Maintenant l'approche globale peut commencer avec 7 placements et un doublé : il y a de quoi faire avec pas moins de 7 zones à quatre trous : R1 R2 L1 L2 L9 CD CH.

Le balayage des lignes et colonnes

fj — 2007-08-06T14:51:09Z

C'est le pendant du balayage des régions pour les lignes et les colonnes.

D'une manière générale, le balayage des lignes et des colonnes n'est pas aussi efficace que le balayage des régions. Il permet toutefois de trouver des placements ou de placer des marques que l'analyse par région n'a pas découverts.

Je conseille donc d'effectuer un balayage de lignes et colonnes quand vous n'êtes pas satisfait des résultats de l'analyse par région.

D'une manière générale, c'est une technique que j'utilise peu car je trouve qu'elle est trop longue à effectuer complètement. Je lui préfère La pêche au gros.

Exemple d'utilisation :

Effectuons un balayage de la ligne 1 par le candidat 8 :

la case C1 est interdite par le 8 en C5,
la case E1 est interdite par une liste exhaustive de candidats où le 8 n'apparaît pas,
la case F1 est interdite par la marque de choix directionnelle du 8 en colonne F,
donc la seule position est H1.

On voit au passage que cette technique s'apparente à celle du "mur troué". Mais elle permet de résoudre aisément le cas du mur "gruyère" où il manque plus d'une pierre à l'édifice car la technique du mur troué n'est exploitable en pratique que pour le motif de base (un seul trou dans le mur).

XY-Wing

fj — 2007-08-06T14:21:59Z

Le XY-Wing est une technique réputée difficile. Or son principe de fonctionnement est simple et son motif géométrique de base est relativement facile à trouver.

Le motif du XY-Wing est le suivant :

quatre cases en relations circulaires
trois candidats bien identifiés (ABC)
trois des cases contiennent les trois duos (AB, AC et BC).

L'effet a lieu sur la quatrième case : le candidat présent uniquement sur la diagonale du quadrilataire ne peut pas appartenir à cette quatrième case.

Il suffit de raisonner sur les candidats du coin opposé à la case qui a être modifiée pour s'en convaincre aisément.

Exemple :

Considérons la case D7 (case opposée à H2) :

si le candidat définitif est 3, alors la case D2 contient 1 et la case H2 ne peut pas avoir de 1
si le candidat définitif est 7, alors la case H7 contient 1 et la case H2 ne peut pas avoir de 1

Dans les deux cas, le candidat 1 est proscrit dans la case H2 et on peut donc le supprimer.

Ici l'exemple ressemble à un X-Wing car les quatres cases sont à l'extrémité d'un X. Ce n'est toutefois pas toujours le cas si le motif est à l'intérieur d'un alignement de régions :

Ici la case A6 ne peut pas contenir le candidat 3 (raisonnez sur la case C3 pour vous en convaincre). Elle contient donc 8.

Le repérage d'un XY-wing se fait en deux temps :

recherche de 3 duos de 3 candidats en relation circulaire,
recherche de la quatrième case et suppression du candidat diagonal.

C'est presque plus facile à faire qu'à dire.

X-Wing

fj — 2007-08-06T10:26:55Z

Le X-Wing est une technique d'élimination de candidats. Un X-Wing permet d'effectuer un placement définitif uniquement si la case concernée ne contient que deux candidats et que l'un d'eux est justement le candidat concerné par le X-Wing.

Un X-Wing demande :

un candidat bien identifié,
quatre cases formant un X et contenant le candidat,
une présence limitée du candidat (en deux exemplaires seulements), soit dans les deux colonnes (X-Wing de colonne) contenant les quatre cases, soit dans les deux lignes (X-Wing de ligne).

L'effet du X-Wing est simple : suppression du candidat dans les lignes (cas d'un X-Wing de colonne) ou dans les colonnes (X-Wing de ligne) contenant les quatres cases, à l'exception de ces quatres cases évidemment.

La difficulté principale d'un X-Wing est sa détection. Il existe une technique de marquage permettant de repérer à coup sûr tous les X-Wing présents dans un diagramme entièrement rempli de listes de candidats : Marques à distance.

Mais contrairement à ce que beaucoup de joueurs de SUDOKU pensent, il est parfaitement possible (et particulièrement efficace) de détecter un X-Wng de manière très précoce bien avant que toutes les cases ne soient remplies.

A noter que le X-Wing situé dans un alignement est assez fréquent. Il fait alors partie de la famille plus générale des Swing (un Swing peut ne pas être un X-wing). Un simple marquage de proximité suffit pour le détecter facilement.

Exemple extrème d'un X-Wing détecté dès la position initiale

Voici un diagramme initial de SUDOKU (d'un niveau 3-4). Appliquons lui une méthode de balayage du 1 (on raye toutes les positions interdites) :

Tout d'abors, la technique de balayage donne immédiatement un placement en région centrale :

Mais il fait aussi apparaître un X-Wing colonne :

En effet, il n'y a que deux 1 en colonnes A et I et ces 1 se trouvent dans les mêmes lignes 1 et 9. L'effet du X-Wing est le suivant :

Et ce n'est pas fini ! Un second X-Wing "colonne" apparaît soudain (B et G) :

Avec comme effet :

Ceci dit, j'ai résolu facilement ce SUDOKU sans utiliser les X-Wing : il est en effet suffisamment simple pour que la stratégie de base suffise (recherche des marques de choix puis approche globale alternée avec le report des marques).