BacktrackingLanjutFase E–FE1E5

N-Queens dengan Backtracking (Heatmap)

Masalah N-Queens diselesaikan dengan backtracking: pada setiap baris, algoritma mencoba menempatkan ratu di kolom yang aman (tidak diserang ratu lain), lalu melangkah rekursif ke baris berikutnya. Jika tidak ada posisi aman, penempatan terakhir dibatalkan dan kolom lain dicoba, hingga semua ratu terpasang tanpa saling menyerang. Visualisasi heatmap menampilkan papan dengan sel-sel yang terancam serangan dan konflik yang terdeteksi.

Contoh kasus

Penyelesai masalah penempatan dengan batasan, seperti alokasi sumber daya yang tidak boleh saling bertabrakan.

Silabus

N-Queens menempatkan N ratu di papan catur agar tak ada yang saling menyerang, memakai backtracking baris demi baris.

Tujuan Belajar

·Memahami arah serangan ratu: baris, kolom, dan diagonal
·Menjelaskan cara backtracking mencoba dan membatalkan penempatan
·Menerapkan N-Queens untuk masalah penempatan tanpa bentrok

Cara Kerja

·Tempatkan satu ratu per baris, mulai dari baris pertama
·Untuk tiap kolom, cek apakah posisi aman dari ratu lain
·Bila aman, pasang ratu lalu lanjut ke baris berikutnya secara rekursif
·Bila tak ada kolom aman, batalkan penempatan terakhir (backtrack)
·Coba kolom lain sampai semua N ratu terpasang tanpa saling menyerang

Prasyarat

·Backtracking
·Grid 2D

Contoh Nyata

·Alokasi frekuensi pemancar radio agar stasiun tak saling mengganggu
·Menempatkan sumber daya yang tak boleh saling bertabrakan
·Penjadwalan agar beberapa kegiatan tak berada di slot atau ruang sama

Kompleksitas O(N!) pada kasus terburuk