Solver Algorithms and Tractable Subproblem Analysis of Suguru Puzzles
BUTRAHANDISYA
Informasi Umum
Kode
23.04.3530
Klasifikasi
518.172 - Algorithm-Research Methods
Jenis
Karya Ilmiah - Skripsi (S1) - Reference
Subjek
Algorithm Analysis And Problem Complexity, Algorithm Design-structured Programming,
Dilihat
156 kali
Informasi Lainnya
Abstraksi
<p>This paper explores algorithmic and mathematical aspects of Suguru puzzles, a single-player pencil-and-paper puzzle introduced in 2001 and proven NP-complete in 2022. Two algorithmic approaches are presented for solving Suguru puzzles: the backtracking approach and the SAT-based approach. The backtracking approach demonstrates an asymptotic running time of (O(R \cdot (mn - H + 2)!)) for solving a Suguru puzzle of size (m \times n), (R) regions, and (H) hint cells. Furthermore, a SAT encoding of the puzzle rules into propositional formulas is proposed, where the number of variables and clauses are bounded above by (O(m^3n^3)) for an (m \times n) Suguru instance. In addition, it is proven that any Suguru puzzle of size (m \times n) with either (m = 1) or (n = 1) can be solved in linear time in terms of the puzzle size. Experimental results show that the backtracking approach is faster for solving Suguru puzzles of sizes (10 \times 10) or smaller, while the SAT-based technique is superior for solving larger puzzles.</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 | BUTRAHANDISYA |
| 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 |
