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.
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:
[".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
| Pendekatan | Validasi | Kejelasan Kode | Paling Cocok Untuk |
|---|---|---|---|
| Berbasis array yang rapi | O(n) per pengecekan | Paling tinggi | Interview |
| Berbasis set | O(1) per pengecekan | Tinggi | Kode yang fokus ke performa |
| Bitmasking | O(1) per pengecekan | Sedang | Competitive 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
-
Format papan: Ingat bahwa setiap baris berupa string, bukan array berisi karakter. Output-nya adalah array berisi string.
-
Deep copying: Waktu menambahkan solusi ke hasil, pastikan kamu bikin papan baru. Memanggil
buildBoard()bakal bikin string baru setiap kali. -
Pembersihan saat backtracking: Selalu batalkan semua perubahan waktu backtracking. Untuk pendekatan array, reset
queens[row] = 0. Untuk pendekatan set, hapus dari semua set. -
Validasi diagonal: Rumus
Math.abs(queens[r] - col) === Math.abs(r - row)mengecek kedua diagonal dalam satu kondisi. -
Off by one error: Waktu menyusun string dengan
.repeat(), pastikan hitungannya benar:.repeat(col) + 'Q' + .repeat(n - col - 1)menghasilkan tepat n karakter.

Memuat komentar...