On the Exact Algorithmic Extraction of Finite Tesselations Through Prime Extraction of Minimal Representative Forms

Cet article présente un algorithme hiérarchique déterministe capable d'extraire avec exactitude des pavages rectangulaires finis à partir de grilles discrètes en utilisant des techniques de découverte composite et d'extraction de formes représentatives minimales, comblant ainsi une lacune dans l'analyse symbolique des structures périodiques.

L'essentiel

🕵️‍♂️ Le Grand Détective des Motifs : Comment l'ordinateur apprend à "voir" les répétitions

Imaginez que vous avez un immense puzzle géant posé sur une table. Ce puzzle est fait de milliers de petits carrés de couleurs différentes. Parfois, si vous regardez bien, vous vous rendez compte que ce n'est pas un chaos total : il y a des motifs qui se répètent. Par exemple, un petit carré bleu-rouge qui apparaît 50 fois à travers la table.

Le problème, c'est que les ordinateurs actuels (surtout ceux qui utilisent l'intelligence artificielle) sont très forts pour deviner ce qu'ils voient dans une photo floue, mais ils sont souvent très mauvais pour dire : "Attends, ce motif exact de 2x2 se répète ici, là et là, et c'est la seule règle qui explique tout."

C'est là que cette équipe de chercheurs (de l'Université Chulalongkorn en Thaïlande) intervient. Ils ont créé un algorithme (une recette mathématique) qui agit comme un détective très rigoureux pour trouver ces répétitions exactes, sans se tromper.

---

🧱 L'Analogie des Lego : "Les Briques Mères" et "Les Briques Filles"

Pour comprendre leur méthode, imaginez que votre grand puzzle est construit avec des Lego.

1. Le problème : Vous voyez un mur énorme. Vous voulez savoir : "Est-ce que ce mur est fait en empilant un seul petit bloc de Lego, ou est-ce que c'est un mélange compliqué ?"
2. La solution des chercheurs : Ils ne regardent pas le mur entier d'un coup. Ils utilisent une stratégie en trois étapes magiques :

Étape 1 : Le "Détective des Gros Blocs" (Découverte Composite)

Le détective commence par regarder le mur entier.

• L'astuce : Il demande : "Si je coupe ce mur en deux (en haut/bas ou gauche/droite), les deux moitiés sont-elles identiques ?"
• Le cas bizarre (les nombres impairs) : Parfois, le mur a une taille bizarre (par exemple 5 rangées). On ne peut pas couper 5 en deux parts égales ! Alors, l'algorithme fait un tour de magie : il duplique la rangée du milieu temporairement pour pouvoir couper. C'est comme si on ajoutait un Lego fantôme pour faire la coupe, puis on l'enlève après.
• Le résultat : S'il trouve une moitié qui se répète, il dit : "Aha ! Ce grand mur est juste une copie de ce petit bloc !".

Étape 2 : Le "Réducteur de Taille" (Normalisation)

Une fois qu'il a trouvé un bloc qui se répète, il se demande : "Ce bloc est-il le plus petit possible ?"

• Il regarde le bloc trouvé. Est-ce qu'il est lui-même fait de deux blocs plus petits identiques ?
• S'il répond oui, il le coupe encore ! Il continue de couper jusqu'à ce qu'il ne puisse plus couper.
• Le but : Trouver la "Brique Atomique" (ou Prime en anglais). C'est la plus petite brique Lego possible qui, si on la copie et colle, reconstruit tout le motif. C'est comme réduire une image à son fichier le plus petit possible sans perdre de qualité.

Étape 3 : Le "Tri Intelligent" (Filtrage Hiérarchique)

C'est ici que l'algorithme devient très malin et rapide.

• Imaginez que vous avez trouvé un gros motif, et que vous avez aussi trouvé un petit motif qui est à l'intérieur du gros.
• Au lieu de perdre du temps à analyser le petit motif séparément, l'algorithme se dit : "Attends, j'ai déjà trouvé ce petit motif quand j'ai analysé le gros. Je n'ai pas besoin de le chercher à nouveau."
• Il oublie (ou "prune") les recherches inutiles. C'est comme si vous aviez une liste de courses : si vous avez déjà acheté les ingrédients pour faire un gâteau, vous n'avez pas besoin de vérifier si vous avez besoin de farine pour faire un autre gâteau plus tard. Cela rend le calcul 5 fois plus rapide.

---

🚀 Pourquoi est-ce important ? (La Magie du "Pourquoi")

Pourquoi se donner autant de mal pour trouver des carrés qui se répètent ?

