Cryptarithmetic dengan metode Runut Balik (BackTracking)

PENGERTIAN

 CSP merupakan teknik yang dapat digunakan untuk penyelesaian persoalan dalam dunia nyata, yang terkadang memberikan batasan tertentu yang tidak boleh dilanggar pada saat mencari solusinya. Pada saat melakukan pencarian solusi atau pemilihan urutan aksi, teknik penyelesaian ini akan selalu menyesuaikan dengan constraint-constraint yang sudah ditentukan sebelumnya, sedemikian sehingga semua constraint akan terpenuhi.
       
CSP dapat direpresentasikan  sebagai berikut :
 1. Kumpulan  variabel.
X --> kumpulan dari n variabel X1,X2,X3,…..,Xn, 
Variabel adalah elemen atau entity yang ingin dicari nilainya sehingga pemberian nilai pada  variabel dapat menjadi solusi dari CSP.
 

2. Domain D --> Masing-masing variabel didefinisikan oleh suatu domain yang finite D1,D2,………,Dn, yang berisi kumpulan nilainilai yang mungkin untuk variabel tertentu yang bertujuan untuk menyelesaikan persoalan.

3. Constraint C --> kumpulan dari constraintconstraint C1,C2,……,Cm. Ci merupakan constraint-constraint yang berisi batasan nilai untuk setiap variabel dan tidak boleh dilanggar. Constraint-constraint ini akan membatasi domain dari suatu variabel sehingga menjadi lebih sempit

4. Assignment --> pemberian nilai pada suatu variabel.

5. Solusi --> pemberian nilai-nilai pada setiap variabel yang memenuhi semua constraint yang telah ditetapkan untuk persoalan, sehingga nilainilai variabel tersebut merupakan solusi untuk persoalan.

Cryptarithmetic merupakan  pengetahuan dan seni untuk menciptakan dan menyelesaikan mathematic puzzle, dimana digit-digit ditukar dengan hurufhuruf alfabet atau symbol lain.

Cryptarithmetic merupakan salah satu contoh persoalan yang dapat diselesaikan dengan  CSP, dengan constraint yang melibatkan 3 atau lebih variabel. Cryptarithmetic merupakan contoh yang sangat cocok untuk CSP, karena selain menyediakan deskripsi, masalah cryptarithmetic dapat dijelaskan lebih baik dengan constraint-constraint.

Constraint-constraint yang mendefinisikan sebuah cryptarithmetic problem antara lain :
1. Masing-masing huruf atau symbol  merepresentasikan digit yang hanya satu dan unik dalam persoalan tersebut.
2. Ketika digit-digit menggantikan huruf atau simbol, maka hasil dari operasi aritmatika harus benar

Batasan-batasan di atas memunculkan beberapa batasan baru dalam persoalan, yaitu apabila basis dari angka adalah 10, maka pasti akan ada paling banyak 10 simbol atau huruf yang unik dalam persoalan. Jika tidak, maka tidak akan mungkin untuk memberikan digit yang unik ke setiap huruf atau simbol yang unik juga dalam persoalan. Dan supaya memiliki makna yang berarti secara semantik, angka tidak boleh dimulai dengan 0, jadi huruf-huruf yang muncul untuk setiap variabel  pertama sekali seharusnya tidak boleh mengandung  0.   

Spesifikasi persoalan cryptarithmetic (couple + couple = quartet) yaitu:
1. Pemberian digit atau nilai harus berbeda untuk setiap variabel {C, O, U, P, L, E, Q, A, R, T} yaitu digit {0,…..9} sehingga persamaan COUPLE + COUPLE = QUARTET terpenuhi.
2. Apabila masing-masing variabel sudah diberikan nilai, maka pemberian nilai harus memenuhi constraint yang ada, sehingga pada saat operasi aritmatika dilakukan untuk nilai setiap variabel, maka hasil dari operasi penjumlahan COUPLE + COUPLE = QUARTET harus sesuai.    
3. Variabel-variabel untuk persoalan cryptaritmetic ini ada 10 variabel, antara lain : C, O, U, P, L, E, Q, A, R, dan T.
4. Persoalan cryptaritmetic ini akan menggunakan bit carry, yaitu variabel X1, X2, X3, X4, dan X5.

Persoalan cryptarithmetic: Diberikan sebuah bentuk cryptarithmetic dengan n buah variabel dan disediakan m buah angka. Berikan angka yang sesuai untuk setiap variabel, dan hasil aritmatika setelah setiap variabel diberi angka, harus sama dengan bentuk awal dan tidak ada variabel yang diberi angka yang sama.

