Computational Complexity of NURIKABE

• Autorzy: Holzer M. , Klein A. , Kutrib M. , Ruepp O.
• Języki publikacji: EN

Abstrakty

EN

We show that the popular pencil puzzle NURIKABE is intractable from the computational complexity point of view, that is, it is NP-complete, even when the involved numbers are 1 and 2 only. To this end, we show how to simulate Boolean gates by the puzzle under consideration. Moreover, we also study some NURIKABE variants, which remain NP-complete, too.

Słowa kluczowe

EN

NURIKABE puzzle; computational complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 110, nr 1-4
• Strony: 159--174
• Opis fizyczny: Bibliogr. 12 poz., rys.

Twórcy

autor

Holzer M.

autor

Klein A.

autor

Kutrib M.

autor

Ruepp O.

• Institut f¨ur Informatik, Universit¨at Giessen, Arndtstr. 2, 35392 Giessen, Germany,

Bibliografia

• [1] Buro, M.: Simple Amazons Endgames and Their Connection to Hamilton Circuits in Cubic Subgrid Graphs, Proceedings of the 2nd International Conference Computer and Games (CG), number 2063 in LNCS, Springer, Hamamatsu, Japan, 2002, 250-261.
• [2] Datta, S., Prakriya, G.: Planarity Testing Revisited, Report TR11-009, Electronic Colloquium on Computational Complexity (ECCC), January 2011.
• [3] Friedman, E.: Corral Puzzles are NP-complete, Technical report, Stetson University, DeLand, FL 32723., 2002.
• [4] Friedman, E.: Pearl Puzzles are NP-complete, Technical report, Stetson University, DeLand, FL 32723., 2002.
• [5] Friedman, E.: Spiral Galaxies Puzzles are NP-complete, Technical report, Stetson University, DeLand, FL 32723., 2002.
• [6] Lichtenstein, D.: Planar Formulae and Their Uses, SIAM Journal on Computing, 11(2), 1982, 329-343.
• [7] Papadimitriou, C. H.: Computational Complexity, Addison-Wesley, New York, 1994, ISBN 0-201-53082-1.
• [8] Seta, T.: The Complexities of Puzzles, Cross Sum and their Another Solution Problems (ASP), Senior thesis, Department of Information Science, University of Tokyo, Faculty of Science, Hongo 7-3-1, Bunkyo-ku, Tokyo 113, Japan, February 2001.
• [9] Ueda, N., Nagao, T. T.: NP-completeness Results for Nonogram via Parsimonious Reductions, Technical Report TR96-0008, Department of Computer Science, Tokyo Institute of Technology, ˆOokayama 2-12-1, Meguro, Tokyo 152, Japan, May 1996.
• [10] Valiant, L. G.: The Complexity of Computing the Permanent, Theoretical Computer Science, 8, 1979, 189-201.
• [11] Yato, T.: On the NP-completeness of the Slither Link Puzzle, IPSJ SiG Notes, AL-74, 2000, 25-32, In Japanese.
• [12] Yato, T.: Complexity and Completeness of Finding Another Solution and its Application to Puzzles, Master Thesis, Department of Information Science, University of Tokyo, Faculty of Science, Hongo 7-3-1, Bunkyoku, Tokyo 113, Japan, January 2003.