Solving Yin-Yang Puzzles Using Exhaustive Search, Prune-and-Search, and SAT Solver Algorithms
MADE INDRAYANA PUTRA
Informasi Umum
Kode
23.04.144
Klasifikasi
518.1 - Algorithms
Jenis
Karya Ilmiah - Skripsi (S1) - Reference
Subjek
Algorithm Analysis And Problem Complexity, Computer Science,
Dilihat
220 kali
Informasi Lainnya
Abstraksi
<p>This final project investigates some algorithmic and mathematical aspects of Yin-Yang/Shiromaru-Kuromaru puzzles.<br /> Specifically, we discuss three algorithms for solving arbitrary Yin-Yang puzzles, namely the exhaustive search approach, the prune-and-search technique, and SAT solver.<br /> We also discuss rule translation into propositional logic formula and the number of variables and clauses needed for the SAT Solver algorithm.<br /> This final project shows that exhaustive search and prune-and-search algorithm have an identical asymptotic running time of (O(\max{mn,2^{mn-h}})) for finding all solutions of a Yin-Yang instance with (h) hints of size (m \times n). This final project also derives the asymptotic running time for solving Yin-Yang puzzle using SAT-Solver algorithm.<br /> We show that the practical running time of the prune-and-search technique outperforms the conventional exhaustive search approach. We also show that SAT solver based algorithm can be faster than the prune-and-search technique. Exhaustive search and prune-and-search method has to find all potential solution before it can verify it, while SAT solver can verify the potential solution while generating it.</p>
- CII4E4 - TUGAS AKHIR
Koleksi & Sirkulasi
Seluruh (1) koleksi tidak tersedia
Anda harus log in untuk mengakses flippingbook
Pengarang
| Nama | MADE INDRAYANA PUTRA |
| Jenis | Perorangan |
| Penyunting | Muhammad Arzaki, Gia S. 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 |
