N-QUEENS PROBLEM
—
Dalam dunia komputasi dan matematika, N-Queens Problem merupakan salah satu contoh klasik dari masalah pencarian solusi atau constraint satisfaction problem yang memperlihatkan kekuatan rekursi dan backtracking. Masalah ini didasarkan pada permainan catur, dengan tujuannya adalah menempatkan N ratu pada papan catur berukuran N x N sedemikian rupa sehingga tidak ada dua ratu yang saling menyerang.
Ratu dalam permainan catur dapat bergerak ke segala arah: horizontal, vertikal, dan diagonal. Maka dari itu, tantangannya terletak pada bagaimana menempatkan setiap ratu di papan catur agar tidak ada ratu yang berada pada baris, kolom, atau diagonal yang sama.
Masalah ini tidak hanya menjadi latihan algoritmik yang populer, tetapi juga digunakan dalam bidang:
- Penjadwalan (misalnya penjadwalan tugas tanpa konflik),
- Pemrograman berbasis AI,
- Pencarian solusi logis,
Dan pengujian algoritma backtracking.
N-Queens Problem
Definisi Masalah
Masalah N-Queens adalah sebuah permasalahan klasik dalam bidang ilmu komputer dan matematika kombinatorik yang melibatkan penempatan N buah ratu catur pada sebuah papan catur berukuran N \times N sedemikian rupa sehingga tidak ada dua ratu yang saling menyerang.
- Dalam aturan catur, seorang ratu dapat bergerak secara horizontal (baris), vertikal (kolom), dan diagonal.
- Oleh karena itu, solusi dari masalah ini harus memastikan bahwa tidak ada dua ratu yang berada pada baris, kolom, atau diagonal yang sama.
- Contoh paling terkenal adalah masalah 8-Queens, yaitu menempatkan 8 ratu di papan 8 \times 8.
Tujuan Masalah N-Queens
Tujuan utama dari masalah ini adalah:
- Menemukan semua konfigurasi penempatan ratu yang memenuhi syarat tidak saling menyerang.
- Mengembangkan dan menguji algoritma pencarian dan optimasi, seperti backtracking, DFS, heuristic search, atau algoritma genetika.
- Melatih logika pemrograman dan pemecahan masalah, terutama dalam konteks constraint satisfaction problem (CSP).
Pentingnya Masalah N-Queens
Masalah N-Queens penting dalam berbagai konteks, di antaranya:
- Sebagai Studi Kasus dalam AI dan Algoritma:
- Masalah ini digunakan secara luas untuk mengajarkan teknik pencarian seperti backtracking, branch and bound, serta algoritma heuristic dan metaheuristic. Ini menjadikannya landasan dalam studi artificial intelligence dan operations research.
- Model Permasalahan Constraint Satisfaction:
- N-Queens adalah contoh ideal dari masalah CSP, di mana kita harus menetapkan nilai (posisi ratu) ke dalam variabel (baris/kolom) tanpa melanggar kendala (serangan).
- Aplikasi dalam Dunia Nyata:
- Walau berbasis permainan catur, prinsip-prinsip di balik N-Queens dapat diterapkan dalam masalah nyata seperti:
- Penjadwalan tugas (di mana konflik harus dihindari).
- Penempatan modul dalam sirkuit elektronik.
- Dan pengalokasian sumber daya yang saling eksklusif.
- Walau berbasis permainan catur, prinsip-prinsip di balik N-Queens dapat diterapkan dalam masalah nyata seperti:
- Kompleksitas dan Skalabilitas:
- Masalah ini menunjukkan bagaimana kompleksitas meningkat secara eksponensial dengan bertambahnya nilai N, sehingga cocok sebagai bahan evaluasi efisiensi algoritma dalam skala besar.
Mengapa N-Queens adalah Masalah Backtracking
N-Queens adalah masalah klasik yang paling sering diselesaikan menggunakan teknik backtracking. Ini karena:
- Pendekatan Rekursif dan Bertahap:
- Dalam penyelesaian N-Queens, kita menempatkan ratu satu per satu, biasanya dimulai dari baris pertama.
- Untuk setiap baris, kita mencoba meletakkan ratu di setiap kolom satu per satu dan memeriksa apakah posisi tersebut aman (tidak diserang oleh ratu sebelumnya).
- Jika aman, kita lanjut ke baris berikutnya. Jika tidak ada posisi yang aman, kita kembali ke baris sebelumnya dan mencoba posisi lain—proses inilah yang disebut backtracking.
- Pohon Pencarian Solusi:
- Setiap penempatan ratu mewakili satu simpul dalam pohon pencarian.
- Jalur dari akar ke daun mewakili satu kemungkinan solusi. Jika sebuah jalur tidak bisa menghasilkan solusi yang valid, kita prune (pangkas) jalur itu dan mencoba cabang lain.
- Sifat Non-deterministik:
- Karena ada banyak kemungkinan posisi untuk setiap ratu, dan tidak diketahui posisi yang benar sejak awal, kita harus mencoba semua kemungkinan dengan sistematis. Ini menjadikan backtracking sebagai teknik yang sangat cocok.
Relevansi dalam Mata Kuliah Design and Analysis of Algorithms (DAA)
- Studi Kasus Teknik Backtracking:
- N-Queens adalah contoh klasik yang digunakan untuk mengilustrasikan konsep backtracking secara sistematis, sehingga sangat relevan dalam DAA. Mahasiswa bisa belajar bagaimana menyusun solusi secara bertahap dan menghindari eksplorasi solusi yang tidak mungkin.
- Analisis Kompleksitas Algoritma:
- Masalah ini membantu memahami analisis waktu dan ruang dari algoritma brute-force versus algoritma berbasis backtracking yang lebih efisien. Meskipun backtracking memiliki kompleksitas waktu eksponensial dalam kasus terburuk, teknik ini tetap jauh lebih cepat dibanding mencoba semua kemungkinan secara buta.
- Pengenalan Constraint Satisfaction Problem (CSP):
- N-Queens memperkenalkan mahasiswa pada CSP, sebuah topik penting dalam kecerdasan buatan dan optimasi. Teknik backtracking dapat diperluas menjadi backtracking dengan forward checking atau backjumping, yang relevan dalam studi algoritma canggih.
Backtracking
Backtracking adalah teknik penyelesaian masalah yang mencoba membangun solusi langkah demi langkah dan “mundur” (backtrack) ketika menemui jalan buntu (dead end). Ini adalah pendekatan brute-force yang sistematis dengan optimasi, di mana solusi yang tidak valid dibuang secepat mungkin.
Langkah-langkah dalam Algoritma Backtracking:
- Pilih Keputusan (Decision Choice):
- Pada setiap langkah, pilih opsi yang mungkin dari kandidat solusi.
- Contoh: Dalam masalah N-Queens, pilih kolom untuk menempatkan ratu di baris berikutnya.
- Batasan (Constraint Check):
- Periksa apakah pilihan tersebut valid berdasarkan aturan masalah.
- Jika valid, lanjut ke langkah berikutnya.
- Jika tidak valid, abaikan opsi ini dan coba opsi lain (backtrack).
- Rekursi (Recursive Exploration):
- Jika pilihan valid, rekursif melanjutkan pencarian solusi dengan keputusan ini.
- Backtrack (Kembali jika Dead End):
- Jika tidak ada solusi yang ditemukan setelah memilih opsi tertentu, batalkan keputusan terakhir (undo) dan coba opsi lain.
- Basis Kasus (Base Case):
- Jika semua keputusan telah mengarah ke solusi lengkap, catat solusinya (atau kembalikan solusi).
Contoh dalam Permutasi Angka
Mari kita cari semua permutasi dari [1, 2, 3] menggunakan algoritma backtracking.
Langkah Algoritma:
- Pilih angka pertama: 1
- Subproblem: Cari permutasi dari
[2, 3]\rightarrow[1,2,3],[1,3,2] - Backtrack: Kembali ke pilihan awal.
- Subproblem: Cari permutasi dari
- Pilih angka pertama: 2
- Subproblem: Cari permutasi dari
[1, 3]\rightarrow[2,1,3],[2,3,1] - Backtrack: Kembali ke pilihan awal.
- Subproblem: Cari permutasi dari
- Pilih angka pertama: 3
- Subproblem: Cari permutasi dari
[1, 2]\rightarrow[3,1,2],[3,2,1]
- Subproblem: Cari permutasi dari
Solusi Akhir: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Kesimpulan dari Backtracking
Backtracking adalah pendekatan exhaustive search dengan optimasi, di mana solusi dibangun bertahap dan dibatalkan jika tidak valid. Alurnya melibatkan eksplorasi rekursif, pemeriksaan batasan, dan pengembalian (undo) jika gagal.
❓ Permasalahan
Diberikan papan catur N x N, tempatkan N buah ratu sedemikian rupa sehingga tidak ada dua ratu yang saling menyerang, artinya:
- Tidak ada dua ratu di baris atau kolom yang sama.
- Tidak ada dua ratu di diagonal yang sama.
Input:
- Bilangan bulat
N, ukuran papan dan jumlah ratu.
Output:
- Satu atau semua konfigurasi papan catur di mana ratu-ratu bisa ditempatkan dengan aman.
Solusi (Implementasi C++)
Pendekatan yang umum digunakan adalah backtracking, yaitu mencoba satu per satu kemungkinan posisi ratu dan kembali ke langkah sebelumnya bila terjadi konflik.
Kode C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <vector>
using namespace std;
bool isSafe(int row, int col, vector<string>& board, int n) {
// Cek kolom atas
for (int i = 0; i < row; i++)
if (board[i][col] == 'Q') return false;
// Cek diagonal kiri atas
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
if (board[i][j] == 'Q') return false;
// Cek diagonal kanan atas
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
if (board[i][j] == 'Q') return false;
return true;
}
void solve(int row, vector<string>& board, vector<vector<string>>& solutions, int n) {
if (row == n) {
solutions.push_back(board);
return;
}
for (int col = 0; col < n; col++) {
if (isSafe(row, col, board, n)) {
board[row][col] = 'Q';
solve(row + 1, board, solutions, n);
board[row][col] = '.'; // backtrack
}
}
}
void nQueens(int n) {
vector<vector<string>> solutions;
vector<string> board(n, string(n, '.'));
solve(0, board, solutions, n);
cout << "Jumlah solusi: " << solutions.size() << endl;
for (const auto& sol : solutions) {
for (const string& row : sol)
cout << row << endl;
cout << "----------" << endl;
}
}
int main() {
int N = 4;
nQueens(N);
return 0;
}
Kesimpulan
N-Queens Problem adalah masalah klasik yang menguji kemampuan kita dalam penalaran kombinatorik dan penerapan algoritma. Dengan menggunakan pendekatan backtracking, kita dapat secara sistematis mengeksplorasi semua kemungkinan penempatan ratu, memangkas cabang yang tidak valid, dan menemukan setiap konfigurasi yang memenuhi batasan.
Masalah ini bukan hanya sekedar teka-teki catur; ia berfungsi sebagai studi kasus fundamental dalam ilmu komputer untuk mengajarkan konsep-konsep kunci seperti pencarian rekursif, manajemen batasan, dan analisis kompleksitas algoritma. Penerapannya meluas hingga ke penjadwalan, alokasi sumber daya, dan bidang optimasi lainnya di dunia nyata. Dengan demikian, penguasaan N-Queens Problem memberikan dasar yang kuat untuk memahami dan menyelesaikan berbagai masalah komputasi yang lebih kompleks.
—