[ Guillaume Laforge ]


Home

CV

Projets

Weblog

Les techniques plus compliquées pour résoudre les Sudoku  —  Ecrit par Stephanie

Dans un précédent article, j'ai essayé d'expliquer les techniques les plus simples pour résoudre les Sudoku (Su Doku ou Soduku). Ces techniques sont indispensables pour commencer à résoudre tous les Sudoku. Mais elles ne sont pas suffisantes pour les sudoku de niveau moyen ou difficile. Pour ces derniers, il vous faudra également maîtriser les techniques des paires ou triplets cachés et la technique du X-Wing que je vais tenter d'expliquer ci-dessous. Ces techniques ne permettent pas de mettre un chiffre dans une case mais d'éliminer des indices possibles dans une ou plusieurs cases lorsqu'on a fait le recensement exhaustif de tous les indices possibles dans chaque case.
Pour les Sudoku les plus diaboliques, il vous faudra également maîtriser les techniques du Swordfish, du Coloring (ou Colouring), et des paires liées. Mais pour ces 3 techniques, personnellement, je n'arrive pas à les repérer dans un grille. Et même pire : pour le Sworfish et le colouring, je n'arrive pas à comprendre comment ces techniques fonctionnent. Alors, si vous les connaissez, n'hesitez à pas à nous aider.

Dans les grilles ci-dessous, les chiffres en noir sont les chiffres fixes ou trouvés en cours de résolution. Les chiffres écrits en petit et en bleu sont tous les chiffres possibles dans la case concernée(= indices). Les chiffres écrits en petit et en rouge sont les chiffres possibles dans la case concernée après élimination de certains chiffres par une des techniques décrites ci-dessous



Les paires cachées

Dans le grille ci dessus, tous les indices ont été notés pour la région en haut à gauche. On peut voir que les chiffres "1" et "9" n'apparaissent que dans 2 cases (cases 2 et 3 de la colonne n°1). Par conséquent, on peut en déduire que ces 2 chiffres sont forcément dans ces 2 cases et que dans ces 2 cases, les seuls chiffres possibles sont le "1" et le "9". On peut donc supprimer les autres indices possibles c'est- à-dire le "2" et le "5" dans la case 2 de la colonne n°1 et le 5 dans la case 3 de la colonne n°1

<VOICI p < éliminés indices ces fois une grille la>

Pour généraliser, dès que vous trouvez 2 chiffres dans 2 cases d'une même région, colonne ou ligne et uniquement dans ces 2 cases, vous pouvez éliminer tous les autres chiffres possibles dans ces 2 cases.

Les triplets cachés

La technique des triplets cachés est la même que celle des paires cachées mais avec 3 chiffres au lieu de 2

Dans la grille ci-dessus, on peut voir que les chiffres "3", "6" et "7" ne se trouvent que dans 3 cases : les cases n°4, 6 et 7. Par conséquent, tous les autres chiffres que les "3", "6" et "7" peuvent être supprimés de ces 3 cases.

Pour généraliser, dès que vous trouver 3 chiffres dans 3 cases d'une même région, colonne ou ligne et uniquement dans ces cases, vous pouvez éliminer tous les autres chiffres possibles dans ces 3 cases. Attention, il n'est pas nécessaire que les 3 chiffres soient présent dans les 3 cases, il peut n'y avoir que 2 ou 1. La seule chose importante est que ces 3 chiffres ne se retrouvent pas dans d'autres cases que ces 3 cases.

X-Wing

Dans la grille ci-dessous, regardez les cases dont le fond est jaune. Ces 4 cases forment un carré, elles contiennent toutes les quatre, le chiffre "6". Et ce chiffre "6" n'apparaît dans aucune autre case des lignes 1 et 9 : lignes dans lesquelles se trouvent les 4 cases à fond jaune. Par conséquent, on peut éliminer tous les chiffres "6" qui se touvent dans les autres cases des colonnes n°6 et 9 (où se trouvent les 4 cases à fond jaune)

