Masalah N-Queen

Apa itu Masalah N-Queen?

Masalah N-Queen adalah teka-teki ilmu komputer klasik yang bertanya: "Dengan papan catur N×N, bagaimana cara menempatkan N ratu pada papan sehingga tidak ada dua ratu yang saling mengancam?" Artinya tidak ada dua ratu yang berada pada baris, kolom, atau diagonal yang sama.

Masalah ini pertama kali diajukan pada tahun 1848 oleh komposer catur Max Bezzel dan sejak itu menjadi:

• Patokan untuk algoritma backtracking
• Pertanyaan wawancara umum untuk peran teknis
• Alat pengajaran untuk rekursi dan penyelesaian kendala
• Topik penelitian dalam matematika dan ilmu komputer

Kendala Masalah

Contoh: Masalah 4-Ratu

Masalah 8-Ratu (papan catur standar) memiliki 92 solusi, dengan 12 solusi fundamental jika menganggap rotasi dan refleksi sebagai identik.

Pendekatan Backtracking

Solusi standar menggunakan algoritma backtracking yang:

1. Menempatkan ratu satu per satu di kolom berbeda
   • Mulai dari kolom paling kiri
   • Coba semua baris di kolom saat ini
2. Untuk setiap penempatan, periksa apakah ratu aman
   • Tidak ada ratu di baris yang sama di sebelah kiri
   • Tidak ada ratu di diagonal atas ke kiri
   • Tidak ada ratu di diagonal bawah ke kiri
3. Jika aman, tempatkan ratu secara rekursif di kolom berikutnya
4. Jika tidak ada posisi aman, backtrack ke kolom sebelumnya
   • Hapus ratu dari posisi saat ini
   • Coba baris berikutnya di kolom sebelumnya

Implementasi Python

def solve_n_queens(n):
    def is_safe(board, row, col):
        # Periksa baris ini di sisi kiri
        for i in range(col):
            if board[row][i] == 1:
                return False
        
        # Periksa diagonal atas di sisi kiri
        for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
            if board[i][j] == 1:
                return False
        
        # Periksa diagonal bawah di sisi kiri
        for i, j in zip(range(row, n, 1), range(col, -1, -1)):
            if board[i][j] == 1:
                return False
        
        return True

    def solve_util(board, col):
        # Kasus dasar: Jika semua ratu ditempatkan
        if col >= n:
            solutions.append([row[:] for row in board])
            return True
        
        # Pertimbangkan kolom ini dan coba tempatkan ratu di semua baris
        res = False
        for i in range(n):
            if is_safe(board, i, col):
                board[i][col] = 1
                
                # Rekursi untuk menempatkan ratu sisanya
                res = solve_util(board, col + 1) or res
                
                # Backtrack: hapus ratu jika tidak ditemukan solusi
                board[i][col] = 0
        
        return res

    solutions = []
    board = [[0 for _ in range(n)] for _ in range(n)]
    solve_util(board, 0)
    return solutions

# Contoh penggunaan
n = 4
solutions = solve_n_queens(n)
print(f"Jumlah solusi untuk {n}-Ratu:", len(solutions))
for sol in solutions:
    for row in sol:
        print(' '.join('Q' if cell else '.' for cell in row))
    print()

Implementasi JavaScript

function solveNQueens(n) {
    const solutions = [];
    
    function isSafe(board, row, col) {
        // Periksa sisi kiri baris saat ini
        for (let i = 0; i < col; i++) {
            if (board[row][i] === 1) return false;
        }
        
        // Periksa diagonal atas
        for (let i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] === 1) return false;
        }
        
        // Periksa diagonal bawah
        for (let i = row, j = col; i < n && j >= 0; i++, j--) {
            if (board[i][j] === 1) return false;
        }
        
        return true;
    }
    
    function solveUtil(board, col) {
        // Semua ratu ditempatkan
        if (col === n) {
            // Tambahkan solusi (salin papan)
            solutions.push(board.map(row => [...row]));
            return;
        }
        
        // Coba semua baris di kolom saat ini
        for (let i = 0; i < n; i++) {
            if (isSafe(board, i, col)) {
                board[i][col] = 1;  // Tempatkan ratu
                solveUtil(board, col + 1);
                board[i][col] = 0;  // Backtrack
            }
        }
    }
    
    // Inisialisasi papan kosong
    const board = Array(n).fill().map(() => Array(n).fill(0));
    solveUtil(board, 0);
    
    return solutions;
}

// Contoh penggunaan
const n = 4;
const solutions = solveNQueens(n);
console.log('Jumlah solusi untuk N-Queen:', solutions.length);
solutions.forEach((sol, idx) => {
    console.log("Solusi idx + 1:");
    console.log(sol.map(row => row.map(cell => cell ? 'Q' : '.').join(' ')).join('\n'));
    console.log();
});

Optimisasi dan Variasi

Optimisasi:

• Bitmasking:Representasikan keadaan papan dengan bit untuk pemeriksaan konflik lebih cepat
• Pemecahan simetri:Manfaatkan simetri papan untuk mengurangi komputasi
• Pendekatan iteratif:Hindari batas stack rekursi untuk N besar

Variasi:

• N-Benteng:Ratu hanya bisa bergerak seperti benteng (tanpa kendala diagonal)
• Superqueens:Ratu yang juga bisa bergerak seperti kuda
• Papan toroidal:Papan yang melingkar di tepinya
• N-Queen 3D:Ekstensi ke papan tiga dimensi

Analisis Kompleksitas

Aplikasi Dunia Nyata

• Komputasi paralel:Penjadwalan tugas di mana tugas tidak boleh konflik
• Pengujian VLSI:Aplikasi desain dan pengujian chip
• Kontrol lalu lintas udara:Penjadwalan pesawat di landasan pacu tanpa konflik
• Penyelesaian kendala:Patokan untuk pemecah CSP
• Pendidikan algoritma:Pengajaran backtracking dan rekursi

Kesimpulan

Masalah N-Queen adalah contoh klasik dari masalah penyelesaian kendala yang dengan indah menunjukkan kekuatan algoritma backtracking. Meskipun solusi naif memiliki kompleksitas eksponensial, ini berfungsi sebagai fondasi penting untuk memahami teknik yang lebih maju dalam desain algoritma. Kesederhanaan masalah dalam perumusan namun kompleksitas dalam solusi membuatnya menjadi favorit abadi dalam pendidikan dan penelitian ilmu komputer.