SUDOKU

Résolution de "Al Escargot"

fj — 2007-08-21T21:27:28Z

La grille "Al Escargot" est célèbre dans le monde entier. Elle est réputée pour être le problème de SUDOKU le plus compliqué pouvant être résolu par des moyens humains. Voici une façon de la résoudre. Celle-ci ne plaira sans doute pas aux puristes car de nombreux doubles paris sont employés.

Il m'a fallu trois jours et près de 5000 coups élémentaires pour enfin trouver la solution de ce SUDOKU démoniaque !

Cela le classe au niveau hallucinant de 100 étoiles (environ 50 coups par étoile). En écrivant cet article, j'ai toutefois rabaisser le nombre de coups à 2000, ramenant la difficulté au niveau plus modeste de 40 étoiles ... ce qui reste évidemment monstrueux, les SUDOKU des revues ne dépassant jamais 7 étoiles (350 coups au maximum) !

Prise en main du monstre

Voici la grille de départ :

La première étape de la stratégie de résolution amène le diagramme suivant :

Inutile de dire que les progrès ne sont pas brillants :

un seul placement évident,
une moisson minime de marques de choix.

Il est impossible en pratique de démarrer l'étape 3 (l'analyse globale) après un remplissage aussi pauvre d'une grille. La stratégie générale est ici la recherche de placements directs astucieux ou, à défaut, des listes courtes de candidats :

Voilà un résultat particulièrement frustrant :

aucun placement direct supplémentaire,
aucun doublé ou triplé,
deux listes à deux candidats seulement : C5=34 et C2=46

Juste pour voir, la grille "complétée" devient :

Et comme de bien entendu, il n'y a rien de plus à l'horizon :

pas de doublé,
pas de triplé,
pas de motif particulier exploitable,
pas de groupe caché.

Doubles paris précoces

A situation exceptionnelle, méthodes exceptionnelles ! C'est pourquoi je tente de voir ce que donnent des doubles paris contraires, dès maintenant, avant tout remplissage. Le but n'est pas de résoudre la grille mais simplement de continuer à acquérir quelques connaissances sur son comportement démoniaque.

Double pari du 3 en R4 :

Il ne donne rien sinon le fait de rappeler que le 3 en R6 n'a que trois cases possibles, ce qu'on savait déjà !

Double pari du 7 en R5 :

Il ne donne strictement rien !

Double pari sur le 9 en R4 :

On note un double Swing perpendiculaire du 9 en R8, le pari rouge amenant le Swing en R88 tandis que le vert l'amène en R8E. Cela donne cette fois (enfin !) un premier indice précieux sur la grille : il n'y a pas de 9 dans les quatre cases de coin de la région 8, c'est à dire D7, F7, D9 et F9.

Double pari sur la case C5=34

