WEKO3
アイテム
The Complexity of Tantrix Match Puzzles with Four Colors
https://ipsj.ixsq.nii.ac.jp/records/95693
https://ipsj.ixsq.nii.ac.jp/records/9569394fb8d54-052b-4005-b244-18d7bca8fb79
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JIP2103007.pdf (2.2 MB)
|
Copyright (c) 2013 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | JInfP(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2013-07-15 | |||||||
| タイトル | ||||||||
| タイトル | The Complexity of Tantrix Match Puzzles with Four Colors | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | The Complexity of Tantrix Match Puzzles with Four Colors | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | [Special Issue on Mathematics of Puzzles] puzzles, Tantrix, computational complexity, NP-completeness | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| Osaka Electro-Communication University | ||||||||
| 著者所属 | ||||||||
| Osaka Electro-Communication University | ||||||||
| 著者所属 | ||||||||
| Osaka Electro-Communication University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Osaka Electro-Communication University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Osaka Electro-Communication University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Osaka Electro-Communication University | ||||||||
| 著者名 |
Akihiro, Uejima
× Akihiro, Uejima
|
|||||||
| 著者名(英) |
Akihiro, Uejima
× Akihiro, Uejima
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Tantrix Match is a puzzle in which hexagonal tiles are arranged within a hexagonal lattice board in which there are some fixed tiles. Each tile has painted lines in three of four possible colors, and it is required that all lines that touch on adjacent tiles must match in color. The aim of this research is to determine the computational complexity of this puzzle, and we prove that the generalized Tantrix Match is NP-complete by reduction from the circuit-satisfiability problem (Circuit-SAT). | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Tantrix Match is a puzzle in which hexagonal tiles are arranged within a hexagonal lattice board in which there are some fixed tiles. Each tile has painted lines in three of four possible colors, and it is required that all lines that touch on adjacent tiles must match in color. The aim of this research is to determine the computational complexity of this puzzle, and we prove that the generalized Tantrix Match is NP-complete by reduction from the circuit-satisfiability problem (Circuit-SAT). | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA00700121 | |||||||
| 書誌情報 |
Journal of information processing 巻 21, 号 3, p. 405-412, 発行日 2013-07-15 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-6652 | |||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
