Computer-Aided Analysis and Design of Algorithms

本研究项目有以下三个主要成果。(1)我们已经设计了算法，通过反向方法枚举Tsume-Shogi。因此，我们可以证明最长的交配移动一组给定的将棋片。(2)我们已经设计了用于生成p4平铺的基本域的算法（即，通过4倍旋转的平铺）和P6平铺（即，通过6倍旋转的平铺）。(3)我们设计了计算多面体展开数的算法。通过列举所有的展开并检查它们的重叠，我们解决了一个几百年来悬而未决的问题：柏拉图立体的每一个边展开都不重叠吗？答案是肯定的！

This research project has the following three main results. (1) We have designed algorithms for enumerating Tsume-Shogi by the reverse method. As a result, we can prove the longest mating-moves for a given set of Shogi-pieces. (2) We have designed algorithms for generating fundamental domains of p4-tiling (i.e., the tiling by 4-fold rotation) and p6-tiling (i.e., the tiling by 6-fold rotation) based on the reverse search. (3) We have designed algorithms for enumerating the unfoldings of polyhedra. By enumerating all unfoldings and checking their overlapping, we have solved an open problem for hundreds of years : Is every edge-unfolding of Platonic solids nonoverlapping? The answer is yes!