PENERAPAN ALGORITMA BACKTRACKING PADA PERMAINAN SUDOKU BERBASIS ANDROID

Abstract

Permainan biasanya digunakan untuk mengisi waktu dan kadang-kadang digunakan sebagai sarana pendidikan. Banyak macam permainan yang di dalamnya diimplementasikan AI, sehingga permainan menjadi lebih menarik. Sudoku merupakan permainan teka-teki logika yang tersusun atas baris dan kolom. Tujuan dari permainan ini adalah mengisi semua grid dengan angka yang tersedia, dengan ketentuan angka pada setiap baris dan kolom hanya muncul satu kali. Penelitian ini mengimplementasikan algoritma Backtracking untuk membangkitkan angka awal pada permainan Sudoku sehingga memenuhi tujuan permainan. Algoritma Backtracking dipilih karena kecepatannya dalam penentuan angka-angka yang dibangkitkan. Metodologi pada penelitian ini menggunakan model Waterfall, metode pengembangan berorientasi objek, dan UML sebagai alat bantu pengembangan sistem. Berdasarkan pengujian fungsionalitas aplikasi yang dilakukan terhadap 5 orang responden, diperoleh tingkat keberhasilan aplikasi sebesar 100%. Sedangkan, dari hasil pengujian permainan, sebanyak 5 orang responden dapat menyelesaikan permainan pada level easy dan normal, 3 orang responden dapat menyelesaikan permainan pada level hard, dan sayangnya tidak ada responden yang dapat menyelesaikan permainan pada level extreme. Hal ini menunjukkan bahwa angka yang dibangkitkan pada tiap level, membuat pemain lebih sulit menyelesaikan permainan.