王将グラフ上での順次交換による色付きドロップ整列の計算量

• Item type: SIG Technical Reports(1)
• 公開日: 2021-06-12
• タイトル: 王将グラフ上での順次交換による色付きドロップ整列の計算量
• タイトル / 言語: en
• タイトル: Sequentially Swapping Colored Tokens on King's Graphs
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: ゲームの理論
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋大学情報学部
• 著者所属: 名古屋大学未来社会創造機構
• 著者所属: 名古屋大学大学院情報学研究科
• 著者所属: 名古屋大学大学院情報学研究科
• 著者名: 岡田, 優斗; 木谷, 裕紀; 大舘, 陽太; 小野, 廣隆
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 王将グラフとは王将の動きをもとに定義されたグラフであり，いわゆるグリッドに斜辺を足した形をとる．本研究では王将グラフの各頂点に置かれた色付きドロップを初期配置から最終配置に整列させる問題を考える．ただし，ドロップの移動はグラフの適当な歩（walk）上でドロップを順次交換する形をとる．2×2 以上の王将グラフ上では十分長い歩に沿って順次交換を行えば，任意の初期配置からドロップ各色の色数が等しい任意の最終配置へ整列させることができることが知られている．本研究では，そのような歩長のオーダー的にタイトな上界を与える．またドロップが 2 色の場合，入力 k に対して歩長 k 以下の順次交換で目的を達成可能かの判定が NP 完全であることなどを示す．なおこの問題は，モバイル端末ゲーム，パズル&ドラゴンズでのドロップ移動をモデル化したものである．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A king's graph is a graph that represents all legal moves of the king piece on a chessboard, and it forms a grid added with diagonal edges. In this paper, we consider to relocate colored drops on the vertices of a king's graph to a given goal configuration, where drops are moved along a walk in a sequentially swapped manner. Such relocation is always possible from an arbitrary drop configuration to another arbitrary legal drop configuration for king's graphs of size at least 2 × 2 if we use a sufficiently long walk. We give an upper bound on the length of such a walk, which is tight in terms of order. Furthermore, we show that it is NP-complete to decide for given positive integer k whether there exists a walk with length at most k so as to relocate 2-colored drops from an initial configuration to a goal configuration. In passing, sequentially swapping drops models a rule of drop moves of a mobile device game called “Puzzle & Dragons”.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11362144
• 書誌情報: 研究報告ゲーム情報学（GI）; 巻 2021-GI-46, 号 14, p. 1-8, 発行日 2021-06-12
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8736
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会