<p class="spip">Vous connaissez sûrement ce passe temps qui fait fureur en ce moment, je veux bien sur parler du SuDoku.</p>

<p class="spip">Pour ceux qui ne connaîtraient pas, une petite recherche dans google vous retournera 68 millions de pages !
Si vous avez échappé à l’épidémie, <a href="http://www.e-sudoku.fr/regle-grille-sudoku.php" class="spip_out">ce lien</a> vous expliquera les règles du jeu. Pour plus de renseignements <a href="http://fr.wikipedia.org/wiki/Sudoku" class="spip_out">wikipedia</a> est votre ami.</p>

<p class="spip">Je vous propose de réaliser un programme en python pour trouver la solution des grilles de SuDoku qu’on trouve un peu partout.</p>

<h3>Éléments abordés dans ce document</h3>
<p class="spip">En plus des différents sujets abordés dans les tutoriels précédents, voici les nouvelles notions que nous allons découvrir :
<br /></p>
<li> Les threads  « avec QThread, QCustomEvent(), setData(), postEvent() »
<br /><li> Une astuce pour adresser toutes les cases de la grille « avec getAttr() »
<h3>Au travail</h3>
<p class="spip">Avant toutes choses, il va falloir choisir le mode de représentation de la grille.</p>

<p class="spip"><span class='spip_document_840 spip_documents spip_documents_center' >
<img src='http://download.tuxfamily.org/assocoagul/drupal-files/spip/data-2.jpg' width="316" height="316" alt="" /><span>
81 cases numérotées de 0 à 80</p>

<p class="spip">9 lignes, 9 colonnes et 9 boîtes numérotées de 0 à 8</p>

<p class="spip">Puis on va définir 3 fonctions pour retrouver les valeurs stockées dans les lignes, colonnes et boîtes :</p>
<div style='text-align: left;' class='spip_code' dir='ltr'><code><br />
lig[x]=[9i,9i+1,9i+2,9i+3,9i+4,9i+5,9i+6,9i+7,9i+8]<br />
(avec i=x/9)<br />
<br />
col[x]=[i,i+9,i+18,i+27,i+36,i+45,i+54,i+63,i+72]<br />
(avec i=x%9)<br />
<br />
box[x]=[i,i+1,i+2,i+9,i+10,i+11,i+18,i+19,i+20]<br />
(avec i=(x/27)*27+(x%9/3)*3 <br />
</code></div>
<p class="spip">nota : / pour la division entière</p>

<p class="spip">Cet algorithme de mon crû utilise la technique du back-tracking. Il cherchera toutes les solutions possibles en partant de la première case et en testant toutes les valeurs possibles par ordre croissant. En cas de blocage, on retourne en arrière et on prend la valeur suivante etc ...</p>

<p class="spip">Cette méthode très simple me permet d’expliquer à un enfant comment les ordinateurs peuvent faire pour trouver des solutions. Il suffit pour cela d’une feuille de papier et d’un crayon et suivre la recette décrite plus bas en la faisant tourner à la main.</p>

<p class="spip">Il est clair qu’elle n’est certainement pas la plus rapide.</p>

<p class="spip">On utilise <i class="spip"> <strong class="spip">grille</strong> </i> qui contient le problème à résoudre et <i class="spip"> <strong class="spip">grilleTemp</strong> </i> qui contient la solution en cours de calcul.</p>

<p class="spip"><i class="spip"> <strong class="spip">lig(i)</strong> </i> retourne l’ensemble des valeurs déjà utilisées pour la ligne i (idem pour <i class="spip"> <strong class="spip">col()</strong> </i> et <i class="spip"> <strong class="spip">box()</strong> </i>)</p>

<p class="spip"><i class="spip"> <strong class="spip">valMinSup([],x)</strong> </i> retourne la plus petite valeur possible supérieure à x en éliminant les valeurs présentes dans la liste</p>

<p class="spip">Ceci donne en pseudo code :</p>
<div style='text-align: left;' class='spip_code' dir='ltr'><code><br />
grilleTemp = grille<br />
i = 0<br />
Boucler<br />
        si grille(i) est vide<br />
                nouvelleValeur = valMinSup(lig(i)+col(i)+box(i), grilleTemp(i))<br />
                si nouvelleValeur correcte<br />
                        grilleTemp(i) = nouvelleValeur<br />
                        i += 1<br />
                sinon<br />
                        grilleTemp(i) = 0<br />
                        tantQue i>0 et grille(--i) non vide<br />
        sinon<br />
                i += 1<br />
        si i < 0<br />
                fin du programme sans avoir trouvé de solution<br />
        si i > 80<br />
                fin du programme, la solution est dans grilleTemp<br />
</code></div>
<p class="spip">C’est tout, en fait le programme est vraiment très simple. Nous pouvons maintenant utililser nos outils favoris (eric et QT Designer) pour créer ce programme.</p>

<p class="spip">QT Designer nous permet de créer ceci :
<span class='spip_document_836 spip_documents spip_documents_center' >
<img src='http://download.tuxfamily.org/assocoagul/drupal-files/spip/sudoku.jpg' width="403" height="527" alt="" /></span><p>

<p class="spip">Pour le code, pas de difficulté particulière hormis la petite astuce qui permet d’adresser toutes les cases de la grille dans une boucle.</p>
<div style='text-align: left;' class='spip_code' dir='ltr'><code><br />
       for i in range(81):<br />
            a=getattr(self, "lineEdit%d" % i)<br />
            a.setText('')<br />
</code></div>
<p class="spip">Par contre, la fonction qui cherche la solution est une candidate idéale pour un thread. En effet si la recherche est un peu longue, l’application se fige. Lors de mes tests, la grille la plus simple a été trouvée après 242 tests tandis que la plus compliquée en a nécessitée 229 425, soit 11 secondes de calcul sur mon P4-3GHz.</p>

<p class="spip">Pour le multi-threading, j’ai suivi les recommandations de cet <a href="http://www.samspublishing.com/articles/article.asp?p=30708&seqNum=4" class="spip_out">article</a> (en anglais).
Le point important à ne pas oublier avec les threads, c’est qu’il n’est pas possible d’échanger des données directement avec le programme principal. Il faut passer par la fonction customEvent(), sinon, c’est le segfault assuré.</p>

<h2>Historique des modifications</h2>
<table class="spip">
<thead><tr class='row_first'><th scope='col'><strong class="spip">Version</strong></th><th scope='col'><strong class="spip">Date</strong></th><th scope='col'><strong class="spip">Commentaire</strong></th></tr></thead>
<tbody>
<tr class="row_even"><td>0.1</td><td>09/04/2006</td><td>Création par Jibux</td></tr>
<tr class="row_odd"><td>0.2</td><td>15/04/2006</td><td>Ajout d’info et liens (merci [Nemo])</td></tr>
<tr class="row_even"><td>0.3</td><td>13/06/2006</td><td>Simplification formule box[x] (merci lessap.regor)</td></tr>
</tbody>
</table>
<p class="spip">TODO : mettre à jour les fichiers sources suite simplification.</p>
<dl class='spip_document_841 spip_documents spip_documents_left'  style='float:left;width:120px;'>
<dt><a href="http://download.tuxfamily.org/assocoagul/drupal-files/spip/Archive-7.zip" title='Zip - 10 ko' type="application/zip"><img src='dist/vignettes/zip.png' width='52' height='52' alt='Zip - 10 ko' /></a><dt>
<dt class='spip_doc_titre' style='width:120px;'><strong>Les fichiers sources de cette application</strong></dt>
</dl>