Wikilivres

« Résolution de casse-têtes/Résolution du sudoku » : différence entre les versions

Navigation interactive dans l’historique
← Modification précédenteModification suivante →
Contenu supprimé Contenu ajouté
VisuelWikicode
Ortho.
m Ortho.
Ligne 170 :
</TR>
</TABLE>
Cette technique est la plus simple à comprendre mais elle est plus lourde à mettre en oeuvreœuvre que la précédente, puisqu'en principe, elle devrait être envisagée pour toutes les cases restant vides.<br />
En pratique, il est assez judicieux, du moins dans un premier temps (c'est-à-dire tant que l'on ne rencontre pas de difficulté à continuer d'avancer dans la résolution du sudoku), de n'envisager cette technique que dans les régions où le nombre <noinclude></noinclude>de valeurs renseignées est déjà assez élevé (d'abord 7, puis 6 ou à la rigueur 5).<br />
Notons que si une région (ligne, colonne ou pavé) possède déjà 8 valeurs
Ligne 358 :
<BR>
Dans ce type de situation, l'une des 2 régions (R<FONT SIZE="1">1</FONT> ou R<FONT SIZE="1">2</FONT>) est un pavé, l'autre étant une région
"<I>mince</I>", c'est-à-dire une ligne ou une colonne <FONT SIZE="1">(on verra que, parmi les techniques extrêmes, on peut définir une technique -celle des réseaux s'inspirant du même principe mais mettant en oeuvreœuvre des lignes et des colonnes)</FONT>.<br>
 
Donnons deux exemples :<br>
Ligne 710 :
<TABLE BORDER="0" CELLPADDING="25px" WIDTH="90%">
<TR><TD WIDTH="100%">
Dans la mise en oeuvreœuvre d'une technique de coloriage, on progresse pas à pas en prenant en compte, à chaque pas, un nouveau lien. Mais il est interdit de prendre en compte un nouveau lien qui ferait apparaître, par le coloriage supplémentaire qui en résulterait, un couple case-candidat qui aurait la même couleur qu'un couple case-candidat (déjà coloré) situé sur une case "voisine".<BR><BR>
<i>Remarque</i> : on verra que le fait de tomber sur une "<i>situation d'interdiction</i>" est souvent l'indice de la possibilité d'une élimination de candidat ...
</TD></TR></TABLE>
Ligne 723 :
Pour pouvoir appliquer correctement ce principe, voici ce qu'il faut entendre par "<B>voisinage</B>" entre couples : deux couples case-candidat distincts sont "voisins" s'ils ont, soit la même case (et donc des candidats distincts), soit même candidat et même région (ligne, colonne ou pavé) !<BR>
<br>
Parce qu'ils mettent en oeuvreœuvre plusieurs jeux de couleurs, le coloriage multiple et le coloriage généralisé ne peuvent pas utiliser le principe d'élimination sous la forme simple qui vient d'être expliquée, mais ils l'utilisent sous une forme plus sophistiquée (bien qu'équivalente) !
</TD></TR></TABLE>
 
Ligne 932 :
<font id=Elim2> </font>
<B>Elimination de candidat</B> :
:En cas de coloriage multiple, l'élimination éventuelle d'un candidat repose sur une "extension" de l'[[#Elim|élimination]] mise en oeuvreœuvre dans la technique de coloriage simple : en effet, si l'on détecte (au lieu d'une case isolée non colorée ...) deux cases colorées <b>solidaires</b> (peu importe qu'elles soient toutes deux de la couleur <FONT COLOR="#339900"><B>C3</B></FONT> ou de la couleur <FONT COLOR="#339900">C4</FONT>) et dont l'une est voisine d'une case <FONT COLOR="#0000FF"><B>C1</B></FONT> tandis que l'autre est voisine d'une case de couleur <FONT COLOR="#0066CC">C2</FONT> (opposée à <FONT COLOR="#0000FF"><B>C1</B></FONT>), alors on peut affirmer que :<BR>
:- que le candidat <B><I><FONT COLOR="#993300">c</FONT></I></B> peut être effacé pour toutes les cases solidaires dotées de la couleur <FONT COLOR="#339900"><B>C3</B></FONT> (ou <FONT COLOR="#339900">C4</FONT>), et<BR>
:- que les cases antagonistes <FONT COLOR="#339900">C4</FONT> (ou <FONT COLOR="#339900"><B>C3</B></FONT>) doivent prendre la valeur <B><I><FONT COLOR="#993300">c</FONT></I></B> !
Ligne 1 103 :
COLOR="#0066CC">1</FONT><FONT SIZE="1">~Df</FONT><FONT
COLOR="#0000FF"><B>1</B></FONT><BR><BR>
Le couple Df2 est à la fois "voisin" de Df<FONT COLOR="#0000FF"><B>1</B></FONT> et "voisin" de Fd<FONT COLOR="#0066CC">2</FONT> et l'on est certain que Df<FONT COLOR="#0000FF"><B>1</B></FONT> et Fd<FONT COLOR="#0066CC">2</FONT> sont "antagonistes" puisque les liens de paires mis en oeuvreœuvre dans le circuit sont tous des "liens forts" (cas n° 1) : Df2 correspond donc à une hypothèse fausse et l'on peut éliminer le candidat <FONT SIZE="1" COLOR="red">2</FONT><FONT SIZE="1"> de la case </FONT><FONT SIZE="1" COLOR="red">Df</FONT><FONT SIZE="1"> (la suite de la résolution est plus délicate ...)</FONT>
<br>&nbsp;<br></DIV></TD>
<TD WIDTH=6%> </TD>
Ligne 1 220 :
Terminons par quelques <b>commentaires généraux</b> :<BR>
:- un coloriage généralisé utilise toujours plusieurs (au moins deux) jeux de couleurs opposées : <FONT COLOR="#0000FF"><B>C1</B></FONT>|<FONT COLOR="#0066CC">C2</FONT>, <FONT COLOR="#339900"><B>C3</B></FONT>|<FONT COLOR="#339900">C4</FONT>, <FONT COLOR="#996600"><B>C5</B></FONT>|<FONT COLOR="#cc9933">C6</FONT>, <FONT COLOR="#9900CC"><B>C7</B></FONT>|<FONT COLOR="#9966CC">C8</FONT>, etc ...<BR>
:- à chaque jeu de couleurs correspond un "circuit", c'est-à-dire un enchaînement de liens ; et réciproquement, chaque circuit ne met en oeuvreœuvre qu'un seul jeu de 2 couleurs, et ce jeu lui est propre ; <BR>
:- un circuit n'est pas nécessairement "pur", c'est-à-dire constitué de liens de même nature ; il peut au contraire être "mixte", c'est-à-dire combiner à la fois des liens "simples" ("~") et des "liens (de paire) forts" ("=") ; <BR>
:- un circuit "mixte" présente au moins une case "charnière", c'est-à-dire une case présentant d'un côté un lien "simple" (pour l'un de ses candidats) et de l'autre un "lien de paire" ; ceci n'est possible que si la case n'a que 2 candidats (paire) ; <BR>
Récupérée de « https://fr.wikibooks.org/wiki/Résolution_de_casse-têtes/Résolution_du_sudoku »