IMPLEMENTASI ALGORITMA INTERATIVE-DEEPENING SEARCH (IDS)

Artikel ini dibuat berdasarkan jurnal yang disusun oleh Jackri Hendrik pada 2017 dengan judul Penerapan Algoritma Interative-Deepening Search (IDS) Dalam Penyelesaian Permainan Teka-Teki Kakuro

1. Penjelasan Singkat

Menurut John McCarthy (1956), Kecerdasan buatan/Artificial Intelligence (AI) adalah suatu sistem dalam komputer untuk mengetahui atau mengilustrasikan proses bagaimana cara berpikir seperti manusia. Dalam era teknologi informasi ini, AI berkembang sangat pesat. Salah satu peranan AI adalah mencari penyelesaian yang dapat dilakukan oleh manusia. Namun, dengan kelebihan dalam kecepatan perhitungannya, AI dapat menemukan solusi lebih cepat dibandingkan dengan manusia. Salah satu penyelesaian dari permainan yang dapat ditemukan dengan menggunakan ilmu AI adalah Kakuro.

Kakuro adalah permainan teka-teki numerik yang menyerupai logic puzzle, dan sering juga disebut dengan mathematical transliteration of the crossword dan Cross Adition.

https://en.wikipedia.org/wiki/Kakuro

Cara bermain Kakuro adalah pemain harus mengisi setiap kotak yang kosong dengan angka bulat dari 1 hingga 9, dengan syarat bahwa total dari angka per baris dan kolom harus sesuai dengan nilai input pada setiap baris dan kolom. Angka tidak boleh berulang pada angka dan baris yang sama.

Seperti yang dijelaskan dalam artikel Mas Mursit, berikut cara bermain kakuro :

 

https://www.masmursit.com/

Kita akan mengisi kolom yang biru tersebut dengan angka 1-9.

https://www.masmursit.com/

Perhatikan juga jumlah angka disamping/atasnya

7+2 = 9 (ini benar)

7+1+2 = 10 (ini salah) harusnya berjumlah sebelas

Dan diketahui salah satu teknik pencarian yang dapat digunakan untuk penyelesaian teka-teki Kakuro adalah algoritma pencarian Iterative Deepening Search (IDS). Metode Iini merupakan metode yang menggabungkan kelebihan dari pencarian Breadth First Search (BFS) yang komplit dan optimal, dengan kelebihan Depth Limited Search (DFS) yang memiliki space complexity rendah atau membutuhkan sedikit memori. IDS melakukan pencarian secara iteratif menggunakan pencarian mendalam yang dimulai dengan batasan nol. Jika belum ditemukan solusi, maka dilakukan iterasi ke-2 dengan batasan level 1. Demikian seterusnya hingga ditemukan solusi. Teknik pencarian IDS akan dilakukan sedikit modifikasi sehingga dalam pencarian solusi, tidak melanggar aturan dari Kakuro.

 

2. Pembahasan

Pencarian jawaban Kakuro dilakukan dengan menggunakan algoritma pencarian Iterative Deepening Search (IDS). Pencarian jawaban Kakuro dengan algoritma pencarian IDS adalah sebagai berikut:

a. Pencarian dimulai dari kotak pertama, yaitu kotak-0. Apabila kotak-0 adalah kotak petunjuk, maka majukan indeks kotak dan lanjutkan pemeriksaan pada kotak-1. Kotak-1 hingga kotak-8 juga merupakan kotak petunjuk, sehingga pencarian berlanjut hingga kotak-9.

b. Pencarian dilanjutkan ke kotak-9. Kotak-9 kosong atau dianggap bernilai ’0’, tambahkan angka sekarang dengan satu = ’1’ dan uji angka ’1’ pada kotak-9. Ternyata angka ’1’ tidak menyalahi aturan, karena belum terdapat angka ’1’ pada baris pertama atau kolom pertama. Tempatkan angka ’1’ pada kotak-9, seperti terlihat pada gambar berikut :

 

c. Majukan indeks dan lanjutkan pemeriksaan pada kotak-10. Kotak-10 kosong atau dianggap bernilai ’0’, tambahkan angka sekarang dengan satu = ’1’ dan uji angka ’1’ pada kotak-1. Angka ’1’ menyalahi aturan, karena telah terdapat angka ’1’ pada baris yang sama (sebelah kiri). Tambah angka dengan satu dan uji dengan angka ’2’. Ternyata angka ’2’ tidak menyalahi aturan, karena belum terdapat angka ’2’ pada baris pertama atau kolom kedua, kemudian hasil penjumlahan baris juga sama dengan 3 (sesuai dengan nilai penjumlahan baris pada kotak-8 yang menjadi kotak petunjuk). Tempatkan angka ’2’ pada kotak-10, seperti terlihat pada gambar berikut :

 

        d. Pencarian dilanjutkan ke kotak-11. Kotak-11 merupakan kotak petunjuk, majukan indeks pencarian ke kotak-12. Kotak-12 merupakan kotak petunjuk, majukan indeks pencarian ke kotak-13. Kotak-13 kosong atau dianggap bernilai ’0’, tambahkan angka sekarang dengan satu = ’1’ dan uji angka ’1’ pada kotak-13. Ternyata angka ’1’ tidak menyalahi aturan, karena belum terdapat angka ’1’ pada baris pertama atau kolom yang sama. Tempatkan angka ’1’ pada kotak-13, seperti terlihat pada gambar berikut:

      e. Bila setelah diuji hingga angka ’9’ dan suatu kotak jawaban masih tidak dapat diisi angka, maka pencarian backtrack ke kotak jawaban sebelumnya, dan melakukan pengujian kembali dengan angka yang lain.

       f. Demikian pencarian berlangsung, hingga semua kotak jawaban terisi dengan angka yang valid. Pada posisi ini, solusi soal Kakuro telah terpecahkan. 7. Apabila terjadi backtrack pada kotak-0, maka soal Kakuro tidak memiliki solusi atau penyelesaian.

 

Referensi

Hendrik, J. (2017). PENERAPAN ALGORITMA INTERATIVE-DEEPENING SEARCH (IDS) DALAM PENYELESAIAN PERMAINAN TEKA-TEKI KAKURO. INTI, Volume 5 No 1.

Mas Mursit. (2018, Mei). Cara Bermain Kakuro. Retrieved from Blog Mas Mursit: https://www.masmursit.com/2018/05/cara-bermain-kakuro.html