On Computational Complexity of Pipe Puzzles

Takumu SHIRAYAMA
Takuto SHIGEMURA
Yota OTACHI
Shuichi MIYAZAKI
Ryuhei UEHARA

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A    No.9    pp.1134-1141
Publication Date: 2019/09/01
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
Keyword: 
pipe puzzle,  NP-completeness,  polynomial-time algorithm,  

Full Text: PDF(7MB)>>
Buy this Article


Summary: 
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.