The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.9 pp.1134-1141

- Publication Date
- 2019/09/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.E102.A.1134

- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

- Category
- Puzzles

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.

Copy

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

Copy

@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},}

Copy

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 -