LeetCode Grinding
Algorithms3 menit baca

Solusi Leetcode - N-Queens

Pakai backtracking untuk mencari susunan papan catur tanpa dua queen yang saling menyerang.

Di artikel ini 7 bagian

Menaruh satu queen per baris menghilangkan konflik baris dari pencarian. Untuk setiap queen baru, aku cuma perlu mengecek kolom dan diagonal yang ditempati queen di baris sebelumnya.

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

Array menyimpan satu index kolom untuk setiap baris. Sebelum menaruh queen, isSafe mengeceknya terhadap queen yang udah ditempatkan.

javascript
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.."]]

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:

text
[".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:

javascript
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:

javascript
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

PendekatanValidasiKejelasan KodePaling Cocok Untuk
Berbasis array yang rapiO(n) per pengecekanPaling tinggiInterview
Berbasis setO(1) per pengecekanTinggiKode yang fokus ke performa
BitmaskingO(1) per pengecekanSedangCompetitive programming

Aku lebih memilih versi array untuk menjelaskan pencarian. Pengecekannya mengikuti aturan catur secara langsung, dan n dibatasi sampai 9 di soal ini.

Jebakan Umum

  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.

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan