Are "pipes" puzzles NP-hard?
In the Linux computer game KPlumber, the objective is to rotate tiles in a raster of squares so as to complete a system of pipes. We give a complexity classification for the original game and various special cases of it that arise from restricting the set of six possible tiles. Most of the cases are NP-complete. One polynomially solvable case is settled by formulating it as a perfect matching problem; other polynomial cases are settled by simple sweepline techniques. Moreover, we show that all the unsettled cases are polynomial time equivalent.

It is tough to be a plumber.
Král, Daniel; Majerech, Vladan; Sgall, Jirí; Tichy, Tomass; Woeginger, Gerhard.
In: Theoretical computer science, Vol. 313, No. 3, 2004, p. 474-484.
https://doi.org/10.1016/j.tcs.2002.12.002