Backtracking — Algoritma

Backtracking mencoba semua kemungkinan secara sistematis: coba → jika gagal, mundur (backtrack) → coba yang lain. Analogi: Mencari jalan keluar dari labirin —…

Backtracking adalah cara mencari jawaban dengan mencoba pilihan satu per satu, langkah demi langkah. Kalau sebuah pilihan berujung buntu, pilihan terakhir dibatalkan (mundur, itulah backtrack), lalu pilihan berikutnya dicoba. Mirip mencari jalan keluar labirin: ketemu jalan buntu, balik ke persimpangan terakhir dan coba belokan lain.

🧪 Tebakan cepat: angka 1, 2, dan 3 bisa disusun dalam berapa urutan yang berbeda? Tebak dulu, jawabannya ada di bagian "Pola yang sama: semua susunan".

Contoh: 4 queen di papan 4 × 4

Taruh 4 queen (bidak catur) di papan 4 × 4, satu di tiap baris, supaya gak ada yang saling serang. Queen menyerang sepanjang baris, kolom, dan diagonal. Karena tiap baris cuma berisi satu queen, yang perlu dicek tinggal kolom dan diagonal. Isi baris demi baris, dan di tiap baris coba kolom dari kiri:

Langkah Baris Yang terjadi
1 0 Kolom 0 aman: taruh queen.
2 1 Kolom 0 dan 1 diserang, kolom 2 aman: taruh.
3 2 Kolom 0 sampai 3 diserang semua: buntu.
4 1 Mundur: angkat queen baris 1, coba kolom 3. Aman, taruh.
5 2 Kolom 0 diserang, kolom 1 aman: taruh.
6 3 Semua kolom diserang: buntu lagi, mundur.

Mundurnya bisa sampai baris 0: queen pertama pindah ke kolom 1, dan dari situ ketemu solusi [1, 3, 0, 2] (kolom queen di baris 0, 1, 2, 3).

function solveNQueens(n) {
  const board = Array(n).fill(-1);
  const solutions = [];

  function isSafe(row, col) {
    for (let r = 0; r < row; r++) {
      if (board[r] === col) return false; // satu kolom
      if (Math.abs(board[r] - col) === row - r) return false; // satu diagonal
    }
    return true;
  }

  function solve(row) {
    if (row === n) {
      solutions.push([...board]);
      return;
    }
    for (let col = 0; col < n; col++) {
      if (!isSafe(row, col)) continue;
      board[row] = col; // coba
      solve(row + 1); // lanjut ke baris berikutnya
      board[row] = -1; // batalkan
    }
  }

  solve(0);
  return solutions;
}

console.log(solveNQueens(4)); // [[1, 3, 0, 2], [2, 0, 3, 1]]

Brute force (mencoba semua kemungkinan tanpa pilih-pilih) menyusun 4 × 4 × 4 × 4 = 256 papan penuh dulu, baru dicek. Backtracking menemukan solusi pertama setelah mencoba 26 kotak saja.

Pola yang sama: semua susunan

Permutasi adalah semua urutan berbeda dari isi sebuah array. [1, 2, 3] punya 6: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]. Itu jawaban tebakan tadi. Banyaknya n! (n faktorial): 3 × 2 × 1 = 6, dan 4 angka punya 4 × 3 × 2 × 1 = 24 susunan. Satu angka punya satu susunan: [5] jadi [[5]].

function permutations(arr) {
  const result = [];
  const current = [];
  const dipakai = new Array(arr.length).fill(false);

  function backtrack() {
    if (current.length === arr.length) {
      result.push([...current]);
      return;
    }
    for (let i = 0; i < arr.length; i++) {
      if (dipakai[i]) continue;
      dipakai[i] = true; // coba
      current.push(arr[i]);
      backtrack(); // lanjut
      current.pop(); // batalkan
      dipakai[i] = false;
    }
  }

  backtrack();
  return result;
}

console.log(permutations([1, 2, 3]).length); // 6

Polanya sama dengan queen: coba satu angka yang belum dipakai, lanjut menyusun sisanya, lalu batalkan supaya angka lain bisa dicoba di posisi yang sama. Hasilnya selalu array berisi array, satu array untuk tiap susunan.

Backtracking tetap lambat kalau pilihannya banyak. Tiap tambah satu angka, banyaknya susunan dikali jumlah angkanya: 10 angka sudah 3.628.800 susunan. Pakai untuk data kecil, atau soal yang banyak cabangnya bisa dipangkas.

⚠️ Jebakan yang sering ketemu

TL;DR: Backtracking menyusun jawaban langkah demi langkah: coba satu pilihan, lanjut (sering dengan rekursi), lalu batalkan dan coba pilihan berikutnya. Pilihan yang pasti gagal dibuang lebih awal (pruning), makanya lebih cepat dari brute force. Permutasi n angka ada n! susunan: [1, 2, 3] punya 6, empat angka punya 24. Simpan salinan [...current], dan jangan lupa membatalkan pilihan sesudah rekursi.

Yang akan kamu pelajari