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

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

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

这项研究的两个主要目标是阐明数学难题和游戏所具有的计算原理和算法，以及找到它们共有的结构和解决方案，并在高水平上抽象并将其作为更一般的问题解决问题解决方案进行系统化。因此，更具体地说，从理论计算机科学的角度来看，对于应用程序而言似乎很重要，并将其作为基本和优先级实施，并确定计算原理并单独开发解决方案算法。在此下，2022年的第二年，重点是几个特定的​​难题问题。第一个是一个称为葫芦的滑动块拼图，申请人本身就设计了。这具有数学背景，例如其背后的高对称性，并且已经显示出困难。另一方面，可以将这个问题视为组合过渡问题，并且通过使用对称和实验考虑的最短溶液程序开发开发最短的解决方案程序，从而获得了有趣的结果。第二个问题是创作者称之为垃圾压缩的问题。这是不可逆的过渡问题的一个示例，并且具有将其与过渡中对称性问题区分开的特性。我们仍然不知道很多，我们正在采用各种方法来澄清这一点。第三个是使用常规多面体的一种未折叠图的平面填充问题。此外，我们研究并解决了许多有趣的问题，例如非交流树木和地图折叠问题的过渡问题。

项目成果

Fun with Algorithms

享受算法的乐趣

• 发表时间: 2022
• 作者: Pierre Fraigniaud;Yushi Uno
• 通讯作者: Yushi Uno

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

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

• 发表时间: 2021
• 期刊: arXiv
• 作者: Mutsunori Banbara;Kenji Hashimoto;Takashi Horiyama;Shin-ichi Minato;Kakeru Nakamura;Masaaki Nishino;Masahiko Sakai;Ryuhei Uehara;Yushi Uno;Norihito Yasuda
• 通讯作者: Norihito Yasuda

Rolling Polyhedra on Tessellations

镶嵌上的滚动多面体

• 发表时间: 2022
• 期刊: Proceedings of the 11th International Conference on Fun with Algorithms
• 作者: 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
• 期刊: Proceedings of the 33rd Canadian Conference on Computational Geometry
• 作者: Erik D. Demaine;Jayson Lynch;Mikhail Rudoy;Yushi Uno
• 通讯作者: Yushi Uno