Elementary Search-based Algorithms for Solving Tilepaint Puzzles - Fridolin, Vincentius Arnold; Arzaki, Muhammad; Wulandari, Gia Septiana (Indonesian Journal on Computing (Indo-JC), 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.