« Résolution de casse-têtes/Résolution du sudoku » : différence entre les versions
Contenu supprimé Contenu ajouté
m Mise en page |
Mise en page |
||
Ligne 89 :
=Trois techniques simples=
Les techniques simples sont les techniques qui peuvent être mises en œuvre sans avoir besoin de recourir à l'examen exhaustif de tous les candidats de toutes les cases non remplies.<br />▼
▲Les techniques simples sont les techniques qui peuvent être mises en œuvre sans avoir besoin de recourir à l'examen exhaustif de tous les candidats de toutes les cases non remplies.
Il en existe trois grandes catégories :
▲- l'<b>[[#Tech01|élimination directe]]</b> <br><br>
▲- la <b>[[#Tech02|recherche des valeurs uniques]]</b> <br><br>
▲- l'<b>[[#Tech03|élimination indirecte]]</b> <br><br>
<font id=Tech01> </font>
== Élimination directe==
<FONT SIZE="1">(ou recherche d'un candidat "solitaire camouflé")</FONT>
On procéde en quatre temps :
<TABLE style="background-color:#FFFFCC" BORDER="1" CELLPADDING="5" WIDTH="95%"><TR><TD WIDTH="100%">
*
*
*
*
</TD></TR></TABLE>
▲Distinguons quelques types de cas :<br>
▲• Dans les cas les plus courants, on travaille "par bloc" et la région qui intervient à l'étape <B><FONT COLOR="black">c</FONT></B> est un pavé dont deux lignes (<FONT COLOR="#999999">ou deux colonnes</FONT>) du bloc ont été barrées ; il reste, sur les cases du pavé appartenant à la ligne (<FONT COLOR="#999999">colonne</FONT>) non barrée, une seule case vide qui peut être accompagnée : <BR>
▲:: - soit d'une case déjà remplie et d'une case barrée car appartenant à une colonne barrée (<FONT COLOR="#999999">ligne</FONT>), comme dans l'exemple 01a ;<BR>
▲:: - soit de deux cases occupées, ce qui correspond, comme dans l'exemple 01b, à l'un des cas les plus évidents (donc faciles à repérer).<br>
▲• Les cas où, comme dans l'exemple 01c, la région de l'étape <B><FONT COLOR="black">c</FONT></B> est une ligne ou une colonne sont moins faciles à repérer.<br>
▲• Enfin, les cas où l'on dispose, pour une valeur donnée, de 8 cases contenant déjà la valeur <I><B>v</B></I> sont les plus simples car on est sûr de trouver sans peine la neuvième case qui manque !<br><br>
▲Voici donc trois exemples d'élimination directe.<br><br>
<font id=ex01a> </font>
D'abord un exemple courant <FONT SIZE="1">(illustré par trois images successives, correspondant respectivement aux étapes -</FONT><B><FONT SIZE="1">a</FONT></B><FONT SIZE="1">, puis -</FONT><B><FONT SIZE="1">b</FONT></B><FONT SIZE="1"> et -</FONT><B><FONT SIZE="1">c</FONT></B><FONT SIZE="1">, et enfin -</FONT><FONT SIZE="1"><B>d</B> expliquées ci-dessus)</FONT> :
<TABLE BORDER=0 CELLPADDING=0 WIDTH=80%>
<TR>
Ligne 138 ⟶ 128 :
</TR>
</TABLE>
<font id=ex01b> </font>
... ensuite, un exemple particulièrement facile :
Ligne 151 ⟶ 139 :
</TR>
</TABLE>
<font id=ex01c> </font>
... et enfin un dernier exemple, moins immédiat :
Ligne 165 ⟶ 150 :
</TR>
</TABLE>
<font id=Tech02> </font>
== Recherche des valeurs uniques==▼
<font size=1>(ou recherche d'un candidat "solitaire nu")</font><br />▼
Cette recherche consiste à examiner si, pour une case donnée (la case <FONT COLOR="red" FACE="Book Antiqua">Cd</FONT> dans l'exemple 02a ci-dessous), il n'y aurait pas une seule valeur possible (valeur unique, encore appelée "solitaire nu", par opposition aux solitaires "camouflés" que nous avons rencontrés dans la technique précédente).<br
▲== Recherche des valeurs uniques==
▲<font size=1>(ou recherche d'un candidat "solitaire nu")</font>
▲Cette recherche consiste à examiner si, pour une case donnée (la case <FONT COLOR="red" FACE="Book Antiqua">Cd</FONT> dans l'exemple 02a ci-dessous), il n'y aurait pas une seule valeur possible (valeur unique, encore appelée "solitaire nu", par opposition aux solitaires "camouflés" que nous avons rencontrés dans la technique précédente).<br><br>
Pour cela, il suffit :
<TABLE style="background-color:#FFFFCC" BORDER="1" CELLPADDING="5" WIDTH="95%"><TR><TD WIDTH="100%">
Ligne 177 ⟶ 160 :
* de compter le nombre de ces cases remplies
* et si l'on en trouve 8 (et à condition que l'on n'ait pas fait d'erreur !), d'attribuer à la case étudiée la valeur qui ne fait pas partie des 8 valeurs déjà inscrites.
</TD></TR></TABLE
<font id=ex02a> </font>
<TABLE BORDER=0 CELLPADDING=0 WIDTH=80%>
Ligne 188 ⟶ 170 :
</TR>
</TABLE>
Cette technique est la plus simple à comprendre mais elle est plus lourde à mettre en oeuvre 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
▲Cette technique est la plus simple à comprendre mais elle est plus lourde à mettre en oeuvre que la précédente, puisqu'en principe, elle devrait être envisagée pour toutes les cases restant vides.<br><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><br>
Notons que si une région (ligne, colonne ou pavé) possède déjà 8 valeurs
renseignées (situation qui ne se produit que fort rarement au début de la résolution d'un sudoku, mais est au contraire très fréquente en fin de résolution), la valeur à attribuer à la dernière case vide est évidente,
comme dans l'exemple qui suit :
<TABLE BORDER=0 CELLPADDING=0 WIDTH=80%>
<TR>
Ligne 208 ⟶ 187 :
</TR>
</TABLE>
<font id=Tech03> </font>
Ligne 217 ⟶ 193 :
Il s'agit d'une extension de la première méthode (élimination directe en quatre temps - <B><FONT COLOR="black">a</FONT></B>
- <B><FONT COLOR="black">b </FONT></B>- <B><FONT COLOR="black">c</FONT></B> et - <B><FONT COLOR="black">d</FONT></B>)
dans laquelle le "temps - <B><FONT COLOR="black">b</FONT></B>" est complété par l' éventuelle <FONT COLOR="#993300">élimination de cases supplémentaires</FONT> (quand elle est possible).<br
Voici donc les quatre "temps" de cette méthode :
<TABLE style="background-color:#FFFFCC" BORDER="1" CELLPADDING="5" WIDTH="95%"><TR><TD WIDTH="100%">
*
*
*
*
</TD></TR></TABLE>
Voici un premier exemple :
<TABLE BORDER=1 CELLPADDING=10px WIDTH=82%>
<TR><TD><DIV ALIGN="CENTER">
Ligne 249 ⟶ 222 :
<TD WIDTH=47%>[[Image:Sdk ex03A4.gif|frame|exemple 03a - étape d]]</TD></TR></TABLE>
</DIV></TD></TR></TABLE>
Voici un second exemple <FONT SIZE="1">(pour lequel on a seulement illustré l'étape <B><FONT COLOR="black">b</FONT></B>)</FONT> :
Ligne 263 ⟶ 235 :
</TR>
</TABLE>
Voici enfin un troisième exemple <FONT SIZE="1">(plus complexe car il illustre un cas de doublement de la phase - <B><FONT COLOR="black">b</FONT></B> et qui, à ce titre, mérite d'être illustré par 4 images successives)</FONT> :
Ligne 287 ⟶ 257 :
</DIV></TD></TR></TABLE>
Cette méthode d'élimination indirecte est en général considérée comme un cas particulier de la méthode des régions dominantes. Ce point de vue est assez discutable car elle ne nécessite pas, pour sa mise en œuvre, de procéder à l'identification fastidieuse des "candidats" de toutes les cases non renseignée.<br><br>
La méthode d'élimination indirecte, facile et plus rapide à mettre en œuvre que la méthode de recherche des valeurs uniques, est d'un grand intérêt car elle permet :
=Trois techniques élaborées=
| |||