Solusi Leetcode - N-Queens II

Soal N Queens yang klasik mengembalikan konfigurasi papan. N Queens II cuma menghitung penempatan yang valid, jadi nggak perlu membangun papan.

Karena papannya nggak dibangun, versi ini bikin kita bisa membandingkan berbagai strategi validasi dan penghitungan.

Memahami Soalnya

Puzzle n queens meminta kita menaruh n queen di papan catur n x n sehingga nggak ada dua queen yang bisa saling menyerang. Queen bisa menyerang secara horizontal, vertikal, dan diagonal.

Diberikan integer n, kita perlu me-return jumlah solusi berbeda untuk puzzle ini.

Ini constraint-nya:

• 1 <= n <= 9
• Kita cuma perlu menghitung solusinya, bukan meng-generate-nya

Contoh 1:

• Input: n = 4
• Output: 2
• Penjelasan: Papan 4x4 punya tepat dua solusi berbeda

Contoh 2:

• Input: n = 1
• Output: 1
• Penjelasan: Cuma ada satu cara untuk menaruh satu queen

Pendekatan Pertama Saya

Pikiran awal saya: "I'll just try every possible placement and count the valid ones." Pencarian brute force bakal memeriksa semua susunan n posisi queen di n² kotak. Ini termasuk penempatan dengan beberapa queen di satu baris.

Setiap queen harus ada di baris yang berbeda, jadi saya bisa menaruh tepat satu queen per baris. Pencariannya lalu tinggal memilih kolom untuk setiap baris.

function totalNQueensNaive(n) {
  let count = 0;
  const board = Array(n).fill().map(() => Array(n).fill('.'));
  
  function isValid(row, col) {
    // Check column
    for (let i = 0; i < row; i++) {
      if (board[i][col] === 'Q') return false;
    }
    
    // Check diagonal and anti-diagonal
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] === 'Q') return false;
    }
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (board[i][j] === 'Q') return false;
    }
    
    return true;
  }
  
  function backtrack(row) {
    if (row === n) {
      count++;
      return;
    }
    
    for (let col = 0; col < n; col++) {
      if (isValid(row, col)) {
        board[row][col] = 'Q';
        backtrack(row + 1);
        board[row][col] = '.'; // Backtrack
      }
    }
  }
  
  backtrack(0);
  return count;
}

Ini jalan, tapi mengecek validitas pakai papan 2D lebih lambat dari yang seharusnya.

Insight Optimasi dengan Set

Pendekatan berbasis set nggak perlu memelihara papan 2D. Pendekatan ini langsung melacak kolom dan diagonal yang udah terisi.

Setiap diagonal punya jumlah atau selisih koordinat yang konstan:

• Untuk diagonal dari kiri atas ke kanan bawah: semua posisi punya nilai row - col yang sama
• Untuk diagonal dari kanan atas ke kiri bawah: semua posisi punya nilai row + col yang sama

Dengan melacak nilai-nilai ini di set, saya bisa mengecek apakah sebuah posisi valid dalam waktu konstan, bukan waktu linear.

Solusi Saya

function totalNQueens(n) {
  let count = 0;
  
  // Track which columns and diagonals are occupied
  const cols = new Set();
  const posDiag = new Set(); // row + col is constant
  const negDiag = new Set(); // row - col is constant
  
  function backtrack(row) {
    // Base case: all queens placed successfully
    if (row === n) {
      count++;
      return;
    }
    
    // Try placing queen in each column of current row
    for (let col = 0; col < n; col++) {
      // Check if this position conflicts with any existing queens
      if (cols.has(col) || posDiag.has(row + col) || negDiag.has(row - col)) {
        continue; // Skip this position
      }
      
      // Place queen: mark column and diagonals as occupied
      cols.add(col);
      posDiag.add(row + col);
      negDiag.add(row - col);
      
      // Recurse to next row
      backtrack(row + 1);
      
      // Backtrack: remove queen and free up column and diagonals
      cols.delete(col);
      posDiag.delete(row + col);
      negDiag.delete(row - col);
    }
  }
  
  backtrack(0);
  return count;
}

// Example usage:
console.log(totalNQueens(4)); // Output: 2
console.log(totalNQueens(1)); // Output: 1

Cara Kerjanya

Untuk n = 4, backtracking-nya berjalan seperti ini:

Mulai dari baris 0:

• Coba col 0: Taruh queen di (0, 0). Tandai col 0, posDiag 0, negDiag 0
• Pindah ke baris 1: Coba col 0 (terisi), col 1 (terisi oleh negDiag), col 2 (valid)
• Taruh queen di (1, 2). Tandai col 2, posDiag 3, negDiag -1
• Lanjutkan proses ini...
• Ternyata nggak ada solusi valid yang dimulai dari (0, 0)
• Backtrack dan coba (0, 1) sebagai posisi awal
• Lanjutkan sampai semua posisi awal udah dicoba

Algoritmanya menjelajahi semua kemungkinan secara sistematis, pakai set untuk cepat menentukan apakah sebuah posisi valid tanpa mengecek seluruh papan.

Bitmasking

Bitmasking mengganti set dengan integer dan operasi bitwise. Setiap bit merepresentasikan kolom atau diagonal yang terisi.

Mask kolom mencatat kolom yang terisi. Mask diagonal mencatat posisi yang diserang di baris saat ini. Untuk n = 4, kolom 0 dan 2 yang terisi menghasilkan mask kolom 0101 dalam biner, atau 5 dalam desimal.

Operasi AND, OR, dan NOT mengecek dan meng-update state itu sebagai integer mask.

function totalNQueensBitmasking(n) {
  let count = 0;
  
  function backtrack(row, cols, posDiag, negDiag) {
    // Base case: all queens placed
    if (row === n) {
      count++;
      return;
    }
    
    // Calculate available positions for this row
    // Start with all positions (all bits set to 1 for n positions)
    // Then eliminate occupied columns and diagonals using bitwise operations
    let availablePositions = ((1 << n) - 1) & ~(cols | posDiag | negDiag);
    
    // Try each available position
    while (availablePositions) {
      // Get the rightmost bit (rightmost available position)
      const position = availablePositions & -availablePositions;
      
      // Remove this position from available positions
      availablePositions -= position;
      
      // Recurse with updated state
      // cols | position: mark this column as occupied
      // (posDiag | position) << 1: shift positive diagonal left
      // (negDiag | position) >> 1: shift negative diagonal right
      backtrack(
        row + 1,
        cols | position,
        (posDiag | position) << 1,
        (negDiag | position) >> 1
      );
    }
  }
  
  backtrack(0, 0, 0, 0);
  return count;
}

// Example usage:
console.log(totalNQueensBitmasking(4)); // Output: 2
console.log(totalNQueensBitmasking(8)); // Output: 92

Operasi bit dan pergeseran diagonal

Operasi bitwise utamanya adalah:

1. (1 << n) - 1: Membuat mask dengan n bit bernilai 1. Untuk n = 4, mask-nya 1111 dalam biner (15 dalam desimal).

2. cols | posDiag | negDiag: Menggabungkan semua posisi yang terisi pakai OR. Kalau sebuah bit bernilai 1 di salah satunya, bit itu juga 1 di hasilnya.

3. ~(cols | posDiag | negDiag): Membalik bit pakai NOT. Sekarang 1 berarti tersedia, 0 berarti terisi.

4. availablePositions & -availablePositions: Ekspresi ini mengisolasi bit 1 paling kanan. Misalnya, kalau availablePositions bernilai 1010, hasilnya 0010.

5. (posDiag | position) << 1: Setelah menaruh queen, kita geser diagonal positif ke kiri karena saat kita turun satu baris, diagonalnya bergeser ke kiri.

6. (negDiag | position) >> 1: Dengan cara yang sama, kita geser diagonal negatif ke kanan.

Untuk n = 4, baris 0, dan posisi 0 (bit 0001), state-nya berubah seperti ini:

• Awal: cols = 0000, posDiag = 0000, negDiag = 0000
• Taruh queen di posisi 0001
• cols baru = 0001
• posDiag baru = 0001 digeser ke kiri = 0010
• negDiag baru = 0001 digeser ke kanan = 0000
• Untuk baris 1: terisi = 0001 | 0010 | 0000 = 0011
• Jadi posisi 0 dan 1 terblokir, cuma posisi 2 dan 3 yang tersedia

Perbandingan Performa

Perbandingan ketiga pendekatannya seperti ini:

Kenapa bitmasking bisa mengurangi overhead:

Varian set dan bitmask sama-sama punya batas pencarian O(n!), tapi bitmasking menyimpan state per posisi di integer:

1. State yang ringkas: State-nya muat di beberapa integer, bukan di beberapa struktur data
2. Tanpa bookkeeping set: Pencariannya nggak mengalokasikan atau meng-update objek Set di setiap posisi

Space Complexity untuk Semua Pendekatan:

• Recursion stack: O(n) untuk semua pendekatan
• Penyimpanan state: O(n²) untuk naive, O(n) untuk berbasis set dan bitmasking
• Bitmasking menyimpan state kolom dan diagonal di integer mask, di samping recursion stack

Pencariannya menjelajahi O(n!) state penempatan. Versi papan 2D menambahkan scan O(n) di setiap pengecekan keamanan, jadi batasnya O(n × n!). Varian set dan bitmask pakai pengecekan konflik O(1) dan tetap di batas O(n!).

Jebakan Umum

Waktu mengimplementasikan solusi ini, hati-hati dengan:

1. Rumus diagonal: Pastikan kamu paham kenapa row + col dan row - col mengidentifikasi diagonal secara unik. Gambar aja kalau perlu.

2. Pembersihan saat backtracking: Selalu hapus queen dari set setelah rekursi. Kalau lupa, hasilnya bakal salah.

3. Base case: Base case-nya adalah saat row === n, bukan row === n - 1. Kita mulai dari baris 0, jadi sampai di baris n berarti semua n queen udah ditaruh.

4. Operasi set: Ingat untuk pakai add() dan delete() untuk Set, bukan operasi array.

5. Bit shift di bitmasking: Untuk setiap baris baru, geser mask diagonal positif ke kiri (<<). Geser mask diagonal negatif ke kanan (>>). Kalau kebalik, hasilnya bakal salah.

6. Integer overflow: Angka di JavaScript pakai representasi floating point, tapi operasi bitwise ini pakai integer 32 bit. Constraint n <= 9 bikin mask-nya tetap di dalam rentang itu.

7. Mengambil bit paling kanan: Trik availablePositions & -availablePositions bergantung pada representasi two's complement. Di JavaScript, ini jalan dengan benar, tapi memahami alasannya membantu menghindari bug.

Memilih representasi

• Backtracking cocok untuk soal constraint satisfaction kayak N Queens, dan satu queen per baris mengecilkan search space
• Set bisa mengoptimasi pengecekan validitas dari O(n) jadi O(1)
• Memahami matematika di balik diagonal (row + col dan row - col) memungkinkan deteksi konflik yang efisien
• Pola backtracking: coba sebuah pilihan, rekursi, lalu batalkan pilihan itu
• Bitmasking merepresentasikan state pencarian sebagai integer dan menghindari bookkeeping set, dengan harga kompleksitas tambahan