Implementasi Algoritma Genetika Untuk Menyelesaikan Permainan Puzzle Kakuro

Puzzle kakuro adalah permainan penjumlahan angka dimana pemain harus mengisi setiap kotak yang tersedia dengan angka bulat dari 1 hingga 9 dan harus memenuhi beberapa syarat dalam pengisiannya. Untuk menyelesaikan puzzle kakuro berukuran 14 x 14 dengan menggunakan implementasi algoritma Backtracking diperlukan waktu 20 menit. Untuk dapat menyelesaikan puzzle kakuro 14 x 14 dengan waktu yang lebih cepat maka diperlukan suatu metode yang lain. Algoritma genetika merupakan suatu metode heuristik yang dikembangkan berdasarkan prinsip genetika dan proses seleksi alamiah teori evolusi Darwin. Proses pencarian penyelesaian atau proses terpilihnya sebuah penyelesaian dalam algoritma genetika berlangsung sama seperti terpilihnya suatu individu untuk bertahan hidup dalam proses evolusi. Keuntungan dari penggunaan algoritma genetika adalah kemampuannya untuk menemukan solusi pada ruang masalah yang cukup besar dan solusi yang diharapkan tidak harus paling optimal, tetapi cukup bisa diterima. Berdasarkan hal tersebut maka algoritma genetika dapat menjadi pilihan untuk menyelesaikan permainan puzzle kakuro dengan ukuran 14 x 14.

Kakuro puzzle is a number summary game that user have to input every available square with an integer number between 1 to 9 and must obey the rule of the kakuro puzzle game. To solve the kakuro puzzle with a size of 14 x 14, it�s take about 20 minutes to solve the puzzle using the implementation of backtracking algorithm. In order to solve the kakuro puzzle with a size of 14 x 14 faster, then its must be solved with another method. Genetic algorithm is an heuristic method that developed based on the principles of genetics and the process of natural selection from Darwin's theory of evolution. Genetic algorithm for completion of the process of search or election is similar with the election of an individual to survive in the evolutionary process. The benefit of using genetic algorithm is the ability to find a solution in a complex problem and the solution that is given by the genetic algorithm is not has to be most optimal but as long as the solution is acceptable. Because of that, the genetic algorithm can be a solution to solve the kakuro puzzle with a size of 14 x 14.