Puzzle “Missionaries and Cannibals”

Kali ini saya akan menjelaskan tentang Game “Missionaries and Cannibals”. Apa itu Game “Missionaries and Cannibals” ???

Game “Missionaries and Cannibals” merupakan salah satu game bergenre puzzle yang terkenal di dunia. Game ini bercerita tentang tiga orang misionaris dan tiga kanibal yang ingin menyebarang sungai. Untuk menyebrangi sungai tersebut disediakan perahu yang dapat digunakan oleh kanibal maupun misionaris. Pemain dikatakan berhasil memainkan permainan ini jika sampai akhir permainan jumlah misionaris dan kanibal masing masing tiga. Dan aturan pokok yang menjadi cirri dari permainan ini, yaitu jumlah kanibal tidak boleh lebih dari jumlah misionari di berbagai sisi. Jika jumlah kanibal lebih banyak dari misionari, maka kanibal akan memakan misionari dan permainan berkhir.

Problem Solving dari game ini adalah :

1. Initial State : Semua Missionaries (M) dan Cannibals (K) berada diposisi kanan.
2. Successor Function : Memindahkan M dan C dalam satu langkah dengan cara memindahkan M dan C ke sebuah perahu yang maksimal 2 orang dan jumlah M tidak boleh kurang dari jumlah cannibals, apabila kurang maka missionaries akan dimakan dan game pun berakhir.
3. Path Cost : Jumlah berapa kali M dan C menyeberang.
4. Goal : Memindahkan M dan C ke seberang yang berada disebelah kiri.

Dalam permainan ini kita menggunakan metode Breadth First Search (BFS). 

Dan Apa itu BFS??

BFS atau singkatan dari Breadth First Search adalah pencarian yang dilakukan dengan mengunjungi tiap tiap node secara sistematis pada setiap level hingga keadaan tujuan ditemukan. Penelususran yang dilakukan dengan mengunjungi node node pada level yang sama hingga ditemukan tujuan (goal state) nya.

Algoritma Breadth First Search (BFS) dimulai dengan simpul akar (simpul akar terlebih dahulu dimasukkan dalam antrian, lalu di pop()), lalu mengekspansi simpul-simpul anak dari dari simpul akar, dan memasukkan simpul anak dalam sebuah antrian. Antrian tadi digunakan untuk memberikan tanda pada simpul – simpul tetangga yang nantinya akan dikunjungi berdasarkan urutan yang ada pada antrian. 

Berikut pohon state yang dibuat, dari simpul state awal hingga simpul solusi:

 

PENYELESAIAN GAME :

Gambar 1.1

Gambar 1.2

Gambar 1.3

Gambar 1.4

Gambar 1.5

Gambar 1.6

Gambar 1.7

Gambar 1.8

Gambar 1.9

Gambar 1.10

FINISH!!!!!

Referensi :

• http://infokitabersama123.blogspot.co.id/2013/11/pengertian-dan-konsep-breadth-first.html
• http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2012-2013/Makalah2012/Makalah-IF3051-2012-007.pdf
• http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2006-2007/Makalah_2007/MakalahSTMIK2007-031.pdf
• http://kronoid.blogspot.co.id/