Contexte du puzzle
Paradigm propose un défi intitulé « Pack Semicircles » où l’on doit disposer 15 demi‑cercles identiques de façon à minimiser le rayon du cercle englobant. Le classement se base sur la taille du cercle : l’auteur indique qu’une enveloppe de rayon 3 le place dans les deux tiers supérieurs du tableau des scores.
Méthodes manuelles et outils graphiques
Le participant a d’abord utilisé Affinity Photo pour placer les formes, puis est passé à Affinity Designer afin de profiter du système de Symbols et des modes de fusion. Cette approche a permis de créer des sous‑groupes réutilisables et de mettre à jour automatiquement les configurations lors de chaque ajustement. Malgré ces aides, chaque modification nécessitait la relecture du rayon global, ce qui rend le processus très fastidieux.
Analyse géométrique et contraintes algorithmiques
Chaque demi‑cercle possède un rayon r. Leur aire totale vaut 15 × (π r² / 2) = (15π/2) r². Le cercle englobant d’aire π R² doit donc satisfaire π R² ≥ (15π/2) r², d’où une borne inférieure R ≥ r √(15/2) ≈ 2,74 r. Un rayon de 3 r représente donc une solution proche de la limite théorique, expliquant le bon classement initial.
Le problème diffère du packing de cercles complets : avec un nombre impair de demi‑cercles il est impossible de les associer systématiquement en cercles complets, ce qui empêche l’utilisation directe des algorithmes de densité maximale connus pour les cercles. La symétrie pure (par exemple un agencement radial) crée souvent des espaces vides, alors que des ajustements asymétriques permettent de combler ces lacunes mais augmentent la complexité de la recherche d’optimisation.
En l’absence de littérature spécifique, on peut envisager deux axes d’automatisation : (1) un algorithme de placement itératif basé sur la minimisation du rayon via des contraintes non linéaires (ex. optimisation par descente de gradient ou algorithme génétique) ; (2) une approche de simulation physique où chaque demi‑cercle est traité comme un corps rigide soumis à des forces de répulsion et à une contrainte de confinement circulaire. Les deux méthodes nécessitent la définition précise de la fonction objectif R(positions) et de contraintes d’intersection (aucune paire ne doit se chevaucher).
Perspectives et limites
Le principal obstacle reste la représentation exacte des contacts entre arcs : les calculs d’intersection entre deux demi‑cercles demandent la résolution d’équations trigonométriques, ce qui augmente le coût numérique. De plus, la petite taille du problème (15 objets) rend les méthodes exhaustives (enumeration de permutations) coûteuses mais potentiellement réalisables avec un moteur de recherche de voisinage limité.
En pratique, combiner un outil de visualisation interactif (comme Affinity Designer) avec un script d’optimisation (Python + SciPy ou Julia) offrirait un compromis entre intuition visuelle et rigueur mathématique, permettant d’explorer rapidement des configurations asymétriques tout en garantissant la validité géométrique.
