Is This Some Kind of Code? You Can Solve the …


The verb “puzzle” — to perplex or confuse, bewilder or bemuse — is of unknown origin. “That kind of fits,” mentioned Martin Demaine, an artist in residence at the Massachusetts Institute of Technology. “It’s a puzzle where the word ‘puzzle’ comes from.”

His son, Erik Demaine, an M.I.T. pc scientist, agreed. “It’s a self-describing etymology,” he mentioned.

The father-son duo is most well-known for mathematical investigations into paper folding, with “curved-crease sculptures” — swirling loops of pleated paper that resemble intergalactic interchanges. Curved origami dates to late 1920s Bauhaus; a traditional specimen begins as a round piece of paper, which, when folded alongside concentric circles, routinely twists right into a saddle curve. The Demaines’ trio of items, “Computational Origami,” was half of the 2008 “Design and the Elastic Mind” exhibit at the Museum of Modern Art in New York and now resides in its everlasting assortment.

These days, nonetheless, the Demaines are extra targeted on “algorithmic puzzle fonts,” a collection of mathematically impressed typefaces which might be additionally puzzles. The most important utility is enjoyable. One font, a homage to the mathematician and juggler Ron Graham, who died in 2020, draws its letters from the patterns of motion traced by balls thrown into the air during juggling tricks.

The entire suite of puzzle fonts is available, with varying degrees of interactivity, on Dr. Demaine’s website. The Demaines hand-designed the letter shapes, but used a computer to generate the letter-embedding Sudoku puzzles.

“It was hard to design letters that still enabled the puzzle to be solvable, and without adding additional stray connections to the longest path,” Dr. Demaine said. “This was quite a difficult font to design, both for the human and the computer.”

The Demaines began this puzzle-font experiganza around the turn of the century with a dissection puzzle — a puzzle whereby one shape, or polygon, is sliced up and reassembled into other geometric shapes. Their motivation was a problem posed in 1964 by Harry Lindgren, a British-Australian engineer and amateur mathematician: Can every letter of the alphabet be dissected into pieces that rearrange to form a square?

In 2003, building on previous work, the Demaines proved that, yes, indeed it was possible, and they published the result. (Typically, a puzzle font comes with a corresponding research paper.) This first foray was a puzzle only in the sense that the Demaines were perplexed for a while about how to design the font. And they made the challenge more puzzling by adding an extra criterion: They wanted not merely a dissection font, but a “hinged dissection” — a special kind of dissection whereby the pieces are connected (hinged) at their vertexes, forming a closed chain that rearranges, in this case not only into the desired square but also into every other letter of the alphabet.

They succeeded in their quest by deploying the mathematics of “polyforms,” shapes made from multiple copies of a polygon, such as a triangle. More precisely, they used a polyform with the improbable name “polyabolo” (popularized by Martin Gardner, who was a mathematics columnist for Scientific American). A polyabolo is made from congruent right isosceles triangles. A square can be cut into two right isosceles triangles; and those two triangles can in turn be cut into four right isosceles triangles, and those four triangles into eight, and those eight into 16, 16 into 32, 32 into 64, 64 into 128, and so forth.

Reflecting on this exercise in an email, the Demaines said: “The fun for us was combining art and math together, aiming for good design (recognizable as letters and looking consistent across the alphabet) within hard mathematical constraints (fixed area and working with polyabolo shapes).”

The Conveyer Belt Font was prompted by a still-unsolved problem posed in 2001 by the Spanish mathematician Manuel Abellanas: If there are several two-dimensional and nonoverlapping wheels, or disks, of equal size, can they all be wrapped (connected) with a taut conveyor belt, such that the belt touches all the wheels but doesn’t intersect itself?

The Demaines tried to solve this problem and got stuck. They distracted themselves by designing the font. “That’s always been an important part of our philosophy,” Mr. Demaine said. “If we get stuck on a problem, we like to find an artistic way to represent it.”

The Demaines also find that puzzles are a nice way to initiate newcomers into the fun of formal mathematics. The Checkers Font (in which the letters are formed from paths of jumping moves) came into being when Spencer Congero, a computer science graduate student at the University of California, San Diego, got in touch with the idea. The Spiral Galaxies Font (based on the Japanese pencil-and-paper puzzle of the same name; unique solutions to puzzles form letters) was a collaboration with Walker Anderson, then a student at Central Bucks West High School in Doylestown, Pa., and a member of the USA World Puzzle Championship team.

The puzzle font was Mr. Anderson’s gateway to mathematical research; now he’s an undergrad studying math at M.I.T. For the Demaines, these sorts of collaborations are cause for celebration: One more person successfully “corrupted” into the world of theoretical computer science.

Given their reputation with origami, the Demaines have naturally created a few fonts riffing on the nuances of folding, including the Origami Maze Font, the Simple Fold & Cut Font, the Fold & Punch Font and an Impossible Folding Font.

The central vertical crease invites you to fold the sheet in half (from right to left, as if you were turning the page of a book).

And surprise, the text is revealed!

Last fall, the Demaines published their Tetris Font, which is a continuation of their studies into the computational complexity of the iconic falling-block video game. (In 2002 Erik Demaine was conferred the title of “Tetris Master” by the Harvard Tetris Society, in honor of his “intellectual contribution to the art of Tetris,” for a foundational paper, “Tetris Is Hard, Even to Approximate.” )

The upshot of the new result is this: They have proved, in playing the offline version of Tetris (wherein the player has full information in advance about the identity and order of pieces that will drop) that the game is “NP-complete” — meaning that no efficient solution algorithm exists, even with as few as eight columns or four rows. And more practically, as Dr. Demaine described on his website, NP-completeness means “it’s computationally intractable to figure out whether you can survive, or clear the board, given an initial board configuration and a sequence of n pieces to come.”

Initially, the creative constraint for this font was that each letter be constructed as a stacking of one copy of all seven Tetris shapes. Then the Demaines realized it would be neat to animate the font, with letters dropping into formation like pieces in the game — so that each piece placed also had to be supported by the previous pieces, with no extreme overhangs, thus obeying “Tetris physics.” This necessitated a bit of redesign, sometimes with the help of a computer tool (“BurrTools”) that assembled desired shapes from basic unit pieces.

“When us humans got stuck finding a good solution, we’d put some of the shapes we’d been trying into BurrTools, and it would help guide our search,” Dr. Demaine said. “Q” and “M” were among the last letters to fall into place.

So, had this article been written in Everything Font — with each letter bearing a crease pattern (folding instructions) for another letter — there would be another article encoded herein.



Source link Nytimes.com

Leave a Reply

Your email address will not be published. Required fields are marked *