文献

J-GLOBAL ID：202002249558529326   整理番号：20A0800323

格子上のマッチ棒(matchstick)パズル

Matchstick Puzzles on a Grid

著者 (3件)： Takenaga Yasuhiko (Department of Computer and Network Engineering, The University of Electro-Communications, Tokyo, Japan) ,  Mishiba Shohei (Department of Computer Science, The University of Electro-Communications, Tokyo, Japan) ,  Sugiyama Haruka (Department of Computer Science, The University of Electro-Communications, Tokyo, Japan)
資料名： Graphs and Combinatorics (Web)  (Graphs and Combinatorics (Web))
巻： 36  号： 2  ページ： 347-357  発行年： 2020年 
JST資料番号： U1590A  ISSN： 0911-0119  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 本論文では,2種類のマッチ棒パズルを検討した。どちらのパズルでも,マッチ棒を正方格子の端部に置くことができる。初めの問題では,マッチ棒に指定された数を動かして,マッチ棒の位置決めができた。全数探索よりも迅速にエラーを検出するストリングマッチングを使って問題を解くアルゴリズムを示した。第2の問題は,マッチ棒を指定された数を動かして,正方形の指定数を作ることであった。回路SATから縮減することによって,この問題はNP完全であることを示した。若し,格子の幅が定数で境界されていれば,この問題は多項式時間の中で解けることを示した。Copyright Springer Japan KK, part of Springer Nature 2019 Translated from English into Japanese by JST.

シソーラス用語： *格子 ,  端部 ,  *着火器 ,  情報検索 ,  マッチング ,  NP完全問題 ,  計算理論 ,  時間 ,  *娯楽
準シソーラス用語： NP完全 ,  ストリングマッチング ,  *パズル ,  *マッチ棒 ,  全数探索 ,  多項式時間

著者キーワード (4件)： パズル ,  アルゴリズム ,  NP完全性 ,  ストリングマッチング

分類 (2件)： ゲーム理論  (KA03060T) ,  集合論  (AB10000I)

タイトルに関連する用語 (3件)： 格子 ,  棒 ,  パズル