Penerapan Algoritma Backtracking Pada N-Queen Problem Permainan Catur

Abstract

Pada penulisan penelitian ini bertujuan untuk menerapkan Algoritma Backtracking dalam menyelesaikan masalah N-Queen pada permainan catur. N-Queen problem merupakan permasalahan yang mencari solusi penempatan bidak sebanyak N pada papan berukuran N x N dengan ilustrasi setiap bidak yang ditempatkan tidak boleh berada pada satu kolom, satu baris, dan satu diagonal yang sama sehingga tidak ada dua ratu yang saling menyerang dalam satu langkah Gerakan. Salah satu cara yang dapat menyelesaikan permasalahan N-Queen pada permainan catur ini yaitu dengan menggunakan Algoritma Backtracking. Dalam penerapan algoritma backtracking, solusi dicari dengan mencoba setiap kemungkinan langkah satu per satu dan kembali ke langkah sebelumnya jika langkah tersebut tidak menghasilkan solusi yang benar dan mencoba Langkah lain hingga solusi ditemukan atau semua kemungkinan telah dicoba. Penelitian ini menggunakan metode kepustakaan dimana metode ini melibatkan pencarian, peninjauan dari sumber-sumber tertulis yang berhubungan dengan topik yang sedang diteliti. Dengan membentuk pohon ruang status (State Space Tree) pada Algoritma Backtracking menghasilkan solusi pada N = 4 dengan jalur [2,4,1,3].