An Integer Linear Programming Model for the Evolomino Puzzle

Cet article présente un modèle de programmation linéaire en nombres entiers pour formaliser et résoudre le puzzle logique Evolomino, incluant un algorithme de génération d'instances garantissant une solution unique et démontrant l'efficacité d'un solveur CP-SAT sur des grilles allant jusqu'à 18x18.

L'essentiel

Voici une explication simple et imagée de ce papier de recherche, comme si on en discutait autour d'un café.

🧩 Le Jeu : L'Evolomino, un puzzle qui "grandit"

Imaginez un jeu de logique sur papier, un peu comme les Sudoku ou les Kakuro que vous connaissez peut-être. Ce jeu s'appelle Evolomino.

Le principe est fascinant :

1. Vous avez une grille avec des cases blanches et des cases ombrées (interdites).
2. Sur certaines cases blanches, il y a déjà des flèches dessinées.
3. Votre mission : dessiner des carrés pour former des blocs (des formes géométriques).
4. La règle d'or : Chaque flèche doit traverser au moins deux blocs. Le premier bloc est petit (un seul carré sur la flèche). Le deuxième bloc doit être une copie du premier, mais ajoutée d'un seul carré, sans jamais tourner ni retourner la forme. Le troisième bloc ajoute encore un carré, et ainsi de suite. C'est comme une chenille qui grandit à chaque étape, mais qui garde toujours la même forme de base.

Le défi ? Trouver où placer tous ces carrés pour que tout colle parfaitement, sans se chevaucher, et en respectant la direction des flèches.

---

🧠 Le Problème : Un casse-tête pour les ordinateurs

Pour les humains, c'est un jeu amusant. Pour un ordinateur, c'est un cauchemar mathématique. Pourquoi ? Parce qu'il y a des milliards de façons de placer ces carrés, et vérifier si une solution est bonne ou non demande de faire des millions de calculs.

Les chercheurs de l'article (Andrei et Yuri, de l'Université de Iaroslavl en Russie) se sont dit : "Comment on peut convaincre un ordinateur de résoudre ce jeu rapidement ?"

Ils ont décidé de traduire les règles du jeu en un langage que les super-ordinateurs adorent : la Programmation Linéaire Entière (ILP).

---

🏗️ La Solution : Construire un "Plan de Construction"

Au lieu de laisser l'ordinateur deviner au hasard, les auteurs ont créé un plan de construction mathématique très strict. Imaginez que vous donnez les instructions à un architecte robot :

1. Les Variables (Les briques) : Ils ont dit à l'ordinateur : "Pour chaque case de la grille, tu as un interrupteur. Soit il est allumé (1 = il y a un carré), soit il est éteint (0 = rien)."
2. Les Contraintes (Les règles du jeu) : Ils ont écrit des centaines de règles logiques, comme :
   • "Si une case est allumée, elle doit appartenir à exactement un bloc."
   • "Si le bloc 2 existe, le bloc 1 doit exister avant lui."
   • "La forme du bloc 2 doit être exactement celle du bloc 1, plus un carré, décalée d'un certain nombre de cases."
   • "Tout le bloc doit être connecté, comme une île, pas des îlots séparés."

C'est comme si on donnait à l'ordinateur un immense puzzle où chaque pièce a une seule place possible si on respecte toutes les lois de la physique du jeu.

---

🤖 Le Génie : Créer de nouveaux jeux

Une fois que l'ordinateur sait résoudre le jeu, les chercheurs ont eu une idée brillante : l'inverser.

Au lieu de donner un jeu à résoudre, ils ont demandé à l'ordinateur de créer un nouveau jeu.

• Il dessine une grille.
• Il place des flèches et des carrés au hasard.
• Il utilise son modèle mathématique pour vérifier : "Est-ce qu'il n'y a qu'une seule façon de résoudre ce que je viens de dessiner ?"
• Si oui : C'est gagné ! Il a créé un nouveau puzzle unique.
• Si non (il y a deux solutions possibles) : Il efface tout et recommence.

