.jpg)
Latar Belakang
Program permainan (game) merupakan salah satu implementasi dari bidang ilmu komputer. Perkembangan permainan pada masa kini sudah sangat pesat dan telah menjadi mode tersendiri di dunia karena mayoritas pengguna komputer menghabiskan sebagian besar waktu mereka di depan komputer dalam program permainan. Salah satu algoritma yang digunakan untuk mengembangkan program permainan adalah algoritma berbasis pohon ruang pencarian (searching algorithm). Salah satu game yang menggunakan algoritma berbasis pohon ruang pencarian dalam menyelesaikan permainannya yaitu N-puzzle.
N-puzzle merupakan permainan menyusun angka-angka dengan aturan sebuah potongan hanya dapat dipindahkan dengan menggesernya ke ruang kosong (blank tile). Puzzle ini merupakan jenis puzzle yang memiliki tingkat kesulitan sangat tinggi dalam menyelesaikan masalahnya dibandingkan jenis puzzle lain. Umumnya orang yang memainkan puzzle ini butuh waktu lama dalam menyelesaikan permainannya. Hal ini disebabkan karena pada N-puzzle tidak ada informasi tambahan yang dimiliki untuk membantu melakukan pencarian solusi, sehingga saat proses penyusunan potongan-potongan puzzle terjadi susunan puzzle semula. Untuk menyelesaikan persoalan pada permainan ini dibutuhkan suatu algoritma pencarian efektif yang dapat diterapkan.
Dilihat dari karakteristik persoalan N- puzzle, puzzle ini membentuk ruang solusi yang diorganisasikan ke dalam struktur pohon dinamis. Struktur pohon dinamis sendiri dibangun dengan 2 metode traversal yaitu Breadth First Search (BFS) dan Depth First Search (DFS). Untuk itu penulis menerapkan algoritma Breadth First Search dan Depth First Search dalam menyelesaikan permainan N-puzzle.
Batasan Masalah
Penulis membatasi masalah pada penulisan ini sebagai berikut :
1. N-Puzzle dibuat dengan menggunakan tampilan Graphical User Interface (GUI).
2. Bahasa Pemrograman yang dipakai dalam pembuatan puzzle ini adalah Visual Prolog 7.1
3. Puzzle berukuran 4 x 4 dengan berisi 15 papan yang terisi dengan angka 1 – 15 dan satu papan kosong (blank). Setiap memulai game, susunan puzzle akan diacak secara random oleh komputer
Tujuan
Tujuan dari penulisan ini adalah mengimplementasikan penerapan algoritma Breadth First Search (BFS) dan Depth First Search (DFS) sehingga dapat digunakan untuk mengoptimalkan waktu dalam menyelesaikan permainan N-puzzle. Permainan ini juga dapat dijadikan salah satu media alternatif untuk mengisi waktu senggang. Selain itu, permainan puzzle juga termasuk salah satu jenis permainan edukasi yang dapat digunakan untuk melatih kemampuan nalar dan logika.
Metode Penulisan
Metode yang digunakan pada penulisan ini adalah :
1. Perancangan Aplikasi
Tahap perancangan aplikasi dilakukan dengan perancangan tatap muka (interface) game, perancangan alur program, dan penyiapan software bahasa pemrograman Visual Prolog 7.1.
2. Pembuatan Aplikasi
Tahapan dalam pembuatan aplikasi meliputi desain yang telah dibuat pada tahap perancangan diterapkan ke dalam kode program dengan berpedoman pada teori-teori dan algoritma yang mendukung pembuatan game N-puzzle tersebut.
3. Pengujian Aplikasi
Tahapan pengujian aplikasi dilakukan dengan menguji (debuging) terhadap kode sumber (source code) untuk memastikan bahwa fungsi-fungsi pada kode berjalan sesuai tujuan.
Konsep AI
Puzzle Number adalah permainan tradisional yang direpresentasikan dalam papan n x n, dimana setiap blok papan di beri angka dari 1 sampai (n² - 1) dan satu buah papan kosong (blank), yang terurut dari sisi kiri atas papan sampai kanan bawah. Satu papan kosong (disisi paling kanan) digunakan untuk memindahkan papan-papan disekelilingnya. Pemindahan bisa dilakukan dengan memindahkan papan kosong tersebut ke atas, ke bawah, ke kanan, atau ke kiri. Papan yang kosong harus terus dipindah-pindahkan agar solusi akhir didapat. Solusi akhir dari permainan ini adalah papan-papan tersebut terurut dari nilai yang paling kecil hingga yang paling besar seperti pada gambar dibawah ini
| 1 | 2 | 3 | 4 |
| 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | |
Aturan-Aturan
| Aturan ke- | Kondisi | Pergerakan Papan Kosong |
| 1 | Jika Papan Kosong berada di tengah. | Atas, Bawah, Kiri,Kanan |
| 2 | Jika Papan Kosong Berada di paling kanan | Atas, Bawah, Kiri |
| 3 | Jika Papan Kosong Berada di paling kiri | Atas, Bawah, Kanan |
| 4 | Jika Papan Kosong Berada di paling atas | Kiri, Kanan, Bawah |
| 5 | Jika Papan Kosong Berada di paling bawah | Kiri, Kanan, Atas |
| 6 | Jika Papan Kosong Berada di sudut Kanan Atas | Kiri, Bawah |
| 7 | Jika Papan Kosong Berada di sudut Kiri Atas | Kanan, Bawah |
| 8 | Jika Papan Kosong Berada di sudut Kanan Bawah | Kiri, Atas |
| 9 | Jika Papan Kosong Berada di sudut Kiri Bawah | Kanan, Atas |
Alur Program :
4. Eksekusi Program.
5. Mulai dengan mengacak terlebih dahulu susunan papan-papan.
6. Mulai menyusun papan sesuai dengan urutan dari 1 – 15 dengan cara menggeser papan ke posisi yang kosong.
7. Jika puzzle sudah tersusun maka pemain dinyatakan menang.
8. Jika puzzle belum tersusun maka user dapat menyimpan permainan.
9. Tapi jika pemain tidak dapat menyusun dengan benar maka keluar dari permainan.
Tampilan Output
Berikut adalah tampilan awal permainan Puzzle Number ketika pertama kali dieksekusi :
Gambar Tampilan Awal Permainan
Berikut adalah tampilan permainan Puzzle Number setelah tombol mix ditekan yang mengakibatkan urutan angka teracak :
Gambar Tampilan Output Setelah di Acak
Berikut adalah tampilan ketika permainan berhasil diselesaikan :
Gambar Tampilan Akhir