Design and Analysis of Solver Algorithms for Tilepaint Puzzles and Their Variants

VINCENTIUS ARNOLD FRIDOLIN

Informasi Umum

Kode

23.04.3517

Klasifikasi

518.172 - Algorithm-Research Methods

Jenis

Karya Ilmiah - Skripsi (S1) - Reference

Subjek

Algorithm Analysis And Problem Complexity, Algorithms,

Dilihat

400 kali

Informasi Lainnya

Abstraksi

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.