数理的パズルやゲームが持つ計算原理の解明とそれらの汎用問題解決手法としての体系化

阐明数学难题和游戏的计算原理，并将其系统化为通用的问题解决方法

• 批准号: 21K11757
• 负责人: 宇野 裕之
• 金额: $ 2.66万
• 依托单位: Osaka Metropolitan University (2022)Osaka Prefecture University (2021)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2021
• 资助国家: 日本
• 起止时间: 2021-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21K11757/
• 关键词: 数理パズル; アルゴリズムの設計と解析; 離散数学; 組合せ遷移; 組合せゲーム理論

本研究は，数理的なパズルやゲームが持つ計算原理やアルゴリズムを解明すること，さらにそれらに共通する構造や解法を見出し，高いレベルで抽象化しより一般的な問題解決技法として体系化することを主要な2つの目的としている．そのためにより具体的には，とくに理論計算機科学や離散数学の見地から，普遍性を持ち応用上も重要と思われる数理的パズルやゲームを見出し，個別にその計算原理の解明や解法アルゴリズムの開発を行うことを基本的かつ優先的な事項として実施する．そのもとで２年度目にあたる令和４年度は，具体的ないくつかのパズル的な問題を対象とした．一つ目は，申請者ら自身が考案したＧｏｕｒｄｓと呼ばれるスライディングブロックパズルである．これは背後に高度な対称性など数学的な背景をもち，すでに困難性などを示している．一方でこの問題は組合せ遷移問題ととらえることができ，対称性を利用した最短手数求解手順の開発や，実験的な考察などを遂行中で興味深い結果が得られつつあるある．二つ目は，発案者らがゴミ圧縮と呼ぶ問題である．これは，不可逆な遷移問題の一つの実例であり，遷移に対称性を持つ問題とは一線を画する性質をもつ．まだわからないことが多く，解明に向けてさまざまアプローチを着手している．三つめは，正多面体の一種の展開図による平面充填問題である．このほかにも，非交差全域木の遷移問題や地図折り問題など，興味深い問題を幅広く調査し扱った．

这项研究的目的是阐明数学难题和游戏的计算原理和算法，并发现它们共有的结构和解决方案，将它们进行高层次的抽象，并将它们系统化为更通用的问题解决技术。主要目的。为此，我们需要从应用的角度，特别是从理论计算机科学和离散数学的角度找到普遍且重要的数学难题和游戏，并分别阐明其计算原理并开发解决算法。正在将其视为基本和优先事项。 2020 年，即该项目的第二年，我们重点研究了几个具体的类似谜题的问题。第一个是名为“Gourds”的滑块拼图，是申请人自己发明的。这具有高级对称性等数学背景，并且已经表现出困难。另一方面，这个问题可以被视为组合转移问题，并且通过使用对称性和实验考虑开发最短求解过程，获得了有趣的结果。第二个问题是发明者所说的垃圾压缩。这是不可逆转移问题的一个例子，它具有与转移对称问题区分开来的属性。还有很多事情我们不明白，我们正在采取各种方法去揭开它们。第三个问题是使用一种正多面体展开图的平面填充问题。此外，我们还研究并处理了一系列其他有趣的问题，例如非相交生成树转换问题和地图折叠问题。

项目成果

Solving Rep-tile by Computers: Performance of Solvers and Analyses of Solutions

用计算机求解 Rep-tile：求解器的性能和解的分析

• 发表时间: 2021
• 作者: Mutsunori Banbara; Kenji Hashimoto; Takashi Horiyama; Shin
• 通讯作者: Shin

Rolling Polyhedra on Tessellations

镶嵌上的滚动多面体

• 发表时间: 2022
• 作者: Akira Baes; Erik D. Demaine; Martin L. Demaine; Elizabeth Hartung; Stefan Langerman; Joseph O'Rourke; Ryuhei Uehara; Yushi Uno; Aaron Williams
• 通讯作者: Aaron Williams

Solving Rep-tile by Computers: Performance of Solvers and Analyses of Solutions

用计算机求解 Rep-tile：求解器的性能和解的分析

• 发表时间: 2021
• 作者: Mutsunori Banbara; Kenji Hashimoto; Takashi Horiyama; Shin
• 通讯作者: Shin

Rolling Polyhedra on Tessellations

镶嵌上的滚动多面体

• 发表时间: 2022
• 作者: Akira Baes; Erik D. Demaine; Martin L. Demaine; Elizabeth Hartung; Stefan Langerman; Joseph O'Rourke; Ryuhei Uehara; Yushi Uno; Aaron Williams
• 通讯作者: Aaron Williams

Yin-Yang Puzzles are NP-complete

阴阳谜题是 NP 完全的

• 发表时间: 2021
• 作者: Erik D. Demaine; Jayson Lynch; Mikhail Rudoy; Yushi Uno
• 通讯作者: Yushi Uno