Votre espace personnel

S'identifier           S'inscrire

assistant-sudoku.com

A propos de la technique des pistes

La technique des pistes que j'expose dans ce site est une approche personnelle que j'ai développée au cours des années 2007/2008 lorsque j'ai commencé à pratiquer le sudoku et que les techniques expertes me paraissaient bien compliquées à appliquer.
Elle synthétise (voire généralise) les techniques que l'on rencontre dans la littérature consacrée au sudoku (sites web, livres et magazines) sous des noms différents, en particulier les techniques des chaînes (x-Wing, x-chain, xy-chain, coloriage, 3D Medusa, essai-erreur, force brut, etc...), car elle permet de les démontrer toutes.

Ce qui caractérise la technique des pistes et la rend originale, c'est qu'elle ne repose pas sur la notion de liens (forts ou faibles) mais seulement sur la notion de solution possible. Ainsi, la chaîne de candidats formant la piste n'est pas construite comme cela se fait traditionnellement dans les exposés de sudoku en suivant les liens et/ou en utilisant la notion de Vrai/Faux, mais en construisant un ensemble solution potentiel de candidats liés à un candidat de départ. C'est pour cela que j'ai utilisé le terme piste au lieu de chaîne. J'aurais pu aussi l'intituler technique des marquages ou technique des réseaux.

Par ailleurs et contrairement aux techniques dites "chaîne forcée" ou "force brut" ou "essai-erreur" considérées comme faisant appel au hasard, la technique des pistes repose sur une analyse de la structure de la grille guidant le sudokiste vers un choix constructif des pistes.
En effet, le but n'est pas d'essayer une valeur pour savoir si elle convient ou pas, ou conduit à une contradiction ou pas, mais bien de construire un réseau logique qui permet, grâce aux proriétés des pistes, de procéder à des éliminations et/ou à trouver la solution d'une case.
Cette analyse qui demande un peu de pratique consiste essentiellement à examiner au préalable quels candidats permettront un développement significatif des pistes afin d'exploiter leurs propriétés.
On distingue d'ailleurs deux principales manières d'utiliser la technique des pistes :
- Soit en exploitant au maximum les possibilités d'un jeu de pistes et en changeant de pistes que lorsqu'on ne peut plus rien en retirer. Voir cet exemple.
Avec cette façon de procéder j'ai remarqué que, en général pour le sudoku proposé au public dans les magazines spécialisés, 1 jeu de pistes suffit pour les niveaux 7/9, 2 sont nécessaires pour les niveaux 10/11 et 3 pour les niveaux 12 et plus, mais cela n'est pas une règle.
- Soit de manière plus subtile en changeant de pistes dès que l'on a fait apparaître, après éliminations de candidats, de nouvelles paires de candidats d'où l'on peut redémarrer une jeu de pistes. Voir cet exemple.
Cette façon de procéder se rapproche de celle utilisée avec les techniques expertes où pour avancer il faut employer plusieurs techniques différentes successivement, techniques qu'il faut maitriser ce qui n'est pas donné à tout le monde. On voit là que la technique des pistes, intuitive et à la portée de tous, remplace toutes ces techniques.
Evidemment, avec la pratique on utilise l'une et l'autre et un mixe des deux en recherchant l'efficacité.

La notion de piste se distinct aussi de celle de chaîne par le fait qu'une piste est un réseau de candidats comprenant plusieurs branches et des bifurcations (appelées pistes secondaires) permettant de résoudre les grilles les plus difficiles. Il me semble d'ailleurs être le seul à exposer cette notion de pistes secondaires et de donner des exemples d'application (voir par exemple Sudoku-Resolu-13

Enfin, la technique des pistes est rendue originale par l'usage que l'ont peut faire de plusieurs jeux de pistes simultanés ou de jeux de pistes conjuguées.

On trouvera ci-dessous quelques références à des sites ou des livres proposant des techniques semblables à la technique des pistes. Si de votre côté vous avez connaissance d'autres documents présentant une technique semblable à la technique des pistes, n'hésitez pas à m'en informer via le formulaire contact.

R. Mauriès
Créateur de l'Assistant Sudoku


Voici quelques livres et sites internet consacrés au Sudoku qui proposent des techniques plus moins proches de la techniques des pistes, livres et sites que j'ai découvert bien après avoir élaboré la techniques des pistes

