Rangkuman: N-Queens Problem

Backtracking Algorithm

1. Pengertian

N-Queens Problem adalah masalah klasik dalam ilmu komputer dan matematika. Tujuannya adalah menempatkan N ratu (queens) pada papan catur berukuran $N \times N$ sedemikian rupa sehingga tidak ada dua ratu yang saling menyerang. Dalam aturan catur, ratu dapat menyerang ratu lain jika berada di baris, kolom, atau diagonal yang sama.

Masalah ini adalah contoh yang sangat baik untuk dipecahkan menggunakan pendekatan **Backtracking**.

2. Konsep Dasar & Pendekatan Backtracking

Pendekatan Backtracking untuk N-Queens Problem melibatkan penempatan ratu satu per satu di setiap kolom. Untuk setiap ratu yang akan ditempatkan, kita mencoba setiap baris yang mungkin. Jika penempatan aman (tidak diserang oleh ratu lain yang sudah ada), kita lanjutkan ke kolom berikutnya. Jika tidak ada baris yang aman di kolom saat ini, kita "mundur" (backtrack) ke kolom sebelumnya dan mencoba posisi lain untuk ratu di kolom tersebut.

Langkah-langkah Algoritma Backtracking:

  1. Mulai dari kolom pertama (kolom 0).
  2. Untuk kolom saat ini, coba tempatkan ratu di setiap baris (mulai dari baris 0 hingga N-1).
  3. Sebelum menempatkan ratu di posisi $(row, col)$, periksa apakah posisi tersebut aman:
    • Tidak ada ratu lain di baris yang sama.
    • Tidak ada ratu lain di kolom yang sama (ini sudah terjamin karena kita menempatkan ratu per kolom).
    • Tidak ada ratu lain di diagonal atas-kiri.
    • Tidak ada ratu lain di diagonal bawah-kiri.
  4. Jika posisi aman:
    • Tempatkan ratu di posisi tersebut.
    • Rekursif panggil fungsi untuk kolom berikutnya ($col + 1$).
  5. Jika panggilan rekursif berhasil (semua ratu berhasil ditempatkan hingga kolom terakhir), maka temukan satu solusi. Anda bisa menyimpan solusi ini.
  6. Jika panggilan rekursif gagal (tidak ada posisi aman di kolom saat ini, atau rekursi dari kolom berikutnya tidak menemukan solusi), maka "hapus" ratu dari posisi saat ini (backtrack) dan coba baris berikutnya di kolom yang sama.
  7. Jika semua baris di kolom saat ini sudah dicoba dan tidak ada yang berhasil, kembalikan kontrol ke panggilan rekursif sebelumnya.

3. Contoh Ilustrasi (untuk N=4)

Tujuan: Menempatkan 4 ratu di papan $4 \times 4$.

Salah satu solusi (R menandakan Ratu, . menandakan kosong):


. R . .
. . . R
R . . .
. . R .

Penjelasan Singkat Proses:

  • Ratu 1 di (0,1).
  • Ratu 2 mencoba baris di kolom 2, menemukan (1,3) aman.
  • Ratu 3 mencoba baris di kolom 3, menemukan (2,0) aman.
  • Ratu 4 mencoba baris di kolom 4, menemukan (3,2) aman.
  • Solusi ditemukan!

Jika pada suatu langkah tidak ada posisi aman, algoritma akan kembali ke ratu sebelumnya dan mencoba posisi lain.

4. Pseudocode Algoritma


FUNCTION solveNQueens(board_size):
    board = CREATE N x N empty board (e.g., array of characters '.')
    solutions = [] // Untuk menyimpan semua solusi yang ditemukan
    
    // Fungsi rekursif untuk menempatkan ratu
    FUNCTION placeQueen(col):
        IF col == board_size:
            // Semua ratu berhasil ditempatkan, tambahkan solusi ke daftar
            solutions.ADD(board.COPY())
            RETURN

        FOR row FROM 0 TO board_size - 1:
            IF isSafe(row, col, board_size, board):
                board[row][col] = 'Q' // Tempatkan ratu
                placeQueen(col + 1)   // Panggil rekursif untuk kolom berikutnya
                board[row][col] = '.' // Backtrack: Hapus ratu (undo)

    // Fungsi pembantu untuk memeriksa keamanan posisi
    FUNCTION isSafe(row, col, board_size, board):
        // Cek baris ini di sisi kiri
        FOR c FROM 0 TO col - 1:
            IF board[row][c] == 'Q':
                RETURN FALSE
        
        // Cek diagonal atas kiri
        r = row
        c = col
        WHILE r >= 0 AND c >= 0:
            IF board[r][c] == 'Q':
                RETURN FALSE
            r = r - 1
            c = c - 1
            
        // Cek diagonal bawah kiri
        r = row
        c = col
        WHILE r < board_size AND c >= 0:
            IF board[r][c] == 'Q':
                RETURN FALSE
            r = r + 1
            c = c - 1
            
        RETURN TRUE

    placeQueen(0) // Mulai proses dari kolom 0
    RETURN solutions

5. Kompleksitas Waktu & Ruang

  • Kompleksitas Waktu:
    • Secara teoritis, sulit untuk memberikan kompleksitas waktu yang presisi karena sifat backtracking. Pada kasus terburuk, algoritma mungkin mencoba semua permutasi.
    • Kompleksitasnya mendekati $O(N!)$, karena setiap ratu bisa ditempatkan di N posisi, dan ada N ratu, tetapi ada pruning (pemotongan cabang) yang mengurangi pencarian.
    • Rata-rata, jauh lebih baik dari $O(N!)$, tetapi tetap eksponensial.
  • Kompleksitas Ruang: $O(N^2)$ untuk papan catur, atau $O(N)$ jika hanya melacak posisi ratu per kolom. Stack rekursi juga $O(N)$.

6. Aplikasi

  • Dasar untuk memahami algoritma Backtracking.
  • Permasalahan penjadwalan atau alokasi sumber daya yang kompleks dengan banyak batasan.
  • Digunakan dalam pengujian software untuk menghasilkan skenario uji coba.
  • Permainan dan Puzzle.
Kembali ke Materi Materi Selanjutnya