Penerapan Knuth's Algorithm X Pada Proses Pemecahan Masalah Game Sudoku Berbasis Android

Abstrak

Game Sudoku merupakan permainan logika angka yang mengandalkan kemampuan berpikir sistematis untuk menyusun angka 1 hingga 9 dalam kotak berukuran 9x9 tanpa ada angka yang sama di setiap baris, kolom, dan kotak 3x3. Penyelesaian Sudoku secara manual sering kali memerlukan waktu dan ketelitian tinggi, terutama pada tingkat kesulitan yang lebih tinggi. Penelitian ini bertujuan untuk mengembangkan aplikasi berbasis Android yang mampu menyelesaikan permasalahan Sudoku secara otomatis menggunakan Knuth's Algorithm X dengan teknik Dancing Links. Knuth's Algorithm X merupakan metode pencarian eksak (exact cover) yang sangat efisien dalam menangani persoalan kombinatorial seperti Sudoku. Pendekatan ini melibatkan pemetaan puzzle Sudoku ke dalam bentuk matriks biner yang kemudian diselesaikan melalui rekursi backtracking. Dalam implementasinya, aplikasi dirancang dengan antarmuka yang interaktif, memungkinkan pengguna untuk memasukkan teka-teki Sudoku dan mendapatkan solusi secara instan. Pengujian dilakukan dengan berbagai tingkat kesulitan puzzle, dan hasilnya menunjukkan bahwa algoritma ini mampu menyelesaikan setiap kasus dengan waktu eksekusi yang relatif cepat dan akurasi yang tinggi. Selain itu, integrasi pada platform Android memungkinkan aplikasi ini diakses dengan mudah oleh pengguna melalui perangkat mobile. Dengan demikian, penelitian ini tidak hanya menunjukkan efektivitas Knuth's Algorithm X dalam menyelesaikan Sudoku, tetapi juga memberikan kontribusi dalam pengembangan aplikasi edukatif yang menggabungkan kecerdasan algoritmik dengan teknologi mobile