1. Pour résoudre des énigmes (ARC-AGI) : Il existe un défi mondial où des IA doivent résoudre des puzzles logiques sur de petites grilles. Les humains voient immédiatement : "Ah, c'est juste une répétition !". Les IA échouent souvent car elles essaient de "deviner" au lieu de "calculer". Cet algorithme donne aux IA la capacité de voir la structure exacte, comme un humain.
2. Pour l'optimisation : Imaginez que vous devez construire un immeuble. Si vous savez que tout l'immeuble est fait de la même fenêtre répétée, vous n'avez pas besoin de dessiner chaque fenêtre. Vous dessinez une seule fenêtre et vous dites : "Copiez-la 1000 fois". Cela économise du temps, de l'argent et de l'énergie.
3. Pour la précision : Contrairement à l'IA classique qui dit "Je pense que c'est un chat", cet algorithme dit : "C'est EXACTEMENT ce motif, répété 42 fois, sans aucune erreur.". C'est crucial pour les tâches où une petite erreur est inacceptable.

📉 En résumé : La performance

Les chercheurs ont testé leur méthode sur des grilles de différentes tailles :

• Sur de petites grilles simples, c'est ultra-rapide (moins d'un milliseconde, plus vite que le clignement d'un œil).
• Sur des grilles très complexes avec du "bruit" (des motifs qui ne sont pas parfaits), cela prend plus de temps, mais l'algorithme reste fiable.

La conclusion simple :
Ils ont créé un outil qui transforme un chaos de couleurs en une recette simple : "Prenez cette petite brique, et répétez-la ici et là.". C'est une façon de donner aux ordinateurs un sens de la logique pure et de la structure, là où ils avaient l'habitude de seulement faire des statistiques approximatives.

C'est un peu comme passer d'un peintre qui essaie de deviner la forme d'un nuage, à un architecte qui sait exactement combien de briques il faut pour construire le bâtiment. 🏗️✨

Résumé technique

1. Problématique et Contexte

L'article aborde le problème de l'identification exacte et déterministe de motifs de pavage (tessellations) dans des grilles planaires finies discrètes. Bien que les approches statistiques et l'apprentissage machine soient efficaces pour reconnaître des motifs dans des données bruitées ou floues (comme des images réelles), elles échouent souvent à fournir des extractions symboliques exactes nécessaires pour le raisonnement logique, la synthèse de programmes et l'optimisation structurelle.

Le défi spécifique traité ici est l'extraction de structures périodiques rectangulaires où :

