Article Per Year (5 Year)
p-Index From 2019 - 2024
0.23
P-Index
This Author published in this journals
All Journal Indonesian Journal on Computing (Indo-JC)
Vincentius Arnold Fridolin
School of Computing, Telkom University
Computer Science & IT

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
Elementary Search-based Algorithms for Solving Tilepaint Puzzles Vincentius Arnold Fridolin; Muhammad Arzaki; Gia Septiana Wulandari
Indonesia Journal on Computing (Indo-JC) Vol. 8 No. 2 (2023): August, 2023
Publisher : School of Computing, Telkom University

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.34818/INDOJC.2023.8.2.750

Abstract

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.
Co-Authors Gia Septiana Wulandari Muhammad Arzaki