# Result of the optimal solution search for Checkerboard Origami Triangle

## Kazuki Ohshima^{†}, Ryuhei Uehara^{‡} and Jun Mitani^{†}

^{†}University of Tsukuba^{‡}Japan Advanced Institute of Science and Technology

Last updated on January 04 2020

日本語The Origami Checkerboard Triangle Puzzle is a puzzle with the goal of folding a single one-sided colored equilateral triangle sheet of paper into a pattern in which nine equilateral triangles (we call these triangles "cells") are stacked in 3 with as few steps as possible, which was proposed by Serhiy Grabarchuk. We show an example of solution of this puzzle in Figure 1.

In this puzzle, only simple folds can be applied. A single simple fold in a procedure is counted as one step.
A simple fold is a folding that transforms a flat state of a paper to another flat state with respect to a single crease.
There is no restriction on the number of layers at the folding (it is *called some-layers simple fold*).

Details about the folding operation

As the goals of this puzzle, there are 59 patterns duplication by flip, rotate, and mirror. Solutions have been found for all of them (we call a procedure which reach a certain pattern "solution"). When multiple solutions exist for one pattern, we consider the solutions with shorter steps are better. Further, when there are multiple solutions with the same number of steps, we consider the solutions with smaller initial size of triangle are better. The known best solutions have been published on the webpage by Ishino.

We enumerated solutions of this puzzle using super computer situated at the Japan Advanced Institute of Science and Technology (JAIST). The range of the search is up to six steps for initial triangle sizes 4 to 7, and up to five steps for initial triangle sizes 8 and 9. "Size n" indicates that stacked equilateral triangles are in n rows. As the result we obtained better solutions for several patterns than the known solutions.

Click a pattern in the following table to display the procedures of the selected pattern.

### Other Links

- The optimal solution search for Origami Checkerboard Puzzles with the goal of folding a square sheet of paper into 3×3 checkerboard
- The project page of this research
- The top page of this lab

selected pattern) | |

number of steps of procedures) | |

initial triangle size) | |

number of solutions) |

### Details about the folding operation

The known best solutions of pattern #02 and #06 (shown in Figure 2) published on the webpage of this puzzle by Ishino start from a size 4 equilateral triangle sheet of paper and reach the patterns in 3 steps. On the other hand, among the results of this search, the best solutions of these patterns start from a size 4 equilateral triangle but take 4 steps. This difference is due to different interpretations of the folding operation of this puzzle. One of the rules of the folding operation written on the webpage of the Origami Checkerboard puzzle is "The foling line made by one folding is one line segment per operation". For example, when the paper is in the state as shown in Figure 3, folding both white flaps (A and B) to touch flap D takes two steps (white flaps are folded separately) and folding a black flap and two white flaps (A, B and C) to the same position takes one step (when a black flap is folded, two white flaps are also folded at the same time). In this research, we define that the "line segment" exists between the chosen moved flap and the chosen non-moved flap on the sides of the folding line respectively. Other unchosen flaps move in accordance with the positional relationship and the movement of the chosen flaps. According to this interpretation, as shown in Figure 4, the third step of the known solution of #02 and #06 which reaches state (d) is not possible to be done within one step and reaches state (a), (b) or (c). This is the reason that the our result is different from the known solution.