@article{Fridolin_Arzaki_Wulandari_2023, title={Elementary Search-based Algorithms for Solving Tilepaint Puzzles}, volume={8}, url={https://socj.telkomuniversity.ac.id/ojs/index.php/indojc/article/view/750}, DOI={10.34818/INDOJC.2023.8.2.750}, abstractNote={<p>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.</p>}, number={2}, journal={Indonesia Journal on Computing (Indo-JC)}, author={Fridolin, Vincentius Arnold and Arzaki, Muhammad and Wulandari, Gia Septiana}, year={2023}, month={Aug.}, pages={36-64} }