C'est comme un chef cuisinier qui crée une nouvelle recette, la teste pour s'assurer qu'elle est parfaite, et la propose à ses clients.

---

🚀 Les Résultats : Vitesse de l'éclair

Ils ont testé leur méthode sur un ordinateur moderne. Les résultats sont impressionnants :

• Pour des grilles de 11x11 (un peu plus grandes qu'un Sudoku classique), l'ordinateur trouve la solution en moins d'une seconde. C'est plus rapide que vous ne pouvez lire cette phrase !
• Même pour des grilles géantes de 18x18, il trouve la solution en moins d'une minute.

C'est comme si un détective capable de résoudre un crime complexe en une fraction de seconde, alors que nous, humains, aurions besoin de plusieurs heures de réflexion.

🎯 En résumé

Ce papier nous dit essentiellement :

1. Le jeu Evolomino est un nouveau défi de logique amusant.
2. On peut le transformer en un problème mathématique que les ordinateurs adorent résoudre.
3. Grâce à cette méthode, on peut générer automatiquement des milliers de nouveaux puzzles uniques.
4. Les ordinateurs modernes sont si puissants qu'ils peuvent résoudre ces énigmes complexes presque instantanément.

C'est une belle démonstration de comment les mathématiques pures peuvent rendre les jeux de société plus accessibles et plus variés pour tout le monde !

Résumé technique

Voici un résumé technique détaillé de l'article « An Integer Linear Programming Model for the Evolomino Puzzle » en français.

1. Problématique : Le Puzzle Evolomino

L'article se concentre sur Evolomino, un nouveau puzzle logique papier-crayon publié par l'éditeur japonais Nikoli (apparu en mars 2023). Bien que Nikoli soit célèbre pour des jeux comme le Sudoku ou le Kakuro, l'Evolomino est une variante récente dont les règles complexes n'avaient pas encore été formalisées mathématiquement de manière approfondie.

Règles principales :

• Le jeu se déroule sur une grille rectangulaire avec des cellules blanches et ombrées.
• Le joueur doit dessiner des carrés (□) dans certaines cellules blanches pour former des blocs (des polyominos connectés horizontalement et verticalement).
• Chaque bloc doit contenir exactement un carré placé sur une flèche pré-imprimée.
• Chaque flèche doit traverser au moins deux blocs.
• Mécanique d'évolution : Les blocs successifs le long d'une flèche doivent « évoluer » en ajoutant exactement un carré au bloc précédent, sans rotation ni réflexion.

Complexité théorique :
Une étude précédente [22] a démontré que la décision de l'existence d'une solution valide pour un Evolomino est NP-complète, et que le problème de comptage des solutions distinctes est #P-complet.

2. Méthodologie : Modélisation par Programmation Linéaire en Nombres Entiers (PLNE)

Les auteurs proposent une modélisation complète du puzzle sous forme de Programme Linéaire en Nombres Entiers (ILP). Cette approche vise à encoder les règles du jeu, la connectivité et l'évolution des blocs via des contraintes linéaires.

A. Variables et Notations

Le modèle utilise plusieurs types de variables pour représenter l'état de la grille :

• Variables de cellule ($x_i$) : Indiquent si une cellule contient un carré (1) ou non (0).
• Variables de bloc ($y_{i,k}^a$) : Indiquent si la cellule $i$ appartient au $k$-ième bloc de la flèche $a$.
• Variables d'activation ($b_{k}^a$) : Indiquent si le bloc $k$ de la flèche $a$ existe.
• Variables de flux ($f_{ij}^{ak}$) : Utilisées pour garantir la connectivité des polyominos (modèle de flux basé sur Gavish et Graves).
• Variables de translation ($t_{j}^{ak}$) : Indiquent le décalage (translation) appliqué pour passer du bloc $k-1$ au bloc $k$.

B. Contraintes Clés

Le modèle intègre plusieurs ensembles de contraintes :

1. Contraintes de base :
   • Chaque carré appartient à exactement un bloc.
   • Deux carrés consécutifs ne peuvent pas être placés sur une flèche (pour éviter la fusion non désirée).
   • Les blocs sont activés séquentiellement (le bloc $k$ ne peut exister que si $k-1$ existe).
   • La taille des blocs augmente d'exactement un carré à chaque étape ($N_k = N_{k-1} + 1$).
2. Connectivité (Flux) :
   • Un modèle de flux assure que chaque bloc forme un polyomino connexe. Une source de flux est placée sur la cellule de la flèche, et le flux doit atteindre toutes les autres cellules du bloc.
3. Évolution des blocs (Géométrie) :
   • Des contraintes de correspondance garantissent que la forme du bloc $k$ est obtenue en ajoutant un seul carré au bloc $k-1$ via une translation pure (pas de rotation). Cela préserve la géométrie relative des carrés.

C. Algorithme de Génération de Puzzles

Pour créer un jeu de données de référence, les auteurs développent un algorithme (Algorithm 1) qui génère des instances avec une solution unique :

1. Remplissage : Une marche aléatoire biaisée dessine des flèches sur une grille vide.
2. Placement des blocs : Un processus récursif place les blocs le long des flèches en respectant les règles d'évolution.
3. Affinement (Carving) : Une fois une solution valide obtenue, l'algorithme retire itérativement les indices (carrés pré-dessinés et cellules ombrées) tout en vérifiant, via le solveur ILP, que la solution reste unique. Si un retrait crée une ambiguïté, l'indice est rétabli.

3. Résultats Expérimentaux

Les auteurs ont évalué leur modèle sur un jeu de données personnalisé contenant 700 instances (500 avec solution unique, 200 avec solution garantie mais pas nécessairement unique), allant de 5x5 à 18x18.

• Solveurs comparés : Quatre solveurs de la bibliothèque OR-Tools (Google) ont été testés : CP-SAT, SCIP, CBC et BOP.
• Performance : Le solveur CP-SAT s'est avéré nettement supérieur.
  • Il a résolu 100 % des instances 10x10 en moins de 180 secondes (contre 94-96 % pour les autres).
  • Il a résolu 48 instances sur 50 en moins d'une seconde pour la taille 10x10.
• Évolutivité :
  • Jusqu'à 11x11 : Temps médian < 1 seconde.
  • Jusqu'à 14x14 : Temps médian < 5 secondes.
  • Jusqu'à 18x18 : Temps médian < 1 minute (48 secondes).
• Complexité du modèle : Pour une instance 18x18, le modèle contient environ 40 000 variables et 1 million de contraintes linéaires. La croissance du nombre de contraintes est cubique par rapport à la taille de la grille ($O(K \cdot |C|^2)$), principalement due aux contraintes de correspondance géométrique.

4. Contributions Clés

1. Formalisation ILP : Première modélisation complète des règles d'Evolomino en programmation linéaire en nombres entiers, couvrant la connectivité des polyominos et l'évolution géométrique stricte.
2. Algorithme de génération : Méthode robuste pour générer automatiquement des puzzles d'Evolomino avec une solution unique, comblant un vide dans la disponibilité de jeux de données pour ce nouveau genre.
3. Benchmarking : Création d'un ensemble de données de référence et évaluation comparative des solveurs modernes sur ce problème spécifique.

5. Signification et Perspectives

Cet article démontre que, malgré la complexité théorique (NP-complet et #P-complet) du problème d'Evolomino, les solveurs modernes de type CP-SAT (Constraint Programming + SAT) peuvent le résoudre efficacement pour des tailles de grille pertinentes (jusqu'à 18x18) en un temps raisonnable.

Cela valide l'approche « transform-and-conquer » (transformer le problème en un modèle d'optimisation et le conquérir avec un solveur) pour les puzzles logiques complexes. Les auteurs suggèrent que des recherches futures pourraient explorer d'autres approches comme la programmation par contraintes pure, les modèles SAT, ou l'algorithme DLX (Dancing Links) pour le placement de polyominos, afin de comparer l'efficacité relative de ces méthodes.

En résumé, ce travail fournit non seulement un outil puissant pour résoudre et générer des puzzles Evolomino, mais enrichit également la littérature sur la modélisation mathématique des jeux de logique modernes.