Ludique

Jeu Edel

L’objectif de ce jeu de réflexion est de reconstituer un dessin caché sous une grille en s’appuyant sur des indices numériques. Le dessin apparaît au fur et à mesure que le joueur noircit des cases.

Une grille résolue.

Dans le jeu Edel, le but du joueur est de retrouver la position de cases noires dans une grille, de façon à satisfaire les contraintes posées sous la forme d’une suite ordonnée de nombres, sur chaque ligne et chaque colonne de la grille. Chaque nombre spécifie la taille d’un groupe de cases noires contiguës dans la ligne ou la colonne. Tout groupe de cases doit être séparé du précédent et du suivant par au moins une case vide. Il peut également y avoir des cases vides en début ou en fin de ligne ou de colonne, sans que cela soit obligatoire.

Par exemple, dans une grille 10×10, si une ligne est précédée de la série de nombres 2 1 3, il devra à la fin apparaître de gauche à droite sur la ligne un groupe de deux cases noires, suivi d’une case noire isolée, suivie elle-même d’un groupe de trois cases. Cela laisse au total dix possibilités, quatre sont représentées ci-dessous, à vous d’imaginer les autres.

            

 
De la même façon, chaque colonne est surplombée d’une série de nombres qui indiquent la longueur des groupes de cases à noircir consécutivement du haut vers le bas.

Le jeu Edel (également connu sous une trentaine d’autres noms : Picross, Nonograms, Pixel Puzzles, Logimage, Griddlers, Paint by numbers, etc.) appartient ainsi, comme le sudoku, à la famille des jeux qui requièrent la résolution de problèmes combinatoires. La génération comme la résolution de ces grilles peut se faire par un programme informatique.

Nous vous proposons de jouer à Edel sur l'applet ci-dessous. Deux tailles de grilles à résoudre vous sont proposées, 10×10 ou 15×15.

Pour noircir une case, il suffit de cliquer dessus. Lorsque vous trouvez une nouvelle case, la jauge de résolution progresse. Si vous tentez de noircir une case vide, une croix apparaît et votre jauge d’erreur monte d’une unité. Mais attention à ne pas remplir entièrement cette jauge, sous peine de perdre la partie ! Trouver une cellule qui restera nécessairement vide peut s’avérer aussi important que de trouver une case noire. Il est préférable de ne marquer que les cases pour lesquelles la valeur (pleine ou vide) est connue de façon certaine. Si vous détectez une case vide, vous pouvez placer vous-même une croix dessus en cliquant avec le bouton droit de la souris ; n’hésitez pas à utiliser cette possibilité. Le jeu se termine lorsque vous avez entièrement découvert le dessin… ou lorsque la jauge d’erreurs est pleine.

 
Cette applet a été réalisée dans le cadre d'un projet étudiant de l'École Polytechnique de l'Université de Tours
et finalisée par Chi Thanh Bui, encadré par Yannick Kergosien, Christophe Lenté et Jean-Charles Billaut.
 

Génération des grilles

Lorsque l’on conçoit une grille d’Edel, on se heurte à une difficulté : il est possible que plusieurs dessins puissent correspondre à cette grille. Cela se produit en particulier s’il existe trop de symétries ou s’il y a trop peu de cases à noircir. L’exemple le plus simple que l’on puisse imaginer est la grille suivante, qui correspond à deux possibilités.

                    

 
C'est également le cas de cette grille, qui admet elle aussi au moins deux solutions (bien plus en fait).

                    

 
Afin d’éviter ce travers, les grilles générées par notre programme informatique ont été testées par une méthode de programmation par contraintes et seules celles menant à un unique dessin ont été retenues.

Il est également à noter que les grilles ont été générées aléatoirement, ceci dans le souci ne pas donner d’indices implicites au joueur. Vous ne verrez donc pas apparaître de dessins figuratifs…

Pistes de résolution

