Pemecahan Shikaku Menggunakan Pendekatan Logika Proposisi

ABDURRAHMAN SHALEH

Informasi Umum

Kode

19.04.3755

Klasifikasi

005.13 - Language Programming, Coding of Programs, Source Code

Jenis

Karya Ilmiah - Skripsi (S1) - Reference

Subjek

Formal Methods - Edp

Dilihat

306 kali

Informasi Lainnya

Abstraksi

Shikaku adalah permainan teka teki logika yang memiliki beberapa angka yang tersebar pada matriks N × N sebagai petunjuk. Pemain harus membuat partisi dengan ukuran yang sesuai dengan angka tersebut, setiap partisi tidak saling beririsan, dan bentuk partisi yang diperbolehkan adalah persegi atau persegi panjang. Permasalahan yang diberikan pada permainan Shikaku dapat dikategorikan sebagai masalah NP-complete. Pada penelitian ini penulis menggunakan pendekatan logika proposisi untuk mencari semua solusi yang ada pada Shikaku dalam bahasa Python. Python dipilih karena memiliki library Pycosat dan Satispy untuk memudahkan proses pencarian solusi dengan SAT solver. Program dapat mengeluarkan semua solusi yang mungkin ada pada Shikaku N × N. Penulis juga menemukan banyaknya klausa yang dibutukan untuk menemukan semua solusi dari sebuah Shikaku N × N pada setiap iterasinya. Analisis ini juga dilengkapi dengan kompleksitas asimtotik dari algoritma pembangunan seluruh klausa yang diperlukan. Hasil analisis ini memberikan sebuah fakta bahwa Shikaku dapat diselesaikan dalam waktu yang eksponensial terhadap banyaknya petunjuk dan ukuran Shikaku yang diberikan.