Persoalan Cryptarithmetic menggunakan Algoritma Backtracking

Cryptarithmetic merupakan pengetahuan dan seni untuk menciptakan dan menyelesaikan mathematic puzzle, dimana digit-digit ditukar dengan huruf-huruf alfabet atau symbol lain. Cryptarithmetic termasuk salah satu persoalan CSP (Constraint Satisfaction Problem) yang bisa diselesaikan menggunakan algoritma backtracking.

Backtracking adalah algoritma berbasis DFS (Depth First Search) untuk mencari solusi persoalan secara lebih tepat. Pada algoritma backtracking tidak perlu memeriksa semua kemungkinan solusi yang ada, hanya pencarian yang mengarah ke solusi saja yang selalu dipertimbangkan. Dengan proses seperti ini maka perfomansi akan lebih baik karena akan menghemat waktu pencarian.

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 :

<>  Masing-masing huruf atau symbol merepresentasikan digit yang hanya satu dan unik dalam persoalan tersebut.

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

Contoh Persoalan Cryptarithmetic :

Solusi persoalan Cryptarithmetic dengan CSP dengan menggunakan algoritma Backtracking

Variabel      : {M, O, S, E, N, R, D, Y, X₁, X₂, X₃}

Domain       : D_i = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Constraint  : D + E         = Y + 10 * X₁

                         X₁ + N + R = E + 10 * X₂

                         X₂ + E + O = N + 10 * X₃

                         X₃ + S + M = O + 10 * M

Initial State, Setiap variabel masih berbentuk huruf atau symbol.

Successor, Pemberian digit atau nilai kepada setiap variabel, tetapi setiap digit atau nilai harus berbeda untuk setiap variabel.

Path Cost, Jumlah pencarian solusi permasalahan agar mencapai goal state.

Goal State,  Setiap variabel sudah memiliki nilai yang memenuhi semua constraint yang telah ditetapkan untuk persoalan.

Solusi :

=>  S + M = O nilai S dan M harus berkisar diantara [0-9], karena hanya 1 digit. Maka nilai M adalah 1 (M = 1) karena S + M + X₃ tidak bisa lebih besar dari 19.

=>  Karena M = 1, maka (S + 1 + X₃ = 1(M)O) nilai S adalah 8(+1) atau 9 agar didapat 2 digit nilai (10 atau 11). 8(+1) maksudnya 8 ditambah nilai X₃.

=>  Nilai O adalah 0 karena S + (M = 1) + X₃ harus bernilai 10 supaya didapat 2 digit. Nilai 11 bisa didpat kalau menggunakan S = 9 dan X₃ = 1, tapi nilai 1 sudah buat M, karena itu nilai O tidak boleh 1.

=>  Kemungkinan pertama : S = 8, X₃ = 1, O = 0

<> E + O = N, nilai E + O harus bernilai 10 agar bisa didapat nilai X₃ = 1

<>  X₂ + E + O = N, (1+) + (E = 9) + (O = 0) = (1)N, maka 10 = (1)N, maka    N = 0, hal ini menciptakan kesalahan karena nilai N = O, jadi kemungkinan ini salah.

=>  Kemungkinan kedua : S = 9, X₃ = 0, O = 0

<> E + O = N, X₂ + E + O = N, maka nilai X₂ harus 1 karena nilai E tidak boleh sama dengan N.

<> Didapat persamaan 1 + E + 0 = N, maka N = E + 1.

=>  Karena nilai pasti tidak dapat, maka kita menjalan kemungkinan pertama.

=>  N + R = E (hasil disini harus bernilai belasan agar X₂ = 1) D + E = Y.

=>  kemungkinan pertama sudah dijalankan, tapi tidak ketemu nilai variabel, karena itu kita jalankan kemungkinan kedua.

=>  Kita mulai dengan tebakan Kalo E = 2, maka N = 3. Pemilihan nilai E, karena  variabel E paling banyak muncul dan paling banyak berinteraksi dengan huruf lain. X₁ + N + R = (1)E, X₁ + 3 +R = (1)2, berapa nilai           X₁ + R + 3 agar di dapat nilai 12?

<> Jawabannya X₁ = 1, R = 8. Lalu kita masukan ke persamaan lanjutan, D + E = Y (hasil disini harus belasan agar di dpat X₁ = 1), D + 2 = Y, dari sini didapatkan kesimpulan bahwa kemungkinan ini tidak mungkin, karena sebesar apapun nilai D + 2 tidak akan mencapai nlai belasan.

=>  Kita lanjutkan tebakan jika E = 3, maka N = 4, (X₁ + N + R), X₁ + 4 + R = (1)3, berapa X₁ + R + 4  agar didapat 12? R = 8 dam X₁ =1.

<> Kita masukan ke D + E = (1)Y, kemungkinan ini tidak mungkin karena D + 3 hanya bernilai paling besar 10(D = 7), dan menyebabkan Y = 0 dan menjadi sama dengan nilai O.

=>  Sekarang jika E = 4, maka N = 5, (X₁ + N + R), X₁ + 5 +R = (1)4, berapa  X₁ + 5 + R agar didapat 14? R = 8 dan X₁ = 1.

<>  Kita masukan  ke D + E  = (1)Y kemungkinan ini tidak mungkin karena D(7) + 4 hanya bernilai paling besar 11, dan menyebabkan
Y = 1 dan menjadi sama dengan nilai M.

=>  Sekarang jika E = 5, maka N = 6, (X₁ + N + R), X₁ + 6 + R = (1)5, berapa X₁ + 6 + R agar didapat 15? R = 8 dan X₁ = 1.

<> Kita masukan ke D + E = (1)Y kemungkinan ini mungkin karena  D(7) + 5 bernilai paling besar 12, dan menyebabkan Y = 2. Didapatkan jawaban.

Hasil yang didapat adalah :

M = 1        N = 6       X₁ = 1

O = 0        R = 8       X₂ = 1

S = 9         D = 7      X₃ = 0

E = 5         Y = 2

   

Referensi :

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

http://slideplayer.info/slide/5075075/