Penyelesaian Cryptarithmetic dengan Algorithm Backtracking

        Pada kesempatan kali ini saya mau membahas tentang CSP.. kalian pasti sudah tau kan apa itu CSP, bagi yang belum tau, yuk kenalan dulu :D Cekidotttt…

CSP adalah singkatan dari Constraint Satisfaction Problem, untuk lebih jelasnya adalah proses menemukan solusi untuk satu set kendala yang memaksakan kondisi dimana variabel harus memuaskan. Pada saat dilakukan pencarian solusi atau pemilihan urutan aksi, teknik yang digunakan dalam constraint satisfaction tergantung pada jenis kendala yang dipertimbangkan, sedemikian rupa sehingga semua constraint akan terpenuhi.

CSP dapat dijabarkan dalam 5 bagian :
1. Kumpulan variable, X  ->  kumpulan dari n variable 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 variable didefinisikan oleh suatu domain yag finite D1,D2,………,Dn, yang berisi kumpulan nilai-nilai yang mungkin untuk variabel tertentu yang bertujuan untuk menyelesaikan persoalan.

    3. Constraint C  ->  kumpulan dari constraint-constraint 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 nilai-nilai variabel tersebut merupakan solusi untuk persoalan.

 

Deskrispsi Masalah Cryptarithmetic

Cryptarithmetic merupakan ilmu dan seni yang digunakan untuk menciptakan dan menyelesaikan mathematic puzzle, dimana digit-digit ditukar dengan huruf-huruf alfabet atau symbol lain.

Cryptarithmetic juga 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 dijelaskan dalam cryptarithmetic problem antara lain :

1.      1. Masing-masing huruf atau symbol merepresentasikan digit yang hanya satu dan unik dalam persoalannya.

2.       2. Ketika digit-digit menggantikan huruf atau symbol yang digunakan, maka hasil dari operasi aritmatika haruslah benar.

 

Dari ketentuan diatas, dapat disimpulkan bahwa batasan-batasan di atas memunculkan beberapa batasan baru dalam persoalan, yaitu apabila baris 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 variable pertama sekali seharusnya tidak boleh mengandung 0.

Untuk lebih jelasnya… silahkan simak baik-baik dibawah ini :

 

Spesifikasi dalam persoalan cryptarithmetic (couple + couple = quartet) yaitu:

1.      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.   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.      3. Variabel-variabel untuk persoalan cryptaritmetic ini ada 10 variabel, antara lain : C, O, U, P, L, E, Q, A, R, dan T.

4.      4. Persoalan cryptaritmetic ini akan menggunakan bit carry, yaitu variabel X1, X2, X3, X4, dan X5.

      Masih bingung? :D Silahkan simak contoh berikut….. cekidotttt

Dalam persoalan ini, karena jumlah variabel ada 10, maka sudah tentu kesepuluh angka harus dipakai.  

         X5  X4 X3 X2 X1
         C  O  U  P  L  E
         C  O  U  P  L  E
       ---------------------- +
    Q  U  A  R  T  E  T

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.      1. Bangkitkan angka i

2.      2. Periksa pemberian angka berdasarkan constraint yang ada

3.   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.     4. Jika tidak ada lagi angka yang dapat dibangkitkan (angka habis), maka persoalan cryptarithmetic dengan n variabel dan m warna tidak dapat diselesaikan.

    Karena penamaan simpul adalah angka, bukan variabel, sehingga untuk setiap variabel akan diberi urutan nomor dimulai dari variabel paling kanan dari cryptarithmetic yaitu E sampai ke paling kiri yaitu Q, sebab operasi yang dilakukan adalah penjumlahan sehingga harus dimulai dari sebelah kiri, yaitu:

      E = 1   R = 6
T = 2   O = 7
L = 3   A = 8
P = 4   C = 9
U = 5  Q = 10

nb# pemberian nomor untuk variabel bukanlah solusi, tetapi hanya untuk mempermudah proses iterasi.

•      Initial state
                           C  O  U  P  L  E
                           C  O  U  P  L  E
                          ---------------------- +
                      Q  U  A  R  T  E  T 

•      Operator Succesor : (0,1,2,3,4,5,6,7,8,9)

•      Path cost
                          • 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

•      Goal state 

E = 1  R = 6 T = 2  O = 7

L = 3  A = 8

P = 4  C = 9

U = 5  Q = 10

Sumber referensi :

• http://saefulnugroho.blogspot.co.id/2011/10/constraint-satisfaction.html
• http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2005-2006/Makalah2006/MakalahStmik2006-47.pdf
• Rinaldi Munir, Diktat Kuliah IF2251 Strategi Algoritmik, STEI, 2006
• Stuart J Russell & Peter Norvig, Artificial Intelligence – A Modern Approach, Prentice-Hall International, Inc, Textbook

Related Posts: