Le verbe « puzzle » – perplexe ou confus, déconcertant ou déconcertant – est d’origine inconnue. « Ce genre de correspondances », a déclaré Martin Demaine, artiste en résidence au Massachusetts Institute of Technology. « C’est un puzzle d’où vient le mot ‘puzzle’. »

Son fils, Erik Demaine, un M.I.T. informaticien, d’accord. « C’est une étymologie auto-descriptive », a-t-il déclaré.

Le duo père-fils est surtout connu pour ses recherches mathématiques sur le pliage du papier, avec «sculptures à plis incurvés” — des boucles tourbillonnantes de papier plissé qui ressemblent à des échanges intergalactiques. Dates d’origami incurvées à Bauhaus de la fin des années 1920; un spécimen classique commence comme un morceau de papier circulaire qui, une fois plié le long de cercles concentriques, se tord automatiquement en une courbe en selle. Le trio de pièces de Demaines, «Origami informatique, » faisait partie de l’exposition « Design and the Elastic Mind » de 2008 au Museum of Modern Art de New York et fait maintenant partie de sa collection permanente.

De nos jours, cependant, les Demaines se concentrent davantage sur les « fontes de puzzle algorithmiques », une suite de polices de caractères d’inspiration mathématique qui sont également des puzzles. L’application principale est amusante. Une police, un hommage au mathématicien et jongleur Ron Graham, décédé en 2020, tire ses lettres des motifs de mouvement tracés par des balles lancées en l’air pendant jonglerie des trucs.

Une autre police, proposée par l’informaticien Donald Knuth (presque toutes les polices impliquent des collaborateurs), a comme caractéristique distinctive que toutes les lettres peuvent être « disséqué” – coupé en morceaux et réarrangé – en un carré de 6 par 6.

Dans un article de 2015, «Amusez-vous avec les polices : typographie algorithmique», les Demaine ont expliqué leurs motivations : « Les scientifiques utilisent chaque jour des fontes pour exprimer leur recherche par l’écrit. Mais et si la police elle-même communiquait (l’esprit de) la recherche ? Et si la façon dont le texte est écrit, et pas seulement le texte lui-même, engageait le lecteur dans la science ? »

Inspirées de théorèmes ou de problèmes ouverts, les polices – et les messages qu’elles composent – ne peuvent généralement être lues qu’après avoir résolu le puzzle ou la série de puzzles correspondants.

Prenez, par exemple, une nouvelle police dans leur collection qui fait ses débuts aujourd’hui : la Police de Sudoku. L’inspiration est venue à l’automne 2019, lorsqu’Erik Demaine a co-enseigné le cours « Fondamentaux de la programmation » (avec l’informaticienne Srini Devadas). Au cours d’un cours, le Dr Demaine et ses 400 étudiants de première année et de deuxième année ont programmé un solveur de Sudoku – ils ont écrit un code qui a résolu un puzzle de Sudoku. Le père du Dr Demaine a assisté à la conférence ce jour-là, et tout en prêtant à moitié attention, M. Demaine s’est demandé s’il serait possible de créer une police basée sur Sudoku, c’est-à-dire basée sur des énigmes dont les solutions uniques révéleraient d’une manière ou d’une autre des lettres. de l’alphabet.

Après avoir joué avec diverses possibilités, les Demaine ont conçu une police de puzzle Sudoku qui fonctionne comme suit : Tout d’abord, commencez par l’un de leurs puzzles Sudoku et résolvez-le. Ensuite, tracez une ligne reliant le plus long chemin de carrés avec des nombres consécutifs (croissants ou décroissants ; mais uniquement des carrés adjacents aux bords, pas en diagonale). Cette ligne dessine la forme d’une lettre dans la grille du puzzle. Une série de Sudokus ainsi résolus peut révéler un message, comme ceci :

La suite complète de polices de puzzle est disponible, avec différents degrés d’interactivité, sur le site du Dr Demaine Les Demaine ont conçu les formes des lettres à la main, mais ont utilisé un ordinateur pour générer les puzzles Sudoku intégrant les lettres.

« Il était difficile de concevoir des lettres qui permettaient toujours de résoudre le puzzle, et sans ajouter de connexions parasites supplémentaires au chemin le plus long », a déclaré le Dr Demaine. « C’était une police assez difficile à concevoir, à la fois pour l’humain et l’ordinateur. »

Mathématiques + art = plaisir

Les Demaine ont commencé cette expérience de police de puzzle au tournant du siècle avec un puzzle de dissection – un puzzle dans lequel une forme, ou un polygone, est découpé et réassemblé en d’autres formes géométriques. Leur motivation était un problème posé en 1964 par Harry Lindgren, un ingénieur anglo-australien et mathématicien amateur : chaque lettre de l’alphabet peut-elle être disséquée en morceaux qui se réorganisent pour former un carré ?

En 2003, s’appuyant sur précédent travail, les Demaines prouvé que, oui, en effet c’était possible, et ils ont publié le résultat. (En règle générale, une police puzzle est accompagnée d’un document de recherche correspondant.) Cette première incursion était un puzzle uniquement dans le sens où les Demaine étaient perplexes pendant un certain temps sur la façon de concevoir la police. Et ils ont rendu le défi plus déroutant en ajoutant un critère supplémentaire : ils voulaient non seulement une police de dissection, mais une « dissection articulée » – un type spécial de dissection dans lequel les pièces sont connectées (articulées) à leurs sommets, formant une chaîne fermée qui se réorganise, dans ce cas non seulement dans le carré souhaité, mais aussi dans toutes les autres lettres de l’alphabet.

Ils ont réussi leur quête en déployant les mathématiques des « polyformes », des formes constituées de multiples copies d’un polygone, comme un triangle. Plus précisément, ils ont utilisé un polyforme au nom improbable de « polyabolo » (vulgarisé par Martin Gardner, chroniqueur mathématique pour Scientific American). Un polyabolo est constitué de triangles rectangles isocèles congrus. Un carré peut être coupé en deux triangles rectangles isocèles ; et ces deux triangles peuvent à leur tour être coupés en quatre triangles rectangles isocèles, et ces quatre triangles en huit, et ces huit en 16, 16 en 32, 32 en 64, 64 en 128, et ainsi de suite.

Par cette méthode, les Demaines ont créé leur police de dissection. Chaque lettre de l’alphabet est disséquée en 32 triangles (ce qui en fait un « 32-abolo ») qui peut être réorganisé en un carré de 4 sur 4 ou en toute autre lettre. Mais atteindre le but souhaité dissection articulée — une chaîne connectée de triangles qui peuvent se transformer d’une lettre en une autre — exigeait que chaque lettre soit disséquée en 128 morceaux triangulaires (ce qui en fait un « 128-abolo »).

Réfléchissant à cet exercice dans un e-mail, les Demaines ont déclaré : « Le plaisir pour nous était de combiner l’art et les mathématiques, en visant un bon design (reconnaissable sous forme de lettres et cohérent dans l’alphabet) dans le cadre de contraintes mathématiques strictes (zone fixe et travail avec polyabolo formes). »

La philosophie du blocage

Vingt ans plus tard, ces humbles débuts se sont transformés en une fabuleuse maison de polices amusantes, avec des supports artistiques aussi variés que tiges de verre, art de la chaîne et pièces de monnaie.

Prendre en compte Police de mosaïque: Chaque lettre « carre le plan », ce qui signifie, comme l’expliquent les Demaine, « qu’une infinité de copies de cette même forme peut remplir deux dimensions sans laisser d’espace entre les carreaux ». Idéal pour une rénovation de salle de bain.

Avec le Police de bande transporteuse, chaque lettre est formée par la boucle fermée d’une bande transporteuse qui s’enroule autour de roues stratégiquement placées. (Le nom de la police est intentionnellement orthographié « convoyeur » plutôt que « convoyeur », car la police « transmet » des lettres et des mots.)

La police de bande transporteuse a été suscitée par un problème encore non résolu posé en 2001 par le mathématicien espagnol Manuel Abellanas : s’il y a plusieurs roues ou disques bidimensionnels et non chevauchants, de taille égale, peuvent-ils tous être enveloppés (connectés) avec un bande transporteuse tendue, telle que la bande touche toutes les roues mais ne se coupe pas ?

Les Demaines ont essayé de résoudre ce problème et sont restés bloqués. Ils se sont distraits en concevant la police. « Cela a toujours été une partie importante de notre philosophie », a déclaré M. Demaine. « Si nous restons bloqués sur un problème, nous aimons trouver une façon artistique de le représenter. »

Les Demaine trouvent également que les puzzles sont un bon moyen d’initier les nouveaux arrivants au plaisir des mathématiques formelles. le Police de dames (dans lequel les lettres sont formées à partir de chemins de mouvements de saut) a vu le jour lorsque Spencer Congero, un étudiant diplômé en informatique à l’Université de Californie à San Diego, a eu l’idée. le Police des galaxies spirales (basé sur le puzzle japonais crayon et papier du même nom ; des solutions uniques aux puzzles sous forme de lettres) était une collaboration avec Walker Anderson, alors étudiant à la Central Bucks West High School à Doylestown, en Pennsylvanie, et membre de la Équipe du championnat du monde de puzzle des États-Unis

La police de puzzle était la passerelle de M. Anderson vers la recherche mathématique; maintenant, il étudie les mathématiques au M.I.T. Pour les Demaine, ce genre de collaborations est un motif de célébration : une personne de plus a réussi à « corrompre » dans le monde de l’informatique théorique.

Contrainte de création

Compte tenu de leur notoriété auprès de l’origami, les Demaine ont naturellement créé quelques fontes riffant sur les nuances du pliage, dont le Police de labyrinthe en origami, les Police simple plier et couper, les Police de pliage et de perforation Et un Police de pliage impossible.

Les Demaines ont également décidé, pour changer, de créer une police minimaliste ne nécessitant qu’un seul pli.

De peur que cette simplicité ne rende la police non résolue trop simple à lire, ils ont ajouté une restriction : les lettres doivent être illisibles avant le pliage. La plupart de leurs polices, en fait, sont basées sur des contraintes similaires. Les Demaines aiment se compliquer la tâche, mais pas de façon absurde ; ils ne veulent pas trop de liberté ou de flexibilité, car l’attrait est dans le défi, mais ils veulent que la tâche soit réalisable.

Avec ces paramètres, ils ont conçu le Police de silhouette à un volet. L’élément silhouette emprunte à un « Puzzle Silhouette de lapin » datant de 1900, dans lequel cinq cartes avec des découpes de divers animaux s’empilent pour produire la silhouette d’un lapin. La police One-Fold Silhouette fonctionne de la même manière. Imaginez une feuille transparente, avec des marques noires :

Le pli vertical central vous invite à plier la feuille en deux (de droite à gauche, comme si vous tourniez la page d’un livre).

Et surprise, le texte est dévoilé !

Avec le Police de pliage en bande, une séquence de lettres est pliée à partir d’une longue bande de papier — la contrainte ici était que chaque lettre devait être pliable en utilisant uniquement des plis horizontaux, verticaux et diagonaux.

Physique des polices

L’automne dernier, les Demaine ont publié leur Police Tetris, qui s’inscrit dans la continuité de leurs études sur la complexité informatique du célèbre jeu vidéo à blocs tombants. (En 2002, Erik Demaine s’est vu conférer le titre de «Maître Tetris» par la Harvard Tetris Society, en l’honneur de sa « contribution intellectuelle à l’art de Tetris », pour un article fondateur, «Tetris est dur, même approximatif.  » )

Le résultat du nouveau résultat est le suivant : ils ont prouvé, en jouant à la version hors ligne de Tetris (dans laquelle le joueur a toutes les informations à l’avance sur l’identité et l’ordre des pièces qui vont tomber) que le jeu est « NP-complet » — ce qui signifie qu’il n’existe aucun algorithme de solution efficace, même avec aussi peu que huit colonnes ou quatre lignes. Et plus concrètement, comme le décrit le Dr Demaine sur son site Web, la complétude NP signifie « qu’il est difficile de déterminer si vous pouvez survivre ou effacer le tableau, compte tenu d’une configuration initiale et d’une séquence de m morceaux à venir.

Initialement, la contrainte créative pour cette police était que chaque lettre soit construite comme un empilement d’une copie des sept formes de Tetris. Ensuite, les Demaine ont réalisé qu’il serait judicieux d’animer la police, avec des lettres tombant en formation comme des pièces dans le jeu – de sorte que chaque pièce placée devait également être soutenue par les pièces précédentes, sans surplombs extrêmes, obéissant ainsi à la «physique de Tetris.  » Cela a nécessité un peu de refonte, parfois à l’aide d’un outil informatique (« BurrTools ») qui assemblait les formes souhaitées à partir de pièces unitaires de base.

« Lorsque nous, les humains, étions coincés à trouver une bonne solution, nous mettions certaines des formes que nous avions essayées dans BurrTools, et cela aiderait à guider notre recherche », a déclaré le Dr Demaine. « Q » et « M » ont été parmi les dernières lettres à se mettre en place.

Enfin, essayez de comprendre Police de tout, vient également de sortir aujourd’hui dans la nature. Il a été inspiré par ces graphiques oculaires avec «Es» sur chaque ligne. Dans le contexte des polices mathématiques, la lettre « E » est ce qu’on appelle une « forme canonique » – chaque lettre de l’alphabet peut être pliée en un « E » et « E » à son tour peut être plié en chaque lettre. Ce qui signifie, en fin de compte, que chaque lettre peut se replier dans n’importe quelle autre lettre. (Une forme canonique naturelle pour les chaînes protéiques, qui se replient en différentes formes, est l’hélice.)

Donc, si cet article avait été écrit dans Everything Font – avec chaque lettre portant un motif de pli (instructions de pliage) pour une autre lettre – il y aurait un autre article codé ici.