8 Puzzle problem AI

permasalahan pada 8 puzzle adalah bagaimana caranya agar dapat menyusun petak2/ubin puzzle sesuai dengan urutannya. namun seblumnya petak-petak pada puzzle akan di acak letaknya.
lihat gambar.

untuk menyelesaikan permasalahan 8 puzzle kita menggunakan metode Heuristic search yang Greddy Best

Sebelumnya sudah di jelaskan bahwa pada Greddy best nilai f(n) = h(n)
maka pada permassalahan 8 puzzle, menentukan nilai heuristic atau h(n)nya ada 2 cara
1. jumlah ubin yang salah tempat.
2. total jarak.

1. LETAK UBIN SALAH TEMPAT.
kalau kita lihat, banyak ubin yang salah tempat ada 6 buah

kita mulai menyelesaikan puzzle ini dengan patokan pada ubin kosong, jika kita lihat ada 3 pilihan yang dapat kita lakukan
1. naikkan ubin 7 (DOWN) jika kita hitung jmlah ubin yang salah tempat menjadi 7 buah.
2. turunkan ubin 1 (UP) ubin yang salah tempat = 7 buah.
3. geser ubin 4 ke kiri (RIGHT) ubin yang salah tempat = 5 buah. maka langkah ini lah yang di ambil.


selanjutnya ada 3 kemungkinan yang dapat kita lakukan
pindah kan 8 (UP) = 5 (banyak ubin yang salah tempat)
ppindahkan 6 (DOWN) = 5
pindahkan 3 (RIGHT) = 5
karena semuanya memiliki nilai f(n) yang sama, maka kita pilih ubin yang pertama kali kita pindahkan sehingga posisi ubin menjadi
[1    2]
[4 8 3]
[7 6 5]

kemudian ada 2 kemungkinan yang dapat kita lakukan
pindahkan 1 (LEFT) = f(n)=6 (ubin yang salah tempat)
pindahkan 2 (RIGHT) = f(n)=4 (kita pilih karena f(n) kecil
sehingga puzzle menjadi
[1 2   ]
[4 8 3]
[7 6 5]
pindahkan 3 (DOWN)
[1 2 3]
[4 8   ]
[7 6 5]

kembali muncul pilihan
pindahkan 8 (RIGHT) = f(n) = 3
pindahkan 5 (DOWN) = f(n) = 3
karena kedua pilihan memiliki nilai n yang sama maka kita pilih pilihan pertama (LEFT)
[1 2 3]
[4   8]
[7 6 5]

kemungkinan
pindahkan 4 (LEFT) = f(n)= 4
pindahkan 6 (DOWN) = f(n)= 3 (dipilih)
[1 2 3]
[4 6 8]
[7   5]
pindah 5 (LEFT) = f(n)=3 (dipilih)
pindah 7 (RIGHT) = f(n)=3
[1 2 3]
[4 6 8]
[7 5  ]

pindah 8 (UP)
[1 2 3]
[4 6  ]
[7 5 8]

pindah 6 (LEFT)= f(n)= 2. (dipilih)
pindah 3 (UP) = f(n) = 4
[1 2 3]
[4   6]
[7 5 8]

lakukan terus menerus langkah diatas sehingga nanti akan didapat perpindahan 5, dan terakhir perpindahan 8
[1 2 3]
[4 5 6]
[7 8  ] GOAL STATE ^^

selanjutnya
2. TOTAL JARAK.
contoh:

dengan patokan ubin yang kosong, kita dapatkan 3 kemungkinan yang dapat di lakukan. UP,RIGHT,LEFT.

maksud dari penambahan di bawah puzzle tersebut adalah total jarak yang harus di tempuh agar ubin tersusun.
misalnya pada kotak pertama. 1+2+1+1+1 karena
1 (jarak ubin 2 ke posisi aslinya) +
2 (jarak ubin 4 ke posisinya) +
1 (jarak ubin 1 ke posisinya) +
1 (jarak ubin 7 ke posisinya) +
1 (jarak ubin 6 ke posisinya) sehingga total nilai huristiknya = 6

karena UP memiliki nilai heuristik terkecil, kita pilih proses ini.
[243]
[1  5]
[678]
lanjutkan lagi dengan melihat kemungkinan yang dapat terjadi.
di dapat 3 kemungkinan
RIGHT
[243]
[15  ]
[678] 1+2+1+1= 5

LEFT
[243]
[  15]
[678] 1+1+1+2=5

UP
[2  3]
[145]
[678] 1+1+1 = 3 (dipilih)

selanjutnya akan terpilih LEFT
[  23]
[145]
[678] 1+1= 2

lalu DOWN
[123]
[  45]
[678]

dan terakhir RIGHT
[123]
[4  5]
[678] MENCAPAI GOAL STATE