Algorithmic Methods for Solving Path Puzzles: Study on Backtracking Approach and SAT-Based Technique
JOSHUA ERLANGGA SAKTI
Informasi Umum
Kode
23.04.3486
Klasifikasi
518.172 - Algorithm-Research Methods
Jenis
Karya Ilmiah - Skripsi (S1) - Reference
Subjek
Algorithm Analysis And Problem Complexity, Algorithms Programming,
Dilihat
252 kali
Informasi Lainnya
Abstraksi
<p>This paper explores algorithmic aspects of Path puzzles, a pencil-and-paper puzzle introduced in 2013 and proven NP-complete in 2020. Specifically, this paper presents two algorithmic approaches for solving Path puzzles: the imperative backtracking technique and the declarative SAT-based method. This paper shows that the asymptotic running time of the backtracking method in solving an arbitrary Path puzzle instance of size (m \times n) is (O(3^{mn})). Additionally, the paper presents a SAT encoding scheme that converts the puzzle's rules into propositional formulas, enabling the SAT solver to determine the solution. Experimental findings highlight the effectiveness of the backtracking approach for puzzles of sizes up to (7 \times 7), while the SAT-based approach shines when handling puzzles of sizes more than (7 \times 7).</p>
- CII2C2 - ANALISIS KOMPLEKSITAS ALGORITMA
- CII2K3 - STRATEGI ALGORITMA
Koleksi & Sirkulasi
Tersedia 1 dari total 1 Koleksi
Anda harus log in untuk mengakses flippingbook
Pengarang
| Nama | JOSHUA ERLANGGA SAKTI |
| Jenis | Perorangan |
| Penyunting | Muhammad Arzaki, Gia Septiana Wulandari |
| Penerjemah |
Penerbit
| Nama | Universitas Telkom, S1 Informatika |
| Kota | Bandung |
| Tahun | 2023 |
Sirkulasi
| Harga sewa | IDR 0,00 |
| Denda harian | IDR 0,00 |
| Jenis | Non-Sirkulasi |
