WEKO3
アイテム
The Complexity of Tantrix Match Puzzles with Four Colors
https://ipsj.ixsq.nii.ac.jp/records/92128
https://ipsj.ixsq.nii.ac.jp/records/921280819321e-4465-423c-bdcf-2e3e9931059e
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JNL5405007 (2.2 MB)
|
Copyright (c) 2013 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Journal(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2013-05-15 | |||||||||||
| タイトル | ||||||||||||
| タイトル | The Complexity of Tantrix Match Puzzles with Four Colors | |||||||||||
| タイトル | ||||||||||||
| 言語 | en | |||||||||||
| タイトル | The Complexity of Tantrix Match Puzzles with Four Colors | |||||||||||
| 言語 | ||||||||||||
| 言語 | eng | |||||||||||
| キーワード | ||||||||||||
| 主題Scheme | Other | |||||||||||
| 主題 | [特集：パズルの数理] 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
× Fuhito, Yanagitani
× Shohei, Tsukamoto
|
|||||||||||
| 著者名(英) |
Akihiro, Uejima
× Akihiro, Uejima
× Fuhito, Yanagitani
× Shohei, Tsukamoto
|
|||||||||||
| 論文抄録 | ||||||||||||
| 内容記述タイプ | 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). ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.21(2013) No.3 (online) DOI http://dx.doi.org/10.2197/ipsjjip.21.405 ------------------------------ |
|||||||||||
| 論文抄録(英) | ||||||||||||
| 内容記述タイプ | 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). ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.21(2013) No.3 (online) DOI http://dx.doi.org/10.2197/ipsjjip.21.405 ------------------------------ |
|||||||||||
| 書誌レコードID | ||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||
| 収録物識別子 | AN00116647 | |||||||||||
| 書誌情報 |
情報処理学会論文誌 巻 54, 号 5, 発行日 2013-05-15 |
|||||||||||
| ISSN | ||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||
| 収録物識別子 | 1882-7764 | |||||||||||