Livres

Précis de sudoku, de Narenda Jussien - Edition Hermes

L'auteur présente en page 54 une technique qu'il nomme "disjonction constructive" en tout point semblable à la technique des pistes, à ceci prêt qu'il n'envisage que le cas de suites convergentes de candidats vers un même candidat.

The hidden logic of Sudoku, de Denis Berthier - First Edition

Sont exposées dans ce livre, avec un formalisme très mathématique, essentiellement les techniques des chaînes (x-chain, xy-chain, xyz-chain, etc...). Ces techniques sont des cas particuliers de la technique des pistes.

Coloriage virtuel, de Bernard Borrelly

La technique du coloriage virtuel inventée par l'auteur s'inspire de la technique du coloriage qui a été adaptée et prolongée par l'introduction de la notion de couleur virtuelle, c'est à dire de chaînes au sens classique du terme (construction par lien) complétant le réseau générique des couleurs. L'ensemble des deux réseaux, générique et virtuel, est semblable à la technique des pistes et dispose des mêmes propriétés. S'y ajoute aussi (en complément du livre) les principes des réseaux multiples et leurs applications. http://www.coloriagevirtuel.fr.

Notes sur les sudokus réglementaires très difficiles et diaboliques, de Jacques Allard

Ce document de 300 pages accessible via internet en format PDF est une réflexion de l'auteur sur les grilles difficiles nécessitant l'usage de techniques expertes. Mr Allard distingue notamment les grilles ne pouvant être résolues qu'en faisant intervenir le hasard au moins une fois de celles que l'on peut résoudre totalement par un raisonnement logique. On y trouve toutes les techniques de résolutions et la référence à la technique des pistes, mais aussi de nombreux aspects mathématiques liés au sudoku (unicité, théorie des graphes, etc...). Livre en format PDF

Sites internet

http://parfum-echecs.chez-alice.fr/sudoku/index.html
Ce site en français de Monsieur Francois Jacq présente une technique, dite du "double pari", quasi-identique à la technique des pistes puisque le principe en est le même : partant d'une paire construire deux suites de candidats potentiellement solutions et exploiter les 4 propriétés qui y sont attachées. J'ai découvert ce site récemment en étudiant l'AI Escargot dont l'auteur du site construit la solution aussi. La notion de bifurcation (piste secondaire ou équivalent) n'est toutefois pas évoqué.

http://www.mathrec.org/sudoku/methods.html
Steve Schaefer l'animateur de ce site consacré au sudoku (en anglais) expose sa technique dite "Trial and Error" tout à fait semblable à celle des pistes et énonce les mêmes propriétés.

http://www.mots-croises.ch/Manuels/Sudoku/
Ce site en français présente les principales techniques utilisées en sudoku, les techniques de base et les techniques expertes dont la "force brute". La technique la plus proche de celle des pistes est celle du "candidat forcé en chaîne".

http://vincent.planete.org/sudoku/techniques_sudoku_expert.php?technique_id=chaines_forcees
Ce site en français décrit la technique dite "Chaîne forcée" tout à fait semblable à celle des pistes, mais se limite au cas de pistes convergentes.

http://www.sudokuwiki.org/Cell_Forcing_Chains
Ce site en anglais est le plus complet que je connaisse où les techniques de "Forcing chain" sont les plus développée (forcing chain, Nishio, Bowman's bingo, Medusa). La distinction avec la technique des pistes tient essentiellement au mode de construction des chaînes, mais on y retrouve les mêmes propriétés.
Toutefois, aucune de ces techniques n'abordent les bifurcations et autres approches du type pistes simultanées ou conjuguées.
Il expose aussi l'usage de triples ou quadruples chaînes, comme on peut le faire avec des triples et quadruples pistes (voir Convergence de 3 pistes), mais leur usage est très exceptionnel, voire tient de la curiosité.


http://fr.wikibooks.org/wiki/Résolution_de_casse-têtes/Résolution_du_sudoku
Ce site en français présente toutes les techniques de sudoku et notamment celles du coloriage (simple et multiple), avec toutefois une approche et une terminologie très personnelles de l'auteur.

En savoir plus ...



Nos partenaires














assistant-sudoku.com est la propriété de 2IAsystem sarl, 8 rue du romarin, 31520 Ramonville St Agne. Toute reproduction interdite.