Five Cells and Tilepaint are NP-Complete
Authors:
- 1 March 2022
- journal article
- research article
- Published by Institute of Electronics, Information and Communications Engineers (IEICE) in IEICE Transactions on Information and Systems
- Vol. E105.D (3) , 508-516
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.Keywords
This publication has 14 references indexed in Scilit:
- Dosun-Fuwari is NP-completeJournal of Information Processing, 2018
- The Complexity of Generalized Pipe Link PuzzlesJournal of Information Processing, 2017
- Satogaeri, Hebi, and Suraromu Are NP-Complete2015
- Zig-Zag Numberlink is NP-CompleteJournal of Information Processing, 2015
- Fillmat is NP-Complete and ASP-CompleteJournal of Information Processing, 2015
- Computational Complexity and an Integer Programming Model of ShakashakaIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2014
- Yosenabe is NP-completeJournal of Information Processing, 2014
- Kurodoko is NP-CompleteJournal of Information Processing, 2012
- Hashiwokakero is NP-completeInformation Processing Letters, 2009
- Partition into cliques for cubic graphs: Planar case, complexity and approximationDiscrete Applied Mathematics, 2008