The NP-completeness of some lesser known logic puzzles

Abstract

Logic puzzles have been gaining popularity and many puzzles have been proved to be NP-complete. When a puzzle is NP-complete, it is not feasible to try to compute a solution. In this case algorithms that approximate the solution, or programs that are limited in input size can be used. In this paper we use the Hamiltonian path and cycle problems in grid graphs, and the Latin square completion problem to show that the puzzles unequal and adjacent, towers, chains and linesweeper are NP-complete.