L’objet de cet article est de rappeler cinquante ans plus tard l’intérêt de la programmation logique par contraintes selon un cas d’usage historique et pédagogique : le remplissage d’un rectangle de taille inconnue par un ensemble de carrés de tailles inconnues mais distinctes. L’obligation de différentiation des tailles conduit à se passer de toute hypothèse de symétrie permettant de résoudre plus facilement ce problème.
Il a été prouvé par un mathématicien polonais, Zbigniew Moroń en 1925, que le plus petit ensemble de carrés distincts pavant parfaitement un rectangle est de cardinal 9.
Nous commenterons le comportement du programme Prolog III conçu par Alain Colmerauer qui utilise le domaine des nombres rationnels pour offrir une version automatisée de cette preuve en exploitant une propriété démontrée par le mathématicien Max Dehn, élève de David Hilbert, en 1903 : il ne peut y avoir de solution que si les rapports entre les tailles sont commensurables.
Le programme se lance dans une étude de cas systématique mais fortement combinatoire à la recherche de placements. Il accumule au cours de son cheminement un double ensemble de contraintes additives (selon la hauteur et la largeur du rectangle), donnant lieu à la résolution globale d’un système d’équations et d’inéquations linéaires. Mais tant que ce système reste sous-déterminé, aucune solution partiellement instanciée ne nous aide à entrevoir l’issue du calcul.
Cet article effectue en quelque sorte une rétro-ingénierie des inférences bidimensionnelles effectuées, en explicitant les types de données issus de la méthode de dissection géométrique du problème. La discussion formelle et informelle qui prend place montre à la fois la puissance et la concision déclarative de la programmation logique par contraintes. Elle témoigne aussi de la difficulté à suivre pas à pas les inférences de la belle machinerie opérationnelle qui en coulisse conduit au résultat.
The purpose of this article is to recall, fifty years later, the interest of constraint logic programming according to a historical and pedagogical use case: filling a rectangle of unknown size with a set of squares of unknown but distinct sizes. The obligation to differentiate the sizes precludes the use of any symmetry hypothesis that would make this problem easier to solve.
It was proved by a Polish mathematician, Zbigniew Moroń in 1925, that the smallest set of distinct squares perfectly tiling a rectangle is of cardinal 9. We will comment on the behavior of the Prolog III program designed by Alain Colmerauer which uses the domain of rational numbers to offer an automated version of this proof. It exploits a property demonstrated by Max Dehn, a student of David Hilbert, in 1903: there can only be a solution if the size’s ratios are commensurable.
The program embarks on a systematic but highly combinatorial case study in search of placements. Along the way, it accumulates a double set of additive constraints (according to the height and width of the rectangle), resulting in the global resolution of a system of linear equations and inequalities. But as long as this system remains underdetermined, no partially instantiated solution helps us to glimpse the outcome of the calculation.
By making explicit the data types that derive from the geometric dissection method, this article performs a kind of reverse engineering of the rules applied. The following formal and informal discussion shows both the power and the declarative conciseness of constraint logic programming. It also illustrates the difficulty of tracing the behind-the-scenes inferences of the smart operational machinery that leads to the result.
Accepté le :
Publié le :
Mots clés : Constraint Logic Programming, Mathematical Puzzle, Prolog, Linear constraints on rational numbers
Olivier Bartheye 1 ; Guy Alain Narboni 2
CC-BY 4.0
@article{ROIA_2024__5_2-3_95_0,
author = {Olivier Bartheye and Guy Alain Narboni},
title = {Retour sur un exemple historique en {Prolog~III~:} le d\'ecoupage d{\textquoteright}un rectangle en~carr\'es de tailles distinctes},
journal = {Revue Ouverte d'Intelligence Artificielle},
pages = {95--119},
publisher = {Association pour la diffusion de la recherche francophone en intelligence artificielle},
volume = {5},
number = {2-3},
year = {2024},
doi = {10.5802/roia.74},
language = {fr},
url = {https://roia.centre-mersenne.org/articles/10.5802/roia.74/}
}
TY - JOUR AU - Olivier Bartheye AU - Guy Alain Narboni TI - Retour sur un exemple historique en Prolog III : le découpage d’un rectangle en carrés de tailles distinctes JO - Revue Ouverte d'Intelligence Artificielle PY - 2024 SP - 95 EP - 119 VL - 5 IS - 2-3 PB - Association pour la diffusion de la recherche francophone en intelligence artificielle UR - https://roia.centre-mersenne.org/articles/10.5802/roia.74/ DO - 10.5802/roia.74 LA - fr ID - ROIA_2024__5_2-3_95_0 ER -
%0 Journal Article %A Olivier Bartheye %A Guy Alain Narboni %T Retour sur un exemple historique en Prolog III : le découpage d’un rectangle en carrés de tailles distinctes %J Revue Ouverte d'Intelligence Artificielle %D 2024 %P 95-119 %V 5 %N 2-3 %I Association pour la diffusion de la recherche francophone en intelligence artificielle %U https://roia.centre-mersenne.org/articles/10.5802/roia.74/ %R 10.5802/roia.74 %G fr %F ROIA_2024__5_2-3_95_0
Olivier Bartheye; Guy Alain Narboni. Retour sur un exemple historique en Prolog III : le découpage d’un rectangle en carrés de tailles distinctes. Revue Ouverte d'Intelligence Artificielle, Hommage à Alain Colmerauer, Volume 5 (2024) no. 2-3, pp. 95-119. doi : 10.5802/roia.74. https://roia.centre-mersenne.org/articles/10.5802/roia.74/
[1] Tiling by Squares – squared square finders, www.squaring.net
[2] Une introduction à Prolog III, Annales des Télécommunications, Volume 44 (1989) no. 5-6, p. 229–241 (alain.colmerauer.free.fr/alcol/ArchivesPublications/Prolog3/acmprolog3f.pdf) | DOI | Zbl
[3] An Introduction to Prolog III, Communications of the ACM, Volume 33 (1990) no. 7, pp. 69-90 | DOI
[4] Über Zerlegung von Rechtecken in Rechtecke., Math. Ann., Volume 57 (1903), pp. 314-332 | DOI | Zbl
[5] Simple perfect squared square of lowest order, Journal of Combinatorial Theory, Series B, Volume 25 (1978) no. 2, pp. 240-243 | DOI | Zbl
[6] Quant aux carrés carrelés, thèse de doctorat, Université de la Méditerranée, Marseille (2001) (alain.colmerauer.free.fr/alcol/ArchivesPublications/Gambini/carres.pdf)
[7] Mathematical Games, Scientific American, Volume 199 (1958) no. 5, pp. 136-144 | DOI
[8] O Rozkladach Prostokatow Na Kwadraty (On the Dissection of a Rectangle into Squares), Prezeglad Mat., Volume 3 (1925), pp. 152-153
[9] www.prolog-heritage.org (Manuels de référence des « Prolog de Marseille »)
[10] The Quest of the Perfect Square, The American Mathematical Monthly, Volume 72 (1965) no. 2, pp. 29-35 | DOI | Zbl
Cité par Sources :