Le double pari
mercredi 8 août 2007
par fj

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 :

  1. les deux paris désignent soudain le même placement : validez ce placement !
  2. 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 !
  3. 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).
  4. 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") .