N-QUEENS PROBLEM

N-Queens Problems

---

Definisi Masalah N-Queens

Masalah N-Queens adalah permasalahan klasik dalam ilmu komputer dan matematika kombinatorik yang melibatkan penempatan N buah ratu pada papan catur N×N tanpa saling menyerang satu sama lain.

Tujuan:

1. Menemukan semua konfigurasi penempatan ratu yang tidak saling menyerang.
2. Mengembangkan algoritma pencarian dan optimasi seperti backtracking, DFS, heuristic search, atau algoritma genetika.
3. Melatih logika pemrograman dan pemecahan masalah (CSP - Constraint Satisfaction Problem).

---

Pentingnya Masalah N-Queens

1. Studi Kasus dalam AI dan Algoritma:
   Mengajarkan teknik seperti backtracking, heuristic, dsb.

2. Model CSP (Constraint Satisfaction Problem):
   Penempatan posisi ratu tanpa melanggar aturan baris, kolom, dan diagonal.

3. Aplikasi Dunia Nyata:
   • Penjadwalan tugas
   • Penempatan sirkuit elektronik
   • Pengalokasian sumber daya
4. Kompleksitas dan Skalabilitas:
   Menggambarkan pertumbuhan kompleksitas secara eksponensial terhadap nilai N.

---

Relevansi N-Queens dalam Mata Kuliah DAA

• Backtracking sebagai teknik pencarian solusi yang sistematis dan optimal.
• Analisis Kompleksitas membandingkan brute-force dan backtracking.
• Pengenalan CSP memperkenalkan metode lanjutan seperti forward checking dan backjumping.

---

Backtracking pada N-Queens

Langkah-langkah:

1. Decision Choice: Pilih kolom untuk menempatkan ratu di baris tertentu.
2. Constraint Check: Periksa apakah aman.
3. Recursive Exploration: Lanjutkan ke langkah berikutnya jika valid.
4. Backtrack: Kembali jika tidak ada solusi.
5. Base Case: Solusi lengkap ditemukan.

---

Contoh Backtracking: Permutasi [1, 2, 3]

Solusi:
[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

---

Analogi Dunia Nyata: Penempatan Karyawan

Seperti menempatkan n karyawan dalam n ruangan dengan aturan:

• Tidak satu ruangan atau ruang yang berdekatan.
• Tidak dalam garis lurus (baris/kolom/diagonal).

Jika buntu, maka dilakukan backtracking dan coba ulang dari posisi sebelumnya.

---

Kesimpulan

• Backtracking adalah strategi pencarian sistematis dengan optimasi.
• Cocok untuk masalah dengan banyak kemungkinan dan batasan kompleks.
• N-Queens adalah studi kasus ideal untuk melatih kemampuan algoritmik dan logika.

---

Terima Kasih 🙏