TY - JOUR
AU - Fridolin, Vincentius Arnold
AU - Arzaki, Muhammad
AU - Wulandari, Gia Septiana
PY - 2023/08/30
Y2 - 2024/08/13
TI - Elementary Search-based Algorithms for Solving Tilepaint Puzzles
JF - Indonesia Journal on Computing (Indo-JC)
JA - IndoJC
VL - 8
IS - 2
SE - Computer Science
DO - 10.34818/INDOJC.2023.8.2.750
UR - https://socj.telkomuniversity.ac.id/ojs/index.php/indojc/article/view/750
SP - 36-64
AB - 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.
ER -