Five Cells and Tilepaint are NP-Complete
Chuzo IWAMOTO, Tatsuya IDE
Abstract
Five Cells and Tilepaint are Nikoli's pencil puzzles. We study the computational complexity of Five Cells and Tilepaint puzzles. It is shown that deciding whether a given instance of each puzzle has a solution is NP-complete.
Topics & Concepts
Computer scienceNP-completeComputational complexity theoryPencil (optics)Theoretical computer scienceAlgorithmPhysicsQuantum mechanicsDigital Image Processing TechniquesComputational Geometry and Mesh GenerationGraph Labeling and Dimension Problems