<MAIS
Prenons, la case n°6 de la ligne n°1 (fond jaune). Si le "6" se trouve dans cette case, cela veut dire qu'il n'est pas dans tout le reste de la colonne notamment dans la case 6 de la ligne n°9 (fond jaune). Si le 6 n'est pas dans cette case "6" de la ligne 9, cela veut donc dire qu'il est dans la case 9 de la ligne 9 ( fond jaune) et que par conséquent, il n'est plus dans aucune autre case de la colonne 9.
On peut donc faire le même raisonnement pour chacune des quatre cases à fond jaune

Pour généraliser, si 4 cases contenant le même chiffre forment un carré et que ce chiffre n'apparait pas sur les autres cases des 2 lignes de ce carré, on peut éliminer ce chiffre sur les autres cases des colonnes de ce carré.
De même, si 4 cases contenant le même chiffre forment un carré et que ce chiffre n'apparait pas sur les autres cases des 2 colonnes de ce carré, on peut éliminer ce chiffre sur les autres cases des lignes de ce carré.

posté le 13.11.2005 à 16:48:38 par Stephanie - Catégorie : General

Liens

Commentaires

leblair a écrit :

putain c chaud !!!
19.11.2005 22:13:10

Luc a écrit :

salut stephanie moi c'est luc j'ai decouvert le sudoku la semaine derniere et je me passionne pour ce jeu depuis lol (5 jours c'est rapide c'est vrai) je voulais savoir s'il y avait une logique implacable pour ce jeu (du genre 2 chiffres qui vont toujours de pair...)et qui pourrait faire remplir les cases de logique completement differente. Sinon j'ai encore rencontré personne qui passé du temps comme moi a faire des grille de sudoku mais pour ce qui commencent je n'ai qu'un truc a leur dire c'est du courage parce qu'on evolue vite en 5 jours je suis passé de pres de 3h pour faire ma premiere grille a un dixaine de minutes pour les remplir maintenant et je ne connaissais pas encore les technique de stephanie lol.
a+ tout le monde
23.11.2005 00:35:42

babeth a écrit :

Bravo, ces explications sont super-claires...ce qui est rarement le cas. Le "x.wing" m'a permis de boucler une grille "démoniaque" sur laquelle je m'acharnais depuis trois jours. J'ai découvert le Sudoku il y a un mois; je suis bien accro et je convertis pas mal de gens autour de moi comme ma fille
23.11.2005 10:46:19

Le kabyle a écrit :

Une nouvelle règle, celle de la "BC Doku" à homologuer pour eviter l'inscription de petits chiffres dans les coins au risque de se planter et de salir sa case.
La recherche s'effectuera dans les angles simultanés des neufs cases de neufs avec des règles précises de déduction des chiffres.
Si certains la connaisse alors super sinon je vous en parle après avoir fait un sudoku
23.11.2005 22:09:53

nath a écrit :

bravo pour les explications; est-ce que la technique x.wing marche si le carré est a l'intérieur de la grille?
02.12.2005 23:59:54

Stephanie a écrit :

la technique X-wing marche aussi pour un carré à l'intérieur de la grille!!
03.12.2005 10:22:14

Arnaud a écrit :

Oui cette technique est valable pour un carré à l'intérieur de la grille!
05.12.2005 01:16:28

sax a écrit :

salut stéphanie
Toutes ces techniques sont efficaces, mais comment font les joueurs qui bouclent régulièrement une grille difficile en 10 mn maxi, moi rien que pour écrire tous les petits chiffres, il me faut 12 mn c'est seulement après que je peux analyser. Donc je n'arrive pas en dessous de 30mn.
07.12.2005 14:34:32

Stephanie a écrit :

Sax, plus tu feras de grilles, plus tu seras rapide. Et tu n'auras plus besoin de marquer tous les chiffres car tu capteras de plus en plus la logique Sudoku
08.12.2005 21:02:15

Ilyas a écrit :

Bonjour,

