Penyelesaian Masalah 8-Queen Dengan Depth First Search Menggunakan Algoritma Backtracking

Abstract

Artificial Intelligence (A.I.) atau kecerdasan buatan dapat membantu suatu program untuk bekerja dengan pemikiran program itu sendiri, sehingga meminimalisir campur tangan pengguna. Kecerdasan buatan saat ini umum digunakan dalam permainan-permainan komputer yang memungkinkan mode player atau versus computer, seperti permainan catur yang dapat berjalan dengan sendirinya. 8-Queen merupakan suatu bentuk masalah kombinatorial klasik yang menempatkan 8 bidak pada papan catur berukuran 8x8. Penyelesaian 8-Queen dengan menggunakan algoritma Brute Force di lakukan dengan mencoba keseluruhan kemungkinan penempatan 8 bidak pada papan catur yang berukuran 8 × 8 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 8-Queen dengan kompleksitas waktu yang lebih kecil dibandingkan dengan algoritma Brute Force.