Puzzearch-15: Penyelesaian Persoalan 15-Puzzle dengan Algoritma Branch and Bound

Implementasi algoritma branch and bound untuk melakukan penyelesaian persoalan 15-puzzle dalam bentuk CLI dan GUI sebagai Tugas Kecil 3 Mata Kuliah IF2211 Strategi Algoritma

Daftar Isi

• Deskripsi Singkat
• Requirements
• Kompilasi
• Penggunaan
• Identitas

Deskripsi Singkat

Program ini dibuat menggunakan bahasa Python untuk menyelesaikan persoalan 15-Puzzle dengan menggunakan algoritma branch and bound seperti pada materi kuliah. Nilai bound tiap simpul adalah penjumlahan cost yang diperlukan untuk sampai suatu simpul x dari akar, dengan taksiran cost simpul x untuk sampai ke goal. Taksiran cost yang digunakan adalah jumlah ubin tidak kosong yang tidak berada pada tempat sesuai susunan akhir (goal state).

Program ini dapat menentukan apakah posisi awal suatu masukan dapat diselesaikan hingga mencapai susunan akhir, dengan mengimplementasikan fungsi Kurang(i) dan posisi ubin kosong di kondisi awal (X), seperti pada materi kuliah. Jika posisi awal tidak bisa mencapai susunan akhir, program akan menampilkan pesan tidak bisa diselesaikan,. Jika dapat diselesaikan, program dapat menampilkan urutan matriks rute (path) aksi yang dilakukan dari posisi awal ke susunan akhir.

Requirements

[RECOMMENDED]

• Python 3.9.4 64-bit

Kompilasi

1. Pastikan berada di folder src (root/src/lib)
2. Untuk menjalankan CLI, lakukan kompilasi dengan command:

   python main.py

   Sementara itu, untuk menjalankan GUI, lakukan kompilasi dengan command:

   python gui.py

Penggunaan

[IMPORTANT] Karena penggunaan heuristik berbasis mismatched tiles tidak efisien, maka tidak semua persoalan dapat diselesaikan. Testcases yang diberikan di repository dapat diselesaikan dalam scope waktu di bawah 1 detik, namun dalam beberapa kasus, suatu testcase dapat diselesaikan dalam waktu di atas 30 detik.

Penggunaan CLI

1. Pengguna dapat memilih ingin memasukkan melalui text file atau input pengguna.
   • Pilih opsi [1] untuk melakukan input melalui text file. Masukkan nama file tanpa ekstensi .txt. Pastikan juga file berada pada folder test dan kompilasi dilakukan dari folder src.
   • Pilih opsi [2] untuk melakukan input pengguna. Untuk input pengguna, pengguna memasukkan 4 angka per baris, dengan bagian kosong diisikan dengan karakter -.
2. Akan muncul daftar nilai kurang[i] serta total penjumlahan kurang[i] + x. Setelah itu, program akan mencoba menelusuri puzzle states hingga ditemukan jalur yang ditemukan.
3. Program akan memberikan keluaran urutan gerakan yang harus diambil!

Penggunaan GUI

1. Pengguna dapat memilih ingin memasukkan melalui text file atau input pengguna.

   • Untuk text file, masukkan nama file tanpa ekstensi .txt pada textbox. Pengguna juga dapat memilih delay waktu animasi pada textbox bagian kanan (nilai default = 0.5s)
   • Untuk input pengguna, pengguna dapat langsung memasukkan nilai yang diinginkan ke dalam tabel.

   [IMPORTANT] Apabila waktu pencarian memakan waktu yang lama, program tidak merespon karena program mengandalkan algoritma dalam algo.py Selain itu, program akan mengutamakan input text file. Apabila pengguna memasukkan opsi via tabel dan memasukkan nama file, maka yang akan dicek adalah nama file.

2. Akan muncul daftar nilai kurang[i] serta total penjumlahan kurang[i] + x. Setelah itu, program akan mencoba menelusuri puzzle states hingga ditemukan jalur yang ditemukan.

3. Program akan menampilkan urutan gerakan yang harus diambil dan informasi pencarian!

Identitas

13520124 - Owen Christian Wijaya