Penyelesaian Puzzle Sudoku menggunakan Algoritma Genetik
by :Afriyudi ,Anggoro Suryo Pramudyo , M.Akbar
Abstrak : Puzzle Sudoku merupakan suatu puzzle yang bertujuan menyusun angka-angka 1 sampai dengan 9 dengan aturan dalam satu baris, satu kolom, dan satu region tidak ada angka yang berulang. Telah banyak algoritma yang digunakan untuk menyelesaikan permasalahan ini, antara lain adalah Unique Missing Candidate, Naked Singles, Hidden Singles, Coloring and Multi-Coloring, Forcing Chains, Guessing, dan lain-lain. Penggunaan algoritma genetik untuk menyelesaikan permasalahan puzzle sudoku telah banyak dilakukan. Penelitian-penelitian tersebut merekomendasikan beberapa teknik crossover dan/atau mutasi serta pembentukan kromosom. Namun seluruh teknik tersebut memerlukan generasi yang sangat lama untuk sampai menemukan solusi yang tepat. Dalam menyelesaikan permasalahan ini digunakan 3 varian dari algoritma genetik. Hasil penelitian menunjukkan bahwa varian pertama dari algortima genetik tidak terlalu bagus, disebabkan oleh pembentukan kromoson yang belum memperhatikan masalah batasan. Untuk mengatasi masalah tersebut digunakan algoritma genetik kedua yaitu dengan pembentukan kromosom sudah memperhatikan masalah batasan. Namun solusi yang diharapkan hanya dapat ditemukan apabila hanya sedikit sel yang akan dicari nilainya. Kemudian untuk mengatasi masalah tersebut dibuatlah algortima genetik ketiga dengan menggunakan teknik pengkodean yang sama dengan varian kedua tetapi dengan menggunakan proses seleksi dan mutasi.
Kata kunci : Puzzle Sudoku, Algortima Genetik
