Elementary Search-based Algorithms for Solving Tilepaint Puzzles - Vincentius Arnold Fridolin; Muhammad Arzaki; Gia Septiana Wulandari (School of Computing, Telkom University, 2023)
This paper discusses the elementary computational aspects of Tilepaint puzzles, single-player logic puzzles introduced in 1995 and confirmed NP-complete in 2022. Two elementary search-based algorithms are proposed: the complete search technique with a bitmasking approach and the prune-and-search technique with a backtracking approach and pruning optimization. This paper shows that the asymptotic running time of these algorithms for solving an m × n Tilepaint instance containing p tiles are respectively O(2^p · p · mn) and O(2^p · mn), implying that the latter method is asymptotically faster by a factor of p. This paper also discusses tractable and intractable variants of Tilepaint puzzles. This paper shows that an m × n Tilepaint instance containing mn tiles of size 1 × 1 is solvable in polynomial time. In contrast, this paper shows that solving general m × 1 and 1 × n Tilepaint puzzles remains intractable by reducing such problems from the subset-sum problem.