Unsolvable 8Puzzle

Yuk, bermain sejenak dengan 8Puzzle :). Permainan yang terdiri dari 9 cell berisi 8 tile bernomor (1-8) dan 1 blank. Tile bernomor bisa digeser ke arah blank (sel yang kosong). Objektifnya dengan susunan tile awal diinginkan susunan tile akhir. Berikut contoh permainannya:

Contoh permainan 8puzzle

Berapa langkah pergeseran tile yang perlu dilakukan? Sok cobain, utak-utik sambil latihan otak. Syaratnya jangan pakai program apapun. Hehehe….

Saya sendiri sudah membuat programnya (dengan algoritma heuristik best-first search A*) . Hehehe, curang yah. Salah satu langkah optimal (paling sedikit) yang bisa dilakukan adalah 24 langkah pergeseran blank, yaitu
R (ke kanan) -> D (ke bawah) -> L (ke kiri) -> U (ke atas) -> U -> R -> D -> D -> L -> U ->
U -> L -> D -> D -> R -> U -> U -> L -> D -> R ->
R -> U -> L -> D , DONE!

Dengan program dan algoritma AI, solusinya bisa diperoleh dengan cepat yah.

Tapi ada problem yang tidak bisa dipecahkan. Misalnya contoh berikut:

8Puzzle tidak terpecahkan?

8Puzzle tidak terpecahkan?

Dalam kenyataannya, kondisi di atas tidak bisa dilakukan. Init state diperoleh dengan saling menukarkan tile ‘4’ dan ‘8’ dari goal statenya dengan cara mencopot tile-tile tersebut dan memasangnya terbalik sebagai init state.

Sok, sekarang boleh pakai program. Cari solusinya… hehehe…. Kalau programnya nggak mabok kasih tahu yah… 😀

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: