Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 474-484 |
Number of pages | 10 |
Journal | Theoretical computer science |
Volume | 313 |
Issue number | 3 |
DOIs | |
Publication status | Published - 2004 |
Keywords
- Combinatorial game theory
- METIS-219739
- IR-76286
- NP-completeness