On Computational Complexity of Pipe Puzzles

• SHIRAYAMA Takumu

  appci corporation

• SHIGEMURA Takuto

  Graduate School of Information Science and Technology, The University of Tokyo

• OTACHI Yota

  Faculty of Advanced Science and Technology, Kumamoto University

• MIYAZAKI Shuichi

  Academic Center for Computing and Media Studies, Kyoto University

• UEHARA Ryuhei

  School of Information Science, JAIST

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.

Journal

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E102.A (9), 1134-1141, 2019-09-01

  The Institute of Electronics, Information and Communication Engineers

Keywords

• pipe puzzle
• NP-completeness
• polynomial-time algorithm

Details

• CRID: 1390845702274796800
• NII Article ID: 130007699569
• DOI: 10.1587/transfun.e102.a.1134
• ISSN: 17451337
• ISSN: 09168508
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E102.A/9/E102.A_1134/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed