Les Newsletters Interstices
Interface de l'animation : une grille résolue
    Niveau intermédiaire
    Niveau 2 : Intermédiaire

    Jeu Edel

    Culture & Société
    Algorithmes
    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.

    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’animation 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, la case devient rouge 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.

    Comment jouer ? Tout d’abord, choisissez une taille de grille : 10 × 10 ou 15 × 15.

    Au départ, les cases sont toutes vides. Le but du jeu est de les colorier en vous aidant des nombres indiqués pour chaque ligne et chaque colonne de la grille. Par exemple, lorsqu’il est noté : 5 4 2 1, cela signifie que vous aurez dans la ligne ou la colonne correspondante un bloc de 5 cases consécutives, puis un bloc de 4 cases, un bloc de 2 cases et un bloc de 1 case. L’ordre des nombres est l’ordre des blocs de cases, de gauche à droite ou de haut en bas.

    Aidez-vous de ces indications horizontales et verticales pour réussir à remplir les bonnes cases. Vous verrez apparaître à la fin le dessin formé par toutes les cases coloriées.

    Pour jouer :

    • Colorier une case : clic gauche
    • Mettre une croix dans une case : clic droit

    Les croix peuvent vous permettre de mieux visualiser les cases restant à remplir.

    Les deux jauges à droite vous indiquent le pourcentage de cases que vous avez correctement coloriées et la quantité d’erreurs commises. Vous avez droit à un indice et à quelques erreurs, proportionnellement au nombre de cases à colorier : de l’ordre de 12 pour la petite grille et 25 pour la grande. Lorsque vous avez commis trop d’erreurs, la jauge est pleine et vous perdez la partie.

    Bonne chance !

    L’applet a été réalisée en Java dans le cadre d’un miniprojet à l’École polytechnique de l’Université de Tours, par Florent Renault et Émilie Graziana, étudiants de 4e année en 2008, encadrés par Yannick Kergosien.

    Elle a été finalisée pour le site Interstices par Chi Thanh Bui au cours de son projet de fin d’études 2009-2010, encadré par Yannick Kergosien, Christophe Lenté et Jean-Charles Billaut.

    Elle a été transposée en HTML5/JS par Corentin Wallez, XProjets. Cette version a été améliorée par Ouest INSA.

    Image de fond par Souzan Memari (souzan@memari.fr).

    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 de 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.

    Newsletter

    Le responsable de ce traitement est Inria. En saisissant votre adresse mail, vous consentez à recevoir chaque mois une sélection d'articles et à ce que vos données soient collectées et stockées comme décrit dans notre politique de confidentialité

    Niveau de lecture

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

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

    Votre choix a été pris en compte. Merci d'avoir estimé le niveau de ce document !

    Christophe Lenté

    Voir le profil

    Yannick Kergosien

    Maître de conférences à l'Université de Tours (Laboratoire d'informatique) et à l'École Polytechnique de l'Université de Tours.

    Voir le profil

    Jean-Charles Billaut

    Professeur à l'Université de Tours, directeur du Laboratoire d'informatique et enseignant à l'École Polytechnique de l'Université de Tours, ancien président de l'association ROADEF.

    Voir le profil

    Découvrez le(s) dossier(s) associé(s) à cet article :

    DossierCulture & Société

    TIPE 2023 – 2024 : Jeux, sports

    Ces articles peuvent vous intéresser

    ArticleCulture & Société
    Algorithmes

    La combinatoire des Sudokus

    Yan Georget

    Niveau intermédiaire
    Niveau 2 : Intermédiaire
    ArticleLangages, programmation & logiciel

    La programmation par contraintes

    Étienne Parizot
    Sylvain Soliman
    François Fages

    Niveau facile
    Niveau 1 : Facile