Untuk persoalan ini, karena jumlah variabel ada 10, maka pastilah kesepuluh angka harus dipakai. 

 Bit carry X1 = {0,1}, X2 = {0,1}, X3 = {0,1}, X4 = {0,1}, X5 = {0,1}.

Constraint-contraint yang ditentukan untuk persoalan cryptarithmetic yaitu:
• E + E = T + 10 * X1
• X1 + L + L = E + 10 * X2
• X2 + P + P = T + 10 * X3
• X3 + U + U = R + 10 * X4
• X4 + O + O = A + 10 * X5
• X5 + C + C = U + 10 * Q

Solusi dinyatakan sebagai vektor X dengan n-tuple:

X = (x1, x2, ……., xn), xi Є {0,1,2,…..,9}

Angka variabel ke-k, xk, ditentukan dengan algoritma berikut:
1. Bangkitkan angka i
2. Periksa pemberian angka berdasarkan constraint yang ada
3. Jika angka i yang dibangkitkan tidak melanggar constraint untuk variabel tersebut, maka variabel k diberi angka i, kalau tidak bangkitkan angka berikutnya, dan ulangi langkah 2 di atas.
4. Jika tidak ada lagi angka yang dapat dibangkitkan (angka habis), maka persoalan cryptarithmetic dengan n variabel dan m warna tidak dapat diselesaikan.

Referensi :
http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2005-2006/Makalah2006/MakalahStmik2006-47.pdf

Penyelesaian 8-Puzzle dengan Greedy

Penyelesaian 8-Puzzle dengan Greedy

 8-Puzzle adalah representasi permainan teka-teki yang dapat diselesaikan dengan mengurutkan atau menyusun komponen-komponen pembentuknya sesuai dengan kondisi yang diinginkan. Komponen pada 8-Puzzle adalah berupa kotak-kotak bernomor atau bergambar (sesuai kebutuhan) yang dapat diacak sedemikian hingga menjadi suatu pola random yang dapat dicari jalan penyelesaiannya. Sesuai namanya, 8-Puzzle terdiri atas 8 kotak dan 1 tempat kosong yang dapat digerakkan dengan aturan tertentu. Aturan pergerakannya hanya berupa empat (4) arah pergerakan, yaitu: atas, bawah, kanan, dan kiri. Serta terlimitasi oleh ukuran dimensi papan yang ditempatinya. Pada 8-Puzzle, batasannya adalah ukuran 3×3. Sehingga, 8 kotak yang dimiliki hanya dapat bergerak dalam lingkup ukuran tersebut.
 Pada pembahasan kali ini, saya ingin menyelesaikan puzzle ini dengan suatu algoritma, yaitu Algoritma Greedy, dengan menggunakan dua fungsi heuristik. Algoritma Greedy merupakan algoritma yang sederhana dan lempeng (straightforward). Secara harafiah greedy artinya rakus atau tamak.
Algoritma Greedy membentuk solusi langkah per langkah. Terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan.
Dalam bahasan ini, fungsi heuristik yang akan kita tampilkan yaitu adalah sebagai berikut.
1.    h1(n) = jumlah dari tile yang salah tempat
2.    h2(n) = total jarak Manhattan (jumlah tile dari lokasi yang seharusnya untuk setiap tile)

Solusi yang pertama saya menggunakan cara heurestik yang nomor 1 :

Priority queue :
1.    F(0)=4
2.    F(0)=4 F(1)=5 F(2)=3 F(3)=4
3.    F(2)=3 F(3)=4 F(1)=5
4.    F(2)=3 F(3)=4 F(1)=5 F(4)=4
5.    F(4)=4 F(3)=4 F(1)=5
6.    F(4)=4 F(3)=4 F(1)=5 F(5)=5 F(6)=4
7.    F(6)=4 F(3)=4 F(1)=5 F(5)=5
8.    F(6)=4 F(3)=4 F(1)=5 F(5)=5 F(7)=4 F(8)=5 F(9)=2
9.    F(9)=2 F(3)=4 F(1)=5 F(5)=5 F(7)=4 F(8)=5
10.  F(9)=2 F(3)=4 F(1)=5 F(5)=5 F(7)=4 F(8)=5 F(10)=3 F(11)=0
11.  F(11)=0 F(3)=4 F(1)=5 F(5)=5 F(7)=4 F(8)=5 F(10)=3
12.  F(11)=0 F(3)=4 F(1)=5 F(5)=5 F(7)=4 F(8)=5 F(10)=3
13.  F(0) --> F(2) --> F(4) --> F(6) --> F(11)

