<![CDATA[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 \times n$ Tilepaint instance containing $p$ tiles are respectively $O(2^{p} \cdot p \cdot mn)$ and $O(2^{p} \cdot 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 \times n$ Tilepaint instance containing $mn$ tiles of size $1 \times 1$ is solvable in polynomial time. In contrast, this paper shows that solving general $m \times 1$ and $1 \times n$ Tilepaint puzzles remains intractable by reducing such problems from the subset-sum problem.]]>
Copyrights © 2023
