文献

J-GLOBAL ID：201402224002889312   整理番号：13A1952402

4色を有したTantrix Matchパズルの複雑性

The Complexity of Tantrix Match Puzzles with Four Colors

著者 (3件)： UEJIMA Akihiro (Osaka Electro-Communication Univ.) ,  YANAGITANI Fuhito (Osaka Electro-Communication Univ.) ,  TSUKAMOTO Shohei (Osaka Electro-Communication Univ.)
資料名： Journal of Information Processing (Web)  (Journal of Information Processing (Web))
巻： 21  号： 3  ページ： 405-412 (J-STAGE)  発行年： 2013年 
JST資料番号： U0109A  ISSN： 1882-6652  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： Tantrix Matchとは幾つかの固定タイルが存在する六角形格子ボード内に六角形タイルが配置されているパズルである。各タイルは4つの可能な色の内の3つで直線を塗られており,隣接タイルに触れる全ての直線は色においてマッチしなければならない事が要求される。本研究の目的はこのパズルの計算複雑性を決定する事であり,筆者らは回路-充足可能性問題(Circuit-SAT)からの還元によって一般化Tantrix MatchがNP完全である事を証明した。(翻訳著者抄録)

シソーラス用語： *ゲーム ,  *NP完全問題 ,  *計算量 ,  充足可能性問題 ,  還元
準シソーラス用語： *NP完全性 ,  *パズル

分類 (1件)： 幾何学  (AB06000T)

引用文献 (4件)：

• [1] Holzer, M. and Holzer, W.: Tantrix Rotation Puzzles are Intractable, Discrete Applied Mathematics, Vol.144, No.3, pp.345-358 (2004).
• [2] Baumeister, D. and Rothe, J.: The three-color and two-color Tantrix rotation puzzle problems are NP-complete via parsimonious reductions, Information and Computation, Vol.207, No.11, pp.1119-1139 (2009).
• [3] Cook, C.S.: The complexity of theorem proving procedures, 3rd ACM Symposium on Theory of Computing, pp.151-158 (1971).
• [4] McColl, W.: Planar crossovers, IEEE Trans. Comput., Vol.30, No.2, pp.223-225 (1981).

タイトルに関連する用語 (2件)： パズル ,  複雑性