• Plusieurs motifs indépendants peuvent coexister sur la même grille.
• Les motifs peuvent être hiérarchiques (un motif contenant d'autres motifs).
• Les dimensions peuvent être impaires, compliquant le découpage symétrique.
• L'objectif est de trouver les « briques de base » (primes) minimales qui reconstruisent la grille par translation, sans rotation ni déformation.

Ce problème est motivé par les défis du corpus ARC-AGI (Abstraction and Reasoning Corpus), où les solutions actuelles par apprentissage automatique peinent à inférer des règles de pavage exactes à partir de quelques exemples.

2. Méthodologie Proposée

Les auteurs proposent un algorithme hiérarchique en trois phases principales, combinant découverte composite, normalisation et extraction de nombres premiers (primes).

A. Découverte Composite (Composite Discovery)

Cette phase identifie les régions de la grille présentant un chevauchement interne (répétition).

• Inspection initiale : L'algorithme vérifie si la grille entière (ou une grille élaguée des bordures vides) peut être divisée en deux moitiés identiques (lignes ou colonnes).
• Gestion des dimensions impaires : Une technique de duplication sélective est utilisée ici. Si une dimension est impaire, la ligne ou la colonne centrale est dupliquée avant le découpage pour permettre une vérification de chevauchement.
• Élagage par BFS (Breadth-First Search) : Si l'inspection échoue, l'algorithme explore systématiquement tous les sous-rectangles en élaguant les bords (haut, bas, gauche, droite).
• Filtrage hiérarchique : Les composites sont traités par ordre décroissant de taille. Si un composite plus petit est découvert comme étant un composant d'un plus grand, il est ignoré pour éviter les redondances (mémoïsation).

B. Normalisation

Une fois un composite trouvé, il est réduit à sa forme représentative minimale.

• L'algorithme divise itérativement le composite par la moitié (lignes ou colonnes) tant que les deux moitiés sont identiques.
• La duplication sélective est également utilisée ici pour gérer les dimensions impaires, garantissant que le processus de réduction ne bloque pas.
• Le résultat est un « composite normalisé » qui ne peut plus être divisé symétriquement.

C. Extraction de Primes (Prime Extraction)

Cette phase décompose les composites normalisés en leurs éléments atomiques (primes).

• L'algorithme applique un élagage BFS sur le composite normalisé.
• Détection de chevauchement : Lorsqu'un sous-rectangle (enfant) présente un chevauchement, la partie chevauchante est normalisée. Si cette forme normalisée peut remplir exactement le rectangle enfant par répétition, elle est enregistrée comme un « prime » avec son nombre maximal d'utilisations.
• Coupe de branche (Branch Cut) : Dès qu'un motif répétitif est identifié, l'exploration des descendants de ce nœud est arrêtée, car ils ne seraient que des fragments du motif déjà découvert.

D. Stratégies de Résolution (Dual-Strategy)

Pour assembler la solution finale, deux stratégies sont proposées :

1. Stratégie Cumulative : Combine les primes trouvés à différents niveaux de profondeur (Niveau 1, puis 1-2, etc.) pour trouver la solution globale avec le nombre minimum de placements de tuiles (optimalité globale).
2. Stratégie par Niveau : Résout le problème indépendamment pour chaque niveau de profondeur, permettant d'analyser les compromis entre l'utilisation de grandes tuiles personnalisées (niveau 1) et de nombreuses petites tuiles standard (niveaux profonds).

3. Contributions Clés

1. Algorithme Déterministe : Première méthode capable d'extraire exactement des motifs de pavage rectangulaires et alignés sur les axes dans des grilles finies, sans ambiguïté statistique.
2. Gestion des Dimensions Impaires : L'utilisation de la duplication sélective uniquement lors de l'inspection et de la normalisation (et non lors de l'élagage BFS) permet de traiter les cas impairs tout en maintenant l'efficacité de la recherche exhaustive.
3. Filtrage Hiérarchique et Mémoïsation : Une technique qui réduit considérablement la complexité computationnelle en évitant de re-traiter les sous-composites déjà identifiés comme composants de structures plus grandes (réduction de 81 % du temps de traitement dans les cas complexes).
4. Extraction de Primes et Hiérarchie : Capacité à identifier non seulement les motifs de base, mais aussi les structures imbriquées et leur fréquence d'utilisation, fournissant une représentation canonique des motifs.

4. Résultats Expérimentaux

Les auteurs ont évalué l'algorithme sur des grilles allant de 2x2 à 32x32, avec trois types de cas de test :

• Band-in-blanks (6x6) : Motif répétitif simple entouré de vide.
• Mixed-noise (6x8) : Motifs irréguliers avec du bruit dispersé.
• Simple-pattern (4x4) : Motif en damier parfaitement symétrique.

Performance :

• Temps de traitement : Pour des motifs simples, la détection prend moins de 1 ms. Pour des motifs complexes nécessitant une recherche exhaustive, le temps croît de manière exponentielle, mais reste gérable pour des tailles de grille raisonnables.
• Efficacité du filtrage : Dans le cas « Mixed-noise », 13 des 16 composites trouvés (81,25 %) ont été ignorés grâce au filtrage hiérarchique, réduisant le temps de la phase la plus coûteuse par un facteur de 5,3.
• Scalabilité : L'analyse montre que la découverte de composites par inspection est constante, tandis que l'extraction de primes par élagage BFS montre une croissance exponentielle, ce qui est inévitable pour un problème NP-dur dans le pire des cas.

5. Signification et Limites

Signification :
Ce travail comble un vide important entre l'analyse statistique (floue) et le raisonnement symbolique (exact). Il offre un outil fondamental pour :

• La résolution de puzzles logiques (comme ARC-AGI).
• L'optimisation de matrices de routage et de planification de trajectoires.
• L'inférence de causalité dans des mondes 2D discrets.
• La synthèse de programmes à partir d'exemples.

Limites :

• L'algorithme est restreint aux tuiles rectangulaires et à la géométrie de Manhattan (pas de rotation).
• Il suppose une égalité exacte des valeurs (pas de tolérance au bruit ou à l'approximation).
• La complexité du solveur de pavage peut devenir exponentielle pour des motifs très complexes sans structure périodique claire.

Conclusion :
Les auteurs concluent que leur méthode fournit une base de référence précise et efficace pour l'identification de structures périodiques exactes. Ils suggèrent des travaux futurs pour étendre la méthode à des correspondances tolérantes (bruitées), à des structures rotatives et à des générateurs non rectangulaires, tout en conservant la rigueur déterministe.