Menyelesaikan Sliding Puzzle Dengan Algoritma A*

Pada tulisan ini, saya akan menggunakan algoritma A* seperti pada tulisan sebelumnya.  Kali ini algoritma tersebut tidak dipakai untuk mencari jarak terpendek, melainkan untuk menyelesaikan sliding puzzle berukuran 3×3.  Sliding puzzle adalah sebuah permainan puzzle dimana pemain harus menggeser kotak-kotak yang ada agar memenuhi konfigurasi tertentu.  Sebagai contoh, berikut ini adalah sliding puzzle 15 yang telah berhasil diselesaikan:

15 Sliding Puzle

Tampilan awal program saya akan terlihat seperti:

Tampilan Awal Program

Program akan menggunakan sebuah file gambar yang telah tersimpan di package co.id.jocki.gambar dengan nama gambar.jpg.  Gambar ini akan dibagi ke dalam kotak-kotak sejumlah 8 kotak ditambah 1 kotak kosong.  Posisi kotak-kotak tersebut kemudian diacak.  Begitu tombol “Solve” di-klik, program Java ini akan mencari solusi dengan langkah minimum, kemudian menampilkan solusi tersebut dalam bentuk animasi hingga mencapai output seperti berikut ini:

Tampilan Akhir Program

UML Class Diagram untuk program yang saya buat adalah sebagai berikut:

UML Class Diagram

Algoritma A* yang dipakai oleh program ini terdapat dalam class Algoritma.  Seperti yang diketahui, algoritma A* membutuhkan nilai fungsi g(x) dan fungsi h(x).  Pada kode program, fungsi g(x) dihitung oleh method hitungNilaiG(PapanKotak p) dan fungsi h(x) dihitung oleh method hitungNilaiH(PapanKotak p).

Nilai fungsi g(x) adalah berapa jumlah langkah yang dibutuhkan dari awal hingga mencapai PapanKotak dengan posisi masing-masing kotak seperti saat ini.  Karena program akan mencari penyelesaian sliding puzzle dengan langkah tersingkat, maka semakin kecil nilai fungsi g(x) akan semakin baik.  Setiap PapanKotak memiliki sebuah parent yang mewakili langkah sebelumnya (sebuah PapanKotak sebelum mencapai PapanKotak ini).  Dengan demikian, program dapat menghitung nilai fungsi g(x) dengan proses rekursif.

Nilai fungsi h(x) adalah sebuah perkiraan seberapa jauh puzzle mendekati penyelesaian.   Program ini akan menghitung nilai h(x) dengan memeriksa jumlah kotak yang berada di posisi yang salah.  Semakin banyak jumlah kotak yang berada di posisi yang salah, maka mungkin saja masih banyak langkah yang harus ditempuh.  Semakin sedikit jumlah kotak yang berada di posisi yang salah, maka mungkin saja puzzle sudah hampir mendekati penyelesaian.

Setiap PapanKotak yang akan diproses disimpan di sebuah priority queue.  Java telah menyediakan class java.util.PriorityQueue<E> yang dapat langsung dipakai.  Tentu saja, program harus membuat sebuah Comparator baru untuk memberitahu Java supaya setiap elemen di queue diurutkan berdasarkan nilai fungsi g(x) + h(x).

Program akan melakukan proses berulang hingga menemukan sebuah PapanKotak di priority queue yang berisi solusi (angka 1 berurut hingga 8).  Untuk menemukan langkah-langkah yang dibutuhkan dari awal hingga mencapai PapanKotak solusi tersebut, program tinggal membaca parent (step sebelumnya yang juga diwakili sebuah PapanKotak) secara rekursif hingga kembali ke PapanKotak paling awal.

Kode program dapat di-download di link Google Docs berikut.  Pastikan untuk men-klik tombol “Download Original” di kanan atas.  File zip tersebut merupakan sebuah direktori yang berisi project NetBeans.  Untuk menjalankan program tersebut dibutuhkan minimal JDK 7.  Bila memakai JDK sebelum versi 7, ganti setiap diamond operator yang ada ke cara lama.  Misalnya:

PapanKotak lstHasil = new ArrayList<>();

menjadi

PapanKotak lstHasil = new ArrayList<PapanKotak>();

Bagi yang ingin langsung menjalankan program tanpa source-code, file JAR dapat di-download di link Google Docs ini.