This paper discusses the computational aspects of Tilepaint puzzles, single-player logic puzzles introduced
in 1995 and confirmed NP-complete in 2022. Two different paradigms are discussed for solving Tilepaint
puzzles: the imperative paradigm using elementary search-based algorithms and the declarative paradigm
using a SAT-based algorithm. The search-based algorithms discussed are the complete search technique
with a bitmasking approach and the prune-and-search technique with a backtracking approach and pruning
optimization. It is shown that the asymptotic running time of the search-based algorithms for solving an
m×n Tilepaint instance containing p tiles are respectively O(2p · p · mn) and O(2p · mn), implying that the
latter method is asymptotically faster by a factor of p. This paper also analyzes the number of clauses and
variables required for solving Tilepaint puzzles using the SAT-based method. Experimental results show
that the SAT-based approach outperforms the search-based algorithm in terms of average running time.
This paper also discusses tractable and intractable variants of Tilepaint puzzles. In particular, it is shown
that an m×n Tilepaint instance containing mn tiles of size 1×1 is solvable in polynomial time. In contrast,
it is also shown that solving general m×1 and 1×n Tilepaint puzzles remains intractable by reducing such
problems from the subset-sum problem.