Rien non plus, même si le 4 a bien débloqué la grille (il faudra s'en souvenir).

Stratégie

Après tout cela, le bilan est maigre : seul le pari du 9 en R4 a montré un petit résultat. En tout cas, il est clair que la grille en l'état est trop difficile pour moi et que rajouter un placement à 50% ne la rend pas plus facile. J'en déduis qu'il me faut au moins deux placements supplémentaires pour avoir une grille jouable (peut-être). Naturellement, deux placements à 50% chacun ne génèrent pas une grille mais quatre grilles dont trois d'entre elles n'ont pas de solution.

Je choisis donc le 9 en R4 (il m'a donné un petit résultat) et la case C5=34 : elle a montré une bonne propagation de marques.

Voici les quatre grilles simplifiées à résoudre :

Grille numéro 1

Première étape : l'analyse région par région

Passons à l'approche globale pour les zones à 3, 4 et 5 trous en commençant par l'alignement v1 où ont été ajoutés les placements.

un triplé 278 apparaît rapidement en CB
l'analyse de la colonne C donne C2=6. En association avec le triplé 278 précédent, on obtient B1=5
doublé 59 en R22
doublé 69 en R7B
doublé 47 en L2 (A2 et G2) qui amène G2=1

Inutile d'essayer de remplir les régions R8 et R9 car les listes y sont trop longues :

A présent, il s'agit de réduire les listes. Or la meilleure technique pour cela est le double pari équilibré. La case D1=48 attire mon regard car les deux paris progressent tout de suite, surtout le vert (D1=4). Mais en regardant attentivement le pari rouge (D1=8), on note beaucoup de motifs intéressants :

triplé 134 en L3 => A2=4
motif de non unicité en A3=78 B3=78 A4=78 B4=278 => B4=2
doublé 78 en B6/G6 => H6=5
triplé 346 en colonne I

Le pari vert n'est pas en reste :

toute le ligne 1 se résout,
un doublé 47 apparaît en R3H
il s'en suit un second motif de "presque" non unicité entre A2=47 A3=247 H2=47 et H3=47 => A3=2

Que tire-t-on de tout cela ? Beaucoup d'éléments si on applique méthodiquement les quatre théorèmes du double pari :

d'abord les deux paris sont d'accord pour A2=4 et H2=7 : Ces deux placements sont donc corrects.
ensuite le même chiffre est parfois choisi à des emplacements différents d'une même zone, comme le 2 en région 1 par exemple : seules ces deux cases sont alors possibles pour ce chiffre dans cette région et donc le 2 disparaît de la case B3.
le troisième théorème s'applique dans les cases où les deux paris donnent des résultats différents. C'est le cas de la case H3 par exemple. Dans ce cas, les candidats non sélectionnés sont supprimés (candidat 7 de la case H3).
le 4ème théorème est le plus subtil. Si des candidats différents dans des cases différentes d'une même zone sont sélectionnés par les deux paris, alors des éliminations sont possibles, le candidat du premier pari disparaissant de la case du second et réciproquement. C'est le cas par exemple des cases A4 et B4, le 2 de la case A4 et le 7 de la case B4 pouvant être éliminés. On retrouve encore ce motif entre les cases D5 et D6/E6 : le 7 disparaît de ces deux dernières cases. Mais cela marche aussi entre E3 (pari vert 1) et E6 (pari rouge 9) donc E6=9. D'une manière analogue, on remarque que le 8 vert de H4 (il est bel et bien vert même si j'ai oublié de le colorier sur le diagramme ci-dessus) détruit le 8 du pari rouge H6=5 ce qui valide d'ailleurs ce pari.

La grille s'est bien simplifiée mais il y a encore du travail, sans parler des deux régions R8 et R9 toujours vierges de placement. Ceci dit, on peut déjà insérer le doublon 59 en R9I.

Récidivons avec un nouveau double pari, par exemple dans la case F5 :

C'est beaucoup moins efficace. On ne remarque qu'un théorème 4 entre les cases E1 et E3 (pas de 3 en E4). Remplissons les cases restantes faute de mieux :

Que faire ? Je propose un troisième pari en région 8, E8=3 ou E9=3 par exemple.

pour le premier pari, un doublon 59 D2/D8 surgit qui donne D5=7 puis D7=4 et D9=1. De plus un triplé 569 est mis en évidence en L9 (B9, E9, I9). En fait, toute la grille semble se résoudre avec E8=3 ... mais je m'arrête avant la fin.
le second pari, au contraire, s'arrête très vite (résolution des 3 seulement).

Conclusion : menons le premier pari à son terme ... Et enfin une anomalie survient : deux 6 en colonne G. Donc F8=3 !

Heureusement, D8=9 avait été oublié pour le second pari et la grille progresse à nouveau. Elle se débloque presque complètement quand un doublon 16 surgit en R44 :

Et ici, il faut encore être bien éveillé pour noter le quadruplé 2468 en L7 (donc B7=9).

Voici le diagramme final : la case D7 est vide et la grille 1 n'a pas de solution.

La résolution de cette simple grille a demandé 986 coups élémentaires. Cela en fait la plus complexe que je n'ai jamais résolue (la précédente était un "9 étoiles" avec 450 coups !). Cela la classe au niveau 20. Quand on pense que c'est une grille nettement simplifiée par rapport à "Al Escargot" !

Grille numéro 2

L'analyse région par région est moins efficace qu'avec la grille précédente :

Mais l'analyse globale renverse un peu la situation. A noter :

un triplé 278 en R4 qui permet le placement A4=4,
un triplé 278 en colonne B,
un report de marque du 7 en R4B qui empêche B3=7 et place un 7 en R1A.

Par analogie avec la grille précédente, les régions R8 et R9 sont laissées vierges :

Le premier pari de la grille 1 n'est plus possible (case D1). Mais la case B1 fait aussi bien l'affaire :

Le pari vert (B1=5) progresse grâce aux éléments suivants :

un doublé 27 en R13
un doublé 46 en L2 (C2/H2) qui permet le placement G2=1,
un doublé 59 en R22,
un triplé 134 en R2 qui donne D1=8
un dernier doublé 46 en R1C qui n'apporte rien de particulier.

Le pari rouge (B1=6) montre :

un doublé 28 en CC (C1/C6) ce qui donne C7=6,
un doublé 28 en R7A qui amène A3=7,
un doublé 19 en R22 et un doublé 67 en R32,
le placement I3=1 et donc I4=6, F5=6, G6=1.

Et que tire-t-on de ce double pari bien équilibré ? Pratiquement rien du tout. Incroyable ! Je crois bien que c'est la première fois qu'un double pari équilibré m'apporte aussi peu de résultat : le théorème 4 sauve l'honneur en interdisant G2=4 (interaction C2/G2 des placements différents rouge et vert).

Comment des grilles 1 et 2 presque identiques peuvent-elles se comporter si différemment ?

Evidemment, il faut quand même persévérer. Dilemme : que choisir comme nouveau double pari ? J'ai le choix entre une autre case contenant deux candidats ou bien une marque désignant deux cases.

Après avoir été échaudé avec une case à deux candidats qui semblait prometteuse, j'opte cette fois pour une marque de choix. Quand on choisit une telle marque comme base d'un double pari, autant prendre celle désignant deux cases très chargées car cela élimine à chaque fois tous les autres candidats de la case choisie. Les meilleures marques sont donc le 2 en R3 et le 3 en R6. J'opte pour le 2 car il est plus près de l'action (car plus éloigné des régions désertées R8 et R9).

Et tout de suite le pari s'avère tout sauf équilibré. Le pari vert G1=2 est immédiatement stoppé alors que le pari rouge H3=2 semble débloquer totalement la grille ! En temps normal, j'aurais abandonné un pari aussi déséquilibré mais est-ce bien un SUDOKU normal ? Et il ne faut pas oublier que la fin de la résolution de la grille 1 s'est justement faite sur un pari déséquilibré.

Par ailleurs, ce pari donne tout de suite un résultat car le pari vert dit G1=2 tandis que le pari rouge conclut rapidement à G1=4. Le troisième candidat (6) de la case est donc éliminé (c'est déjà aussi bien que le pari précédent !). Donc faisons progresser le pari rouge en espérant une anomalie rapide :

doublon 19 en R22
doublon 67 en R32

Et sans la moindre difficulté, on obtient pratiquement la résolution complète des cases dotées d'une liste de candidats (dans les cases sans placement rouge, les candidats impossibles pour le pari rouge sont rayés pour faciliter la compréhension) :

Pas d'anomalie en vue. Mais compte tenu de l'ampleur de cette résolution, je ne doute plus que le pari rouge puisse aller au bout et afficher, vers la fin, l'anomalie attendue. Il est temps de compléter les régions R8 et R9 uniquement avec les candidats compatibles au pari rouge : inutile de s'embarrasser de listes complètes puisqu'on sait qu'au début du pari ces deux régions étaient vides ; on pourra donc restaurer facilement la position de départ.

Commençons par la région R9 plus simple à remplir que R8 :

Au tour de la région 8 en tenant compte du doublon 28 en L8 :

On voit le placement direct du 3 suivi de celui du 6. De plus il faut exploiter le doublon 59 en R88 et remarquer qu'il y a un triplé caché 124 dans la région R8 (ce qui amène la suppression des candidats rayés dans la région R8 du le diagramme ci-après) :

Et c'est la plus grosse surprise du pari rouge : il est correct et la grille est résolue.

Décidément, c'est un problème à surprise. Le plus souvent, le volet d'un double pari qui progresse le plus est faux (la loi de Murphy appliquée au SUDOKU). Mais cette grille sort vraiment de l'ordinaire : c'est le pari qui progresse qui est le bon !

Au passage, j'ai plutôt de la chance puisque la solution est obtenue dès la seconde grille. Celle-ci a demandé un peu plus de 700 coups. En tenant compte des différents essais avant de définir la stratégie gagnante, il aura bien fallu les 2000 coups annoncés en début d'article !

Voici la grille résultat nettoyée :

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).

Classification des problèmes

fj — 2007-08-09T00:36:42Z

La classification des problèmes de SUDOKU est assez délicate. Une définition possible, trouvée sur internet, fait appel à la liste des techniques nécessaires pour la résolution des problèmes.

Cette classification basée sur les techniques est intéressante mais pas impartiale pour autant. En effet les techniques elle-mêmes font l'objet d'un classement discutable. En particulier, les problèmes dont la résolution fait appel à la force brute sont toujours jugés extrèmement compliqués.

Or utiliser la force brute n'est pas aussi compliqué qu'il y parait. L'article sur le double pari montre même que c'est une méthode parfaitement utilisable plusieurs fois dans une même résolution.

De plus, la force brute peut souvent pallier un XY-wing oublié ou un Swordfish manqué. Donc la liste des techniques nécessaires pour résoudre un SUDOKU est elle-même sujette à caution.

Mon classement est plus simple : un problème est d'autant plus difficile qu'il demande un nombre d'actions élémentaires élevé ... quand on utilise ma méthode. C'est là je l'avoue que ma méthode de classement a aussi un premier aspect subjectif. Elle en a un second plus pernicieux : si je résous une deuxième fois le même problème, vais-je utiliser le même nombre d'opérations ? Non évidemment. Mais en pratique, la différence n'est pas si grande que cela. Et quand je classe un problème, j'essaie de trouver la méthode la plus rapide possible quitte à le résoudre plusieurs fois de suite.

Une action élémentaire est simplement :

l'écriture d'un candidat dans une case,
l'inscription d'une marque de choix,
l'ajout d'un petit motif au dessus d'un candidat pour désigner un pari ou marquer un candidat qui se déduit d'un pari,
la suppression d'un candidat.

Les logiciels que j'emploie ont le bon goût d'indiquer le nombre d'actions qu'il a fallu que j'effectue pour résoudre un SUDOKU. Voici le classement approximatif que j'ai obtenu :

20 - 80 : problème de niveau 1 dont la résolution se résume à une suite de placements directs,
60-120 : problème de niveau 2 où trouver la suite de placements directs n'est pas aisé (quelques marques de repérage sont alors bienvenues pour faciliter le travail),
100 -160 : problème de niveau 3 pouvant déjà demander la détection de duos,
140 -200 : problème de niveau 4 pouvant déjà demander la détection de duos et de triplés (problèmes difficiles),
180 -240 : problème de niveau 5 contenant au moins un triplé et demandant de la persévérance et de l'astuce (les problèmes classés diaboliques commencent en général à ce niveau),
220 - 280 : problème de niveau 6 dont la résolution peut faire appel à n'importe quelle technique,
260 - 350 : problème de niveau 7 enchaînant de nombreuses difficultés et dont le déblocage définitif ne se produit vraiment qu'à la fin. Rejouez donc la dernière partie que j'ai enregistrée : vous verrez ce que c'est qu'un niveau 7 !
320 - 400 : niveau 8
380 - 450 : niveau 9.
430 - 500 : niveau 10.
au delà, je propose une étoile de plus par tranche de 50 coups. Impossible à résoudre ? Pas si sûr comme le montre l'artticle "Résolution de "Al Escargot""

Il existe sur le net des grilles de niveau 9. Elles sont déjà impitoyables. Allez donc faire un tour sur l'excellent site http://www.mots-croises.ch/Manuels/.... J'ai réussi à résoudre quelques grilles de niveau 9 mais il m'a fallu à chaque fois plus de 400 coups (et plusieurs heures de réflexion) en ayant systématiquement recours à la technique du double pari et ses quatre théorèmes magiques.

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.

Problèmes de niveau 6

fj — 2007-08-08T14:26:54Z

Etes vous prêts à résoudre des problèmes diaboliques ? En voici un florilège pour lequel il faudra appliquer toutes les techniques résentées dans ce site pour en venir à bout.

Rappel des commandes de base :

bouton droit = menu contextuel contenant toutes les fonctions disponibles. Seul le menu permet de modifier les couleurs si celles par défaut ne vous plaisent pas.
racourcis au clavier :
- chiffre : nouveau candidat dans une case
- Suppr ou <- : suppression d'un candidat
- d : vider une case
- X : affichage de la solution

Problèmes de niveau 5

fj — 2007-08-08T12:33:45Z

Cette fois c'est très sérieux. Ces exercices de niveau 5 sont vraiment difficiles.

Rappel des commandes de base :

bouton droit = menu contextuel contenant toutes les fonctions disponibles. Seul le menu permet de modifier les couleurs si celles par défaut ne vous plaisent pas.
racourcis au clavier :
- chiffre : nouveau candidat dans une case
- Suppr ou <- : suppression d'un candidat
- d : vider une case
- X : affichage de la solution

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 :

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).