Penyelesaian Masalah N-Queen Dengan Teknik Backtracking

Abstract

8-Queen merupakan suatu bentuk masalah kombinatorial klasik yang menempatkan 8 bidak pada papan catur berukuran 8x8. Permasalahan yang terjadi pada 8-Queen diilustrasikan dengan aturan sebagai berikut: setiap bidak yang ditempatkan tidak boleh berada pada satu kolom, satu baris, dan satu diagonal yang sama. Dari permasalahan 8-Queen tersebut berkembanglah suatu permasalahan baru yang disebut N-Queen dengan papan catur berukuran N×N. Ada banyak algoritma yang dapat digunakan untuk menyelesaikan permasalahan N-Queen, diantaranya adalah algoritma Brute Force dan Backtracking. Penyelesaian N-Queen dengan menggunakan algoritma Brute Force dilakukan dengan mencoba keseluruhan kemungkinan penempatan N bidak pada papan catur yang berukuran N×N pada kolom, baris, dan diagonal yang berbeda. Namun, kompleksitas waktu yang dihasilkan sangatlah besar (lebih besar dari eksponesial). Sehingga dibutuhkan algoritma lain yang mampu menyelesaikan permasalahan N-Queen dengan kompleksitas waktu yang lebih kecil dibandingkan dengan algoritma Brute Force.