De manière générale, il vaut mieux commencer par les lignes ou les colonnes les plus contraintes et identifier le maximum de cases pleines ou vides. Voici quelques exemples et ce qu’il est possible d’en déduire.

  1. Un cas extrêmement simple pour commencer. Supposons que la grille contienne la ligne suivante :

    Cette ligne fait 10 cases, il faut noircir 10 cases, il n’y a donc qu’une seule possibilité !

  2. Un cas à peine plus compliqué, supposons que la grille contienne la ligne :

    Il y a au total 8 cases à noircir et il y a trois groupes donc au minimum deux cases vides pour séparer ces groupes. 8+2=10, il n’y a donc à nouveau qu’une seule possibilité.

    On a pu sur cet exemple déterminer des cases vides et des cases pleines, mais bien souvent on ne peut identifier que certaines cases pleines, les cases vides sont plus délicates à repérer.
     
  3. Que peut-on dire si la ligne admet plusieurs remplissages possibles, comme celle indiquée ci-dessous ?

    Il y a trois possibilités, on ne peut donc pas dire avec précision quelles seront les cases noircies, néanmoins on peut tirer des renseignements des deux positions extrêmes :
    tout à gauche : et tout à droite :

    On observe que de la troisième à la huitième position, les cases sont forcément noircies, on connait donc à coup sûr 6 cases noires sur 8. Les autres devront être déduites à partir des renseignements sur les colonnes.

  4. Cette technique peut se généraliser à plusieurs groupes, mais elle sera d’autant moins efficace que les groupes seront petits ou qu’ils seront libres de bouger de gauche à droite. Par exemple, si la ligne à remplir est :

    Les deux positions extrêmes sont alors :
    tout à gauche : et tout à droite :

    Dans ce cas de figure, beaucoup moins favorable que le précédent, les deux positions extrêmes ne permettent de détecter qu’une seule case à noircir. Pour le voir, il faut raisonner groupe par groupe. Le premier groupe, qui fait 2 cases, a comme positions extrêmes [case 1 - case 2] et [case 3 - case 4] : il n’y a aucune case commune, donc aucune déduction possible. Le deuxième groupe ne fait qu’une seule case, il ne permettra donc aucune déduction. Le dernier groupe fait 3 cases, ses positions extrêmes sont [case 6 à case 8] et [case 8 à case 10], la huitième case est donc forcément noircie.

  5. Au fur et à mesure que l’on avance dans le jeu, on remplit ou on interdit des cases. Ces informations peuvent être utiles pour améliorer les déductions. Reprenons l’exemple 4 et imaginons que nous sachions de plus que la case 5 est noircie.

    Cette case correspond forcément au deuxième groupe (celui de taille 1), il suffit pour s’en convaincre d’observer les configurations « tout à gauche » et « tout à droite » du 4. Cela implique que les cases 4 et 6 sont vides. De plus, les libertés de mouvement des deux autres groupes vont être limitées par cette case 5. Voici les deux positions extrêmes :
    tout à gauche : et tout à droite :

    On en déduit que les cases 2, 8 et 9 sont également à noircir.

Résolution d’une grille

À titre d’entraînement, appliquons ce qui précède sur un exemple de grille.

 
En traitant d’abord toutes les lignes, puis toutes les colonnes, puis à nouveau toutes les lignes, on réussit à remplir progressivement la grille :

      

 
Un dernier passage sur les colonnes nous apporte la solution finale.

Lien avec la recherche

Pour résoudre des problèmes d'optimisation combinatoire, les chercheurs utilisent et adaptent plusieurs types de méthodes. La démarche proposée ici s'apparente à une technique de gestion de projets qui s’appelle « raisonnement énergétique ». Dans sa formulation la plus générale, cette méthode consiste à calculer des parties « obligatoires » de consommation de ressources nécessaires à l’exécution d’un projet. Par exemple, s'il est prévu qu'une tâche dure 4 heures et qu'elle doit être exécutée entre midi et 18 heures, on peut en déduire que les ressources affectées à cette tâche seront obligatoirement utilisées de 14 heures à 16 heures.

Tags

Niveau de lecture

Aidez-nous à évaluer le niveau de lecture de ce document.

Il vous semble :

Si vous souhaitez expliquer votre choix, vous pouvez ajouter un commentaire (qui ne sera pas publié).