Solusi yang Kedua saya memakai heurestik yang nomor 2 :

  Priority queue :
1.       F(0)=5
2.       F(0)=5 F(1)=6 F(2)=6 F(3)=4
3.       F(2)=6 F(3)=4 F(1)=6
4.       F(2)=6 F(3)=4 F(1)=6 F(4)=3
5.       F(4)=3 F(3)=4 F(1)=6
6.       F(4)=3 F(3)=4 F(1)=6 F(5)=4 F(6)=2
7.       F(6)=2 F(3)=4 F(1)=6 F(5)=4
8.       F(6)=2 F(3)=4 F(1)=6 F(5)=4 F(7)=3 F(8)=3 F(9)=1
9.       F(9)=1 F(3)=4 F(1)=6 F(5)=4 F(7)=3 F(8)=3
10.   F(9)=2 F(3)=4 F(1)=6 F(5)=4 F(7)=3 F(8)=3 F(10)=2 F(11)=0
11.   F(11)=0 F(3)=4 F(1)=6 F(5)=4 F(7)=3 F(8)=3 F(10)=2
12.   F(11)=0 F(3)=4 F(1)=6 F(5)=4 F(7)=3 F(8)=3 F(10)=2
13.   F(0) --> F(2) --> F(4) --> F(6) --> F(11)

Kesimpulan :
Lebih baik menggunakan solusi yang kedua yaitu menggunakan total jarak manhattan karena lebih terlihat jalan keluar nya daripada menggunakan solusi yang pertama yang agak mudah sekali terjadi perulangan.


Referensi :
https://andiktaufiq.wordpress.com/2010/05/02/8-puzzle-problem-bagian-2/
http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2010-2011/Makalah2010/MakalahStima2010-011.pdf.
http://kuliahkusayang.blogspot.co.id/2010/04/8-puzzle-problem-ai.html

Missionaris And Cannibals Puzzle Problem Solving

Penjelasan Puzzle

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 berakhir.

Constraint Puzzle

Game “Missionaries and Cannibals” terasa lebihsulit ketika diberikan aturan – aturan yang harusdipatuhi oleh pemain. Aturan – aturan tersebut antara lain:


• Ada tiga misionaris dan tiga kanibal yang harus menyebrang sungai.

• Hanya disediakan satu perahu.

• Perahu bisa berjalan jika ada minimal satu orang atau satu kanibal (satu

penumpang).

• Perahu maksimaum berisi dua (1 kanibal/1 misionaris /2 kanibal /2

misionaris)

• Jumlah kanibal tidak boleh lebih banyak dari jumlah misionaris di salah satu sisi

daratan.

• Jika jumlah kanibal lebih banyak dari jumlah misionaris pada suatu sisi daratan

maka kanibal akan memakan misionaris.

• Pemain berhasil menyelesaikan permainan jika semua misionaris dan

semua kanibal ada di sisi seberang yang menjadi tujuan.

Algoritma Breadth-First Search

Pengertian

Breadth First Search adalah algoritma pencarian solusi yang melakukan pencarian pada graf atau pohon berakar secara melebar dengan caramengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Simpul yang belum

dikunjungi dan bertetangga dengan simpul - simpulyang tadi dikunjungi , demikian seterusnya.Jika diilustrasikan dalam pohon berakar, makasemua simpul pada x dikunjungi lebih dahulu sebelum simpul-simpul pada x + 1. Algoritma ini memerlukan sebuah antrian (queue) Q untuk dapat menyimpan simpul yang telah dikunjungi. Setiap simpul yang telah dikunjungi

Prinsip Pencarian Solusi pada BFS

Secara umum, prinsip pencarian solusi dengan 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 memberikantanda pada simpul – simpul tetangga yang nantinya akan dikunjungi berdasarkan urutan yang ada pada antrian. Penjabaran dari langkah – langkah pada prinsip pencarian solusi dengan algoritma BFS ini adalah sebagai berikut :

- Akar dimasukkan dalam antrian (Simpulpaling awal yang akan dikunjungi).

- Simpul yang ada pada awal antrian diambil dan dilakukan pengecekan untuk mengetahui status simpul tersebut sebagai solusi permasalahan atau tidak, dan mengekspansi anak-anaknya jika ada.

- Jika simpul yang sudah dicek tadi merupakan solusi permasalahan, pencarian selesai dan hasil dikembalikan.

