The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Dans cet article, nous étudions la complexité informatique des puzzles de tuyaux. Un puzzle de tuyaux est une sorte de puzzle de carrelage ; l'entrée est un jeu de cartes, et une partie d'un tuyau est dessinée sur chaque carte. Pour un jeu de cartes donné, nous les disposons et connectons les tuyaux. Il faut raccorder toutes les canalisations sans créer de boucle locale. Alors que les puzzles de carrelage ordinaires, comme les puzzles, demandent de disposer les tuiles avec une cohérence locale, les puzzles de tuyaux demandent de joindre tous les tuyaux. Nous montrons d’abord que le puzzle de tuyaux est NP-complet en général même si la forme du but est assez restreinte. Nous étudions également des cas restreints et montrons quelques algorithmes en temps polynomial.
Takumu SHIRAYAMA
appci corporation
Takuto SHIGEMURA
The University of Tokyo
Yota OTACHI
Kumamoto University
Shuichi MIYAZAKI
Kyoto University
Ryuhei UEHARA
JAIST
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Takumu SHIRAYAMA, Takuto SHIGEMURA, Yota OTACHI, Shuichi MIYAZAKI, Ryuhei UEHARA, "On Computational Complexity of Pipe Puzzles" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 9, pp. 1134-1141, September 2019, doi: 10.1587/transfun.E102.A.1134.
Abstract: In this paper, we investigate computational complexity of pipe puzzles. A pipe puzzle is a kind of tiling puzzle; the input is a set of cards, and a part of a pipe is drawn on each card. For a given set of cards, we arrange them and connect the pipes. We have to connect all pipes without creating any local loop. While ordinary tiling puzzles, like jigsaw puzzles, ask to arrange the tiles with local consistency, pipe puzzles ask to join all pipes. We first show that the pipe puzzle is NP-complete in general even if the goal shape is quite restricted. We also investigate restricted cases and show some polynomial-time algorithms.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.1134/_p
Copier
@ARTICLE{e102-a_9_1134,
author={Takumu SHIRAYAMA, Takuto SHIGEMURA, Yota OTACHI, Shuichi MIYAZAKI, Ryuhei UEHARA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On Computational Complexity of Pipe Puzzles},
year={2019},
volume={E102-A},
number={9},
pages={1134-1141},
abstract={In this paper, we investigate computational complexity of pipe puzzles. A pipe puzzle is a kind of tiling puzzle; the input is a set of cards, and a part of a pipe is drawn on each card. For a given set of cards, we arrange them and connect the pipes. We have to connect all pipes without creating any local loop. While ordinary tiling puzzles, like jigsaw puzzles, ask to arrange the tiles with local consistency, pipe puzzles ask to join all pipes. We first show that the pipe puzzle is NP-complete in general even if the goal shape is quite restricted. We also investigate restricted cases and show some polynomial-time algorithms.},
keywords={},
doi={10.1587/transfun.E102.A.1134},
ISSN={1745-1337},
month={September},}
Copier
TY - JOUR
TI - On Computational Complexity of Pipe Puzzles
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1134
EP - 1141
AU - Takumu SHIRAYAMA
AU - Takuto SHIGEMURA
AU - Yota OTACHI
AU - Shuichi MIYAZAKI
AU - Ryuhei UEHARA
PY - 2019
DO - 10.1587/transfun.E102.A.1134
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2019
AB - In this paper, we investigate computational complexity of pipe puzzles. A pipe puzzle is a kind of tiling puzzle; the input is a set of cards, and a part of a pipe is drawn on each card. For a given set of cards, we arrange them and connect the pipes. We have to connect all pipes without creating any local loop. While ordinary tiling puzzles, like jigsaw puzzles, ask to arrange the tiles with local consistency, pipe puzzles ask to join all pipes. We first show that the pipe puzzle is NP-complete in general even if the goal shape is quite restricted. We also investigate restricted cases and show some polynomial-time algorithms.
ER -