Solusi Leetcode - N-Queens

Puzzle N Queens meminta semua penempatan valid untuk n queen di papan catur n x n. Nggak boleh ada dua queen yang saling menyerang. Hasilnya berupa konfigurasi papan, bukan cuma jumlahnya.

Tantangannya adalah melacak posisi queen, memvalidasi penempatan, dan menyusun papan output secara efisien.

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 buah catur apa pun yang ada di baris, kolom, atau diagonal yang sama.

Diberikan integer n, kita perlu me-return semua solusi berbeda untuk puzzle ini. Setiap solusi berupa konfigurasi papan dengan aturan:

• 'Q' melambangkan queen
• '.' melambangkan kotak kosong

Ini constraint-nya:

• 1 <= n <= 9
• Kita harus me-return semua solusi yang berbeda

Contoh 1:

• Input: n = 4
• Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
• Penjelasan: Papan 4x4 punya tepat dua solusi berbeda

Contoh 2:

• Input: n = 1
• Output: [["Q"]]
• Penjelasan: Cuma ada satu cara untuk menaruh satu queen

Solusi berbasis array

Pendekatan berbasis array bikin logika validasinya tetap eksplisit:

function solveNQueens(n) {
  const result = [];
  const queens = new Array(n).fill(0);

  function isSafe(row, col) {
    for (let r = 0; r < row; r++) {
      // Check if same column or same diagonal
      if (
        queens[r] === col ||
        Math.abs(queens[r] - col) === Math.abs(r - row)
      ) {
        return false;
      }
    }
    return true;
  }

  function buildBoard() {
    return queens.map((col) => ".".repeat(col) + "Q" + ".".repeat(n - col - 1));
  }

  function backtrack(row) {
    if (row === n) {
      result.push(buildBoard());
      return;
    }

    for (let col = 0; col < n; col++) {
      if (isSafe(row, col)) {
        queens[row] = col;
        backtrack(row + 1);
        queens[row] = 0; // Backtrack
      }
    }
  }

  backtrack(0);
  return result;
}

// Example usage:
console.log(solveNQueens(4));
// Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Solusi ini gampang diperiksa. Untuk n <= 9, solusi ini masuk dalam constraint yang ada di soal.

Cara Kerjanya

Untuk n = 4, pencariannya pertama-tama mencoba cabang ini:

Mulai dari baris 0:

• Coba col 0: isSafe me-return true (belum ada queen sebelumnya)
• queens = [0, 0, 0, 0] dengan queens[0] = 0

Pindah ke baris 1:

• Coba col 0: Nggak aman (kolomnya sama dengan baris 0)
• Coba col 1: Nggak aman (diagonal: |0-1| = |0-1| bernilai true)
• Coba col 2: Aman!
• queens = [0, 2, 0, 0]

Pindah ke baris 2:

• Coba col 0: Nggak aman (kolomnya sama dengan baris 0)
• Coba col 1: Nggak aman (diagonal dengan baris 1: |2-1| = |1-2| bernilai true)
• Coba col 2: Nggak aman (kolomnya sama dengan baris 1)
• Coba col 3: Nggak aman (diagonal dengan baris 1: |2-1| = |3-2| bernilai true)
• Backtrack ke baris 1

Lanjutkan proses ini sampai kita menemukan semua konfigurasi yang valid.

Waktu kita menyelesaikan sebuah solusi dengan queens = [1, 3, 0, 2], kita mengubahnya jadi:

[".Q..",
 "...Q",
 "Q...",
 "..Q."]

Pendekatan Optimasi dengan Set

Kalau kita mau mengoptimasi validasinya dari O(n) jadi O(1), kita bisa pakai set untuk melacak kolom dan diagonal yang udah terisi:

function solveNQueens(n) {
  const result = [];
  const cols = new Set();
  const posDiag = new Set(); // row + col
  const negDiag = new Set(); // row - col
  const queens = [];

  function buildBoard() {
    return queens.map((col) => ".".repeat(col) + "Q" + ".".repeat(n - col - 1));
  }

  function backtrack(row) {
    if (row === n) {
      result.push(buildBoard());
      return;
    }

    for (let col = 0; col < n; col++) {
      if (cols.has(col) || posDiag.has(row + col) || negDiag.has(row - col)) {
        continue;
      }

      // Place queen
      queens.push(col);
      cols.add(col);
      posDiag.add(row + col);
      negDiag.add(row - col);

      backtrack(row + 1);

      // Backtrack
      queens.pop();
      cols.delete(col);
      posDiag.delete(row + col);
      negDiag.delete(row - col);
    }
  }

  backtrack(0);
  return result;
}

Pendekatan ini menukar sedikit kompleksitas kode dengan pengecekan validasi O(1), bukan O(n).

Bitmasking

Bitmasking merepresentasikan kolom dan diagonal yang terisi sebagai bit, sehingga validasinya bisa berjalan dalam waktu konstan:

function solveNQueensBitmasking(n) {
  const result = [];
  const queens = [];

  function buildBoard() {
    return queens.map((col) => ".".repeat(col) + "Q" + ".".repeat(n - col - 1));
  }

  function backtrack(row, cols, posDiag, negDiag) {
    if (row === n) {
      result.push(buildBoard());
      return;
    }

    // Find available positions using bitwise operations
    let availablePositions = ((1 << n) - 1) & ~(cols | posDiag | negDiag);

    while (availablePositions) {
      // Extract rightmost available position
      const position = availablePositions & -availablePositions;
      availablePositions -= position;

      // Convert bit position to column index
      const col = Math.log2(position);
      queens.push(col);

      backtrack(
        row + 1,
        cols | position,
        (posDiag | position) << 1,
        (negDiag | position) >> 1
      );

      queens.pop();
    }
  }

  backtrack(0, 0, 0, 0);
  return result;
}

Perbandingan Performa

Rekomendasi saya: Solusi berbasis array adalah pilihan default yang praktis untuk n <= 9. Solusi ini gampang dijelaskan waktu interview dan masuk dalam constraint yang disebutkan.

Jebakan Umum

Waktu mengimplementasikan solusi ini, hati-hati dengan:

1. Format papan: Ingat bahwa setiap baris berupa string, bukan array berisi karakter. Output-nya adalah array berisi string.

2. Deep copying: Waktu menambahkan solusi ke hasil, pastikan kamu bikin papan baru. Memanggil buildBoard() bakal bikin string baru setiap kali.

3. Pembersihan saat backtracking: Selalu batalkan semua perubahan waktu backtracking. Untuk pendekatan array, reset queens[row] = 0. Untuk pendekatan set, hapus dari semua set.

4. Validasi diagonal: Rumus Math.abs(queens[r] - col) === Math.abs(r - row) mengecek kedua diagonal dalam satu kondisi.

5. Off by one error: Waktu menyusun string dengan .repeat(), pastikan hitungannya benar: .repeat(col) + 'Q' + .repeat(n - col - 1) menghasilkan tepat n karakter.

Memilih implementasi

• Pendekatan berbasis array dengan isSafe itu simpel dan cocok untuk interview
• Simpan satu kolom per baris dan susun papan cuma untuk solusi yang udah lengkap
• Rumus diagonal mengecek kedua diagonal, sementara set memberikan validasi O(1)
• Bitmasking mengurangi bookkeeping tapi menambah kompleksitas, jadi pakai cuma kalau memang perlu

Pendekatan berbasis array gampang diverifikasi dan memenuhi constraint yang diberikan.