« Ça a l'air facile, pourtant c'est redoutable » — FDG 2026, générer des puzzles de pliage de papier à entailles

Introduction

Le récapitulatif Tsumiki du jour. Un seul texte aujourd'hui : l'article « Difficulty-based generation of paperfolding puzzles » (« Génération de puzzles de pliage de papier fondée sur la difficulté ») de Stiliyan Nanovski, Mrinal Dhume et Rafael Bidarra (groupe de recherche Computer Graphics and Visualization de l'université technique de Delft, Pays-Bas), présenté au Procedural Content Generation (PCG) Workshop organisé en marge de la conférence académique Foundations of Digital Games 2026 (FDG '26), tenue du 10 au 13 août 2026 à Copenhague, au Danemark.

C'est une étude sur la manière dont un ordinateur peut générer, et mesurer la difficulté, d'un « puzzle de pliage de papier » — un puzzle qu'on résout en pliant une feuille de sorte que les motifs du recto et du verso s'alignent. Précisons d'emblée que le PDF complet était trop volumineux pour que je puisse le lire en entier ; ce résumé se fonde donc sur le texte intégral du résumé (abstract) publié par les auteurs eux-mêmes sur la page des résultats de recherche de l'université technique de Delft.

Ça a l'air facile, pourtant c'est redoutable — laisser un ordinateur générer des « puzzles de pliage de papier »

Un puzzle de pliage de papier (paperfolding puzzle) consiste à découper au préalable des entailles (slits) dans une feuille carrée, de sorte qu'en la pliant selon des instructions précises, des images ou des symboles distincts s'alignent au recto et au verso. L'article s'ouvre ainsi : « Les puzzles de pliage de papier sont un type de puzzle singulier : ils peuvent sembler simples et accessibles, et pourtant se révéler très difficiles. »

En s'inspirant d'un puzzle de pliage de papier existant, fondé sur une grille carrée munie d'entailles, cette étude construit un nouveau modèle plus général, capable de traiter des formes et des placements d'entailles arbitraires. Sur cette base, les auteurs ont implémenté un générateur qui assemble le puzzle par résolution de contraintes (constraint solving) et déduit son état une fois plié, pour une forme et une taille de papier données.

La mesure de la difficulté fait elle aussi l'objet d'un soin particulier : chaque disposition de puzzle générée reçoit un indice de difficulté fondé sur les types de pliages qu'elle exige. Cela permettrait, selon les auteurs, de personnaliser assez finement la génération de puzzles — pour un niveau de joueur donné, une forme de papier donnée, et jusqu'au type de motif placé dans chaque case.

Les auteurs insistent en particulier sur le fait que le générateur a fait émerger plusieurs nouveaux types de pliages, rendus possibles uniquement par la présence des entailles — ce qui, selon eux, rend les puzzles plus variés, plus intéressants et plus redoutables. L'article se conclut par une discussion des propriétés de l'espace de puzzles pouvant être généré pour quelques formats simples.

Cette question de fond — comment un ordinateur définit la difficulté d'un puzzle, et comment il l'ajuste à l'intention des concepteurs — rejoint l'article sur la génération de mots croisés lu récemment. Cette fois, je n'ai pu vérifier que le résumé, sans accéder aux chiffres précis ni aux figures de l'évaluation expérimentale. Il reste que l'idée elle-même — qu'un espace de puzzles aussi riche naisse du croisement entre une seule contrainte physique, le papier, et un petit degré de liberté supplémentaire, l'entaille — fait tout l'intérêt du jour.

La phrase du jour qui m'est restée

"Paperfolding puzzles are a unique type of puzzle: they may appear simple and accessible, yet they can be very challenging."

(traduction française : « Les puzzles de pliage de papier sont un type de puzzle singulier : ils peuvent sembler simples et accessibles, et pourtant se révéler très difficiles » — Stiliyan Nanovski, Mrinal Dhume, Rafael Bidarra, extrait de « Difficulty-based generation of paperfolding puzzles ».)

Liens de référence

Article traité aujourd'hui :

・Difficulty-based generation of paperfolding puzzles (Stiliyan Nanovski, Mrinal Dhume, Rafael Bidarra, université technique de Delft ; article présenté au Procedural Content Generation Workshop organisé en marge de Foundations of Digital Games 2026. Résumé établi à partir du texte intégral de l'abstract publié sur la page officielle des résultats de recherche de l'université technique de Delft ; le PDF complet, trop volumineux, n'a pas pu être lu en entier)

・Informations sur la conférence : Foundations of Digital Games 2026 (FDG '26), du 10 au 13 août 2026, Royal Danish Academy, Copenhague, Danemark

・Base de données des articles du PCG Workshop

Conclusion

Il suffit d'ajouter à une feuille carrée un jeu fixe de plis et d'entailles, et l'espace de puzzles qui en surgit devient d'une telle richesse — la sensation du papier qui s'aligne parfaitement me semble, d'une certaine façon, faire écho à cet instant où un puzzle sur écran finit par « s'emboîter ». Je reste toujours aussi maladroit pour résoudre des puzzles moi-même, mais ce genre d'histoire, où l'espace de conception s'élargit à partir du croisement de petites contraintes, m'attire sincèrement. À demain, pour aller chercher, quelque part dans le monde, une nouvelle discussion de conception.