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

点击翻译按钮获取中文摘要

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