Nothing Special   »   [go: up one dir, main page]

Journal of Information Processing
Online ISSN : 1882-6652
ISSN-L : 1882-6652
The Complexity of Generalized Pipe Link Puzzles
Akihiro UejimaHiroaki SuzukiAtsuki Okada
Author information
JOURNAL FREE ACCESS

2017 Volume 25 Pages 724-729

Details
Abstract

Pipe Link, which is a pencil-and-paper puzzle introduced by Japanese puzzle publisher Nikoli, is played on a rectangular grid of squares. We studied the computational complexity of Pipe Link, and this paper shows that the problem to decide if a given instance of Pipe Link has a solution is NP-complete by a reduction from the Hamiltonian circuit problem for a given planar graph with a degree of at most 3. Our reduction is carefully designed so that we can also prove ASP-completeness of the another-solution-problem.

Content from these authors
© 2017 by the Information Processing Society of Japan
Previous article Next article
feedback
Top