Solving Tatamibari Puzzle Using Exhaustive Search and SAT Solver
ENRICO CHRISTOPHER REINHARD
Informasi Umum
Kode
23.04.808
Klasifikasi
C -
Jenis
Karya Ilmiah - Skripsi (S1) - Reference
Subjek
Algorithm Analysis And Problem Complexity
Dilihat
125 kali
Informasi Lainnya
Abstraksi
<p>In this final project, we investigate two algorithmic approaches to solve the Tatamibari puzzle and analyze it, namely, exhaustive search and SAT Solver. We also develop a polynomial time algorithm to verify whether a Tatamibari configuration is a solution. It shows that the asymptotic running time for solving the Tatamibari puzzle using exhaustive search is (O(\max{m^2n^2,h^{mn-h}\cdot hmn})) and we also derive the asymptotic running time for solving Tatamibari puzzle using SAT solver. From the experimental result, we infer that SAT solver is faster than the exhaustive search. Exhaustive search generates all possible configurations before verifying, while SAT solver generates a solution and immediately verifies it. Additionally, we also develop an algorithm to check the number of solutions for empty Tatamibari instances.</p>
<p>Keywords: Asymptotic Analysis, Exhaustive Search, SAT Solver, Tatamibari.</p>
- CII2C2 - ANALISIS KOMPLEKSITAS ALGORITMA
- CII1B3 - LOGIKA MATEMATIKA
- MSH1B3 - LOGIKA MATEMATIKA A
- CII2K3 - STRATEGI ALGORITMA
- CII4E4 - TUGAS AKHIR
Koleksi & Sirkulasi
Seluruh 1 koleksi sedang dipinjam
Anda harus log in untuk mengakses flippingbook
Pengarang
| Nama | ENRICO CHRISTOPHER REINHARD |
| Jenis | Perorangan |
| Penyunting | Muhammad Arzaki, 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 |