- Jika simpul yang sudah dicek sebelumnya bukan merupakan solusi permasalahan,

semua simpul yang bertetanggan dengan simpul tadi (simpul anak) dimasukkan

kedalam antrian.

- Jika antrian ternyata telah kosong dan semua simpul sudah dicek maka status pencarian selesai dan berarti solusi tidak ditemukan.

- Hal ini dilakukan secara berulang (simpul berisi solusi ditemukan/sampai antrian

kosong)

PENERAPAN BFS PADA PUZZLE

Tiap-tiap state pada puzzle dijadikan sebuahsimpul pada pohon. Pada Missionaries and Cannibals, state awal adalah sisi daratan kiri masih kosong, dan sisi daratan kanan berisi 3 Misionaris dan 3 Kanibal. Agar mempermudah penggambaran, maka dibuat notasi untuk tiap-tiap simpul/state.Untuk state awal, notasinya adalah |`(0,0)|(3,3)K`|yang artinya, di sisi kiri ada 0 Misionaris 0 Kanibal,dan disisi kanan ada 3 Misionaris, 3 Kanibal dan perahu. State akhir notasinya adalah|`K(3,3)|(0,0)`|

. Jika perahu ada di sisi kanan, makayang dapat dipindahkan adalah Misionaris atau

Kanibal yang berada di sisi kanan, dan sebaliknya.Pada tahap pencarian, state awal dimasukkan kedalam antrian, dan dikunjungi paling awal (pertamadi-dequeue), dari state awal, diexpand anak-anak dari simpul state awal tersebut, dan masing-masing

anak dimasukkan ke dalam antrian (di-enqueue).Kunjungi simpul pada antrian paling awal(di-dequeue), dan periksa simpul tersebut. Apabila pada simpul yang dikunjungi memiliki lebih banyak kanibal daripada misionaris pada suatu sisi, maka

state pada simpul tersebut merupakan state salah,dan tidak usah di-expand. Simpul yang dikunjungi juga dimasukkan pada tabel boolean sebagai penanda bahwa simpul tersebut telah dikunjungi agar simpul tersebut tidak dikunjungi jika ditemukan kembali. Jika simpul yang dikunjungi

bukan state salah, dan bukan solusi, maka expand simpul tersebut dan masukkan anak-anak simpulter sebut dalam antrian. Lakukan kembali pengunjungan simpul dari antrian yang di-dequeue hingga ditemukan simpul solusi.Runtutan langkah-langkah dari state awal hingga solusi dapat diperolah dengan melakukan backtrack tiap parent dari simpul solusi ke simpul state awal. Berikut pohon state yang dibuat, dari simpul stateawal hingga simpul solusi:

  

Warna merah berarti state tersebut salah, merah + garis bawah berarti state tersebut telah dikunjungi.


ANALISIS

Penggunaan algoritma BFS pada pencarian solusi puzzle Missionaries and kannibals menghasilkan langkah-langkah menuju solusi yang optimal (terpendek), ini dikarenakan pencarian dilakukann secara melebar dari simpul akar hingga simpul akhir. Tidak seperti penggunaan algoritma DFS (Dept-First Search), yang lebih  mengutamakan kedalaman untuk mencapai ke simpul solusi. Kekurangan penggunaan BFS disini, langkah proses pencarian lebih banyak dibandingkan dengan DFS, penggunaan ruang (memori) juga lebih banyak,karena tiap simpul anak-anak hasil ekspansi suatu simpul dimasukkan ke dalam antrian.


KESIMPULAN

Algoritma Breadth-First Search (BFS) dapat diterapkan dalam berbagai macam masalah untuk melakukan pencarian solusi, salah satunya pada puzzle Missionaries and Cannibals. Algoritma BFS melakukan pencarian pada graf atau pohon dengan cara melebar, yang tentu memerlukan memori dan langkah pencarian yang lebih banyak dibandingkan dengan Depth-First Search.Keuntungan menggunakan BFS adalah langkah dari state awal ke state akhir optimal (terpendek).


REFERENSI

Knuth, Donald E. (1997), The Art Of Computer Programming Vol 1. 3rd ed.(http://www-cs-faculty.stanford.edu/~knuth/taocp.html)

http://games.tejasri.in/2010/08/missionaries-cannibals-problem.html

Munir, Rinaldi. 2009. Diktat Kuliah Strategi Algoritmik IF2251 Strategi Algoritmik. Departemen Teknik Informatika ITB


informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2007.../MakalahIF2251-2008-060.pdf