Unfolding patterns: The computer science behind origami, puzzles, and games

A thin sheet of paper can be transformed into a crane, a boat, or a dragon by simply folding and sculpting its edges in a certain pattern. This ancient Japanese art of paper folding, or “origami,” has gained worldwide popularity today. What is less widely known, however, is that underneath the folds of origami patterns hides a world of logic, computation, and problem-solving, converging head-on at the intersection of computer science and mathematics!

The sequence of folding a sheet of paper, or in fact solving any puzzle using a series of steps, corresponds to a set of operations that defines an “algorithm” for writing a computer program. This, in essence, is the foundation of an emerging field in theoretical computer science called Computational Origami. The process has the potential to not only find efficient procedures to design origami and solve complex puzzles and games but also in real-world applications, e.g., figuring out how compact solar panels or drug vectors of specific shapes can be designed to ensure optimal and effective functioning. Moreover, it can also help us solve problems in computational geometry, such as the problem of efficiently packing n objects of a certain shape into a fixed space, which have applications in optimization problems.

Professor Ryuhei Uehara from Japan Advanced Institute of Science and Technology (JAIST) has built his career at the intersection of these ideas – blending discrete mathematics and computer science with his deep interest in puzzles, games, and origami.

Finding the hidden computer science in puzzles: the “Sen Tan” edge of research

Prof. Uehara, who is formally trained in Computer Science and Information Mathematics, formerly visited the University of Waterloo, Canada, during working at Komazawa University in Japan as an Associate Professor. Currently a Professor of Information Science, he leads the Laboratory of Discrete Algorithms at JAIST.

An ardent puzzle collector, Prof. Uehara describes himself as a mathematician whose interest lies in studying the computational complexities of algorithms for solving puzzles. He explains, “If you are given a long paper strip and you fold it in half over and over, you will see a pattern or shape when you unfold it. This is due to the creases that form during folding the paper in half repeatedly. This is the optimal or simplest way to get to that shape, but for a different shape you will need to change the folding patterns. You can build an algorithm to compute this pattern in the most optimal way. This way, we can actually device a theoretical solution to an abstract problem. That is how theoretical computer science is hidden in things that do not seem related to computer science like origami and puzzle.”

At Prof. Uehara’s laboratory at JAIST, his team works on building algorithms for finding effective solutions to complex puzzles and patterns by framing them as computation problems.

Under the leadership of Prof. Uehara, the field of computational origami and computational complexity theory has garnered worldwide attention, with his research as one of the highlights in the academic landscape of JAIST. The dynamic and collaborative environment at JAIST aids Prof. Uehara’s research with the facilities that enable him to lead the field of computational origami in Japan, making Asia one of the three main strongholds in computational origami, alongside North America and Europe.

Notably, his collaboration with Professor Erik D. Demaine from the Massachusetts Institute of Technology, USA, resulted in several interesting publications, including a solution to the problem of how to minimize the cut length to develop a polyhedron from a large sheet of material. The only known research on this topic, which remains surprisingly underexplored, had been from Professor Jin Akiyama, a Japanese mathematician. In their study, Prof. Uehara used rules of computational geometry to demonstrate how a given tetrahedron with four congruent triangles (triangles that can be superimposed on one another perfectly) can be unfolded with minimum cut length.

In another landmark discovery, the duo went on to prove that Dudeney’s Dissection is Optimal. What does this mean? Prof. Uehara elaborates, “The English puzzle designer Dudeney had posed the following puzzle 120 years ago: can we cut an equilateral triangle into as few pieces as possible to fit it together to form a perfect square? While Dudeney proved that only four pieces were sufficient, mathematicians were still intrigued about whether it could be done with fewer pieces.”

When Prof. Uehara first encountered the dissection puzzle several years ago, it struck him as a difficult problem that alluded to an easy solution. After joining forces with Assistant Professor Tonan Kamata from JAIST and Prof. Demaine from MIT, he went on to prove that the equilateral triangle and square had no common dissection with three or fewer polygonal pieces, which made Dudeney’s solution the most optimal. This discovery, while intellectually rewarding in itself, has important applications in textile design, engineering, and manufacturing industries.

Additionally, Prof. Uehara’s team has also investigated the computational complexities of sorting puzzles, a popular video game where the goal is to sort colored units (balls or water) into empty bins. Prof. Uehara and his team showed that such puzzles are computationally solvable with a solution of polynomial length.

Facilitating cutting-edge research: How JAIST supports researchers

From understanding the complexity of common shape puzzles to tackling the computational difficulty of jumping block puzzles, Prof. Uehara’s team works at the cutting-edge of theoretical computer science. Prof. Uehara points out that Japan has many puzzle and origami societies that are involved in theoretical computer science research. However, there are not many researchers working at the intersection of these ideas in the country. JAIST provides advanced infrastructure and facilities, notably supercomputers, which have enabled him to clearly understand the boundaries between solvability and insolvability of puzzle as well as solve computationally complex problems in realistic timescales.

Prof. Uehara adds that JAIST is one of the few universities in Japan that only supports Master’s and PhD programs (there are no undergraduate programs). This offers the advantage of allowing the facilities to be used more equitably. Moreover, this enables researchers at JAIST to dedicate more time to their research. This, along with an emphasis on publishing cutting-edge research, makes JAIST an ideal ecosystem for young researchers.

JAIST provides young researchers the liberty, infrastructure, and mentorship to explore their interests freely. Innovative research topics, such as computational origami or computational geometry, can provide a robust mathematical foundation for developing cutting-edge technologies in the fields of robotics, cryptography, and optimization.

Additionally, JAIST provides support for students who wish to attend and present their work at international conferences. Interacting with international researchers working on similar thematic research areas is crucial for professors and young researchers alike and is much encouraged by JAIST. For instance, an international conference in computational geometry will be held this year in Kanazawa, Japan, which will be accessible to the students and faculties at JAIST.

Finally, JAIST holds one of the three most famous puzzle collections in the world—Prof. Uehara is the director of this puzzle gallery, which has nearly 300 puzzles on display among around 10,000 puzzles in the collection!

Finding your Sen Tan: Advice to aspiring researchers

Speaking of young researchers and their journey, Prof. Uehara encourages them to pursue research in the area they find most enjoyable as this is often the key to discovering one’s true calling. He says, “My professors have supported my early years of research in theoretical computer science, but I did not particularly follow their research path. Instead, I pursued my love for puzzles and incorporated that into my training as a computer scientist to carve out my own niche research area.”

***

About Japan Advanced Institute of Science and Technology, Japan

Founded in 1990 in Ishikawa prefecture, the Japan Advanced Institute of Science and Technology (JAIST) was the first independent national graduate university that has its own campus in Japan to carry out research-based graduate education in advanced science and technology. The term “Advanced” in JAIST’s name reflects the Japanese term “Sen Tan,” meaning “cutting-edge,” representing the university’s focus on being at the forefront of innovative research and education. Now, after 30 years of steady progress, JAIST has become one of Japan’s top-ranking universities. JAIST aims to foster capable leaders through its advanced education and research curricula. About 40% of JAIST’s alumni are international students. The university has a unique style of graduate education to ensure that students have a thorough foundation to build cutting-edge research and technology in the future. JAIST also works closely with both local and overseas academic and industrial communities, promoting industry–academia collaborative research.

Website: https://www.jaist.ac.jp/english/