Je me demande un truc, là: est-ce que toutes ces techniques permettent de résoudre à coup sûr un Sudoku niveau démoniaque? Je me retrouve régulièrement dans l'impossibilité de déterminer à coup sûr quel chiffre doit aller où, ce qui m'oblige à passer par des grilles intermédiaires (en gros, un raisonnement par l'absurde).

Merci d'avance,
Ilyas
30.12.2005 15:12:02

Stephanie a écrit :

Pour les vrais Sudoku (à une solution) et résolvable par un cerveau humain : toutes ces techniques normalement suffisent pour les résoudre. Il me semble qu'il existe quand même une autre technique : le colouring que je ne connais pas.
Par contre, il arrive qu'on rencontre des "faux" Sudoku qui ont plusieurs solutions. Et sur certains sites, on trouve des grilles démoniaques qui peuvent être totalement résolues que par un ordinateur : les techniques de résolution employées sont trop compliquées pour un cerveau humain.
02.01.2006 12:15:20

Pouyet jean a écrit :

Bonsoir
l'unicité de la solution d'une grille a t elle été démontrée et si oui, où?
merci
01.02.2006 18:51:42

Stephanie a écrit :

En fait, si ce sont de vrais Sudoku, une et une solution est possible. Par contre, dans certains magasines, il arrive de trouver des Sudoku avec plusieurs solutions
01.02.2006 19:37:55

akim a écrit :

l'unicité n'a pas été démontrée pour la simple raison qu'elle n'est pas garantie (y compris pour des vrais sudoku dit à répartition symétrique)

Malheureusement les sudoku ne sont pas des logigrammes (résolus seulement par la logique) : la mutiplicité des solution impliquera forcément un choix arbitraire.

Heuresement les éditeurs s'arrange pour qu'il n'y ait qu'une seule solution.

L'ordi peut toujours résoudre un sudoku (notement en appliquant la méthode par l'absurde).
04.02.2006 00:08:17

lelor63 a écrit :

ta premiere grille de paire cachée ... a 2 six dans un carré ;)

Sinon tes explications sont super claires! merci
06.02.2006 17:01:46

karlik a écrit :

Comment savoir si votre solution est la bonne, si l'unicité n'a pas été démontrée.

Au niveau débutant, je me suis retrouvé devant une grille vierge.

J'ai répondu
1 2 3
4 5 6
7 8 9

Le magazine me propose une autre solution. Que faire, choisir sa solution ou celle du magazine ?
13.02.2006 20:23:11

Stephanie a écrit :

Je ne comprends pas : t'avais bien des chiffres pour t'aider dans les autres régions?
13.02.2006 21:32:10

Arianne a écrit :

bonjour,
je voulais vous dire que je suis entrein de me passionner sur les sudoku.
mais je ne comprend pas encore les truc compliques.
19.02.2006 19:04:44

Marco a écrit :

Voilà, je connais enfin la methode X-wing dont tout le monde parle. En faite, je l'appliquait plus ou moins sans savoir que c'était comme ça que ça s'appelait :D
28.02.2006 22:59:11

eric a écrit :

.

X-wing... c'est un nom qui me fait penser aux nom de planètes dans stargate !

.
01.03.2006 19:24:10

Ji-Pé a écrit :

X-WING ... c'est le nom de certains chasseurs (les petits trucs qui tirent des lasers sur les gros super crpoiseurs) dans STAR WAR.

;-)
15.04.2006 09:17:05

zendo a écrit :

j'iame bien se jeu mais pour rien vous caché je ne compren pas les explikation mdr... yoré personne pour me donné des explication plus claire et des exemple! des cours particulier koi????
17.04.2006 21:31:32

Ajouter un commentaire

:

:
:


Références externes

Cette page a été vue 13843 fois.
Dernier visiteur le 2006-05-20 10:09:54.

Cette page a été indexée par Google le 2006-05-20 10:09:54

118 - [g]
80 - [g]
65 - [g]
57 - [g]
56 - [g]
41 - [g]
41 - [g]
40 - [y]
38 - [g]
36 - [g]
32 - [g]
31 - [g]
29 - [g]
29 - [g]
28 - [g]
28 - [g]
27 - [g]
27 - [g]
27 - [y]
26 - [g]