Rekursi sudah menjadi alat harian kita: merge sort, traversal tree, dan pencarian BST semuanya memanggil dirinya sendiri pada masalah yang lebih kecil. Backtracking menambahkan satu langkah yang mengubah rekursi dari menghitung menjadi menjelajah: setelah mencoba satu pilihan hingga tuntas, kita mundur (undo) dan mencoba pilihan lain. Pola tiga langkahnya sederhana dan selalu sama — pilih, jelajahi, urungkan. Chapter ini menerapkan pola itu pada dua masalah klasik yang hasilnya bisa kita verifikasi dengan mata: semua permutasi dari {1, 2, 3}, dan N-Queens pada papan 4x4 yang terkenal hanya punya dua solusi.

Pola Pilih-Jelajahi-Urungkan #

Cara paling ringkas melihat pola ini adalah menghasilkan semua permutasi: pada setiap posisi, kita menukar satu kandidat ke tempatnya (pilih), memproses sisa posisi secara rekursif (jelajahi), lalu mengembalikan tukaran (urungkan) supaya elemen lain berkesempatan.

cpp 
// Backtracking pola pilih-jelajahi-urungkan: semua permutasi {1, 2, 3}.
#include <iostream>
#include <utility>
#include <vector>

void permutasi(std::vector<int>& data, int mulai, long long& jumlah) {
    if (mulai == static_cast<int>(data.size())) {  // basis: penuh
        ++jumlah;
        for (std::size_t i = 0; i < data.size(); ++i) {
            if (i > 0) std::cout << ' ';
            std::cout << data[i];
        }
        std::cout << '\n';
        return;
    }
    for (int i = mulai; i < static_cast<int>(data.size()); ++i) {
        std::swap(data[mulai], data[i]);          // 1. PILIH kandidat
        permutasi(data, mulai + 1, jumlah);       // 2. JELAJAHI sisa posisi
        std::swap(data[mulai], data[i]);          // 3. URUNGKAN pilihan
    }
}

int main() {
    std::vector<int> data = {1, 2, 3};
    long long jumlah = 0;
    permutasi(data, 0, jumlah);
    std::cout << "Total: " << jumlah << " permutasi\n";
    return 0;
}

Output yang Dihasilkan:

text 
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
Total: 6 permutasi

Bedah baris penting:

  1. Baris 7-15 (basis rekursi): mulai == data.size() berarti semua posisi terisi — cetak satu permutasi dan hitung.
  2. Baris 17 (PILIH): swap menaruh kandidat i di posisi mulai; elemen sebelum mulai sudah final.
  3. Baris 18 (JELAJAHI): rekursi mengerjakan sisa posisi; pemanggilan bertingkat membentuk tree keputusan.
  4. Baris 19 (URUNGKAN): swap dibalik persis; tanpa baris ini, isi vector bisa campur dan permutasi berikutnya jadi salah.
  5. Baris 24-26: titik awal {1, 2, 3} dan penghitung total — enam baris output, sesuai 3! = 6.

Satu detail yang menarik dari output: urutan hasilnya bukan urutan kamus yang sempurna. Dua baris terakhir adalah 3 2 1 lalu 3 1 2 — tertukar, karena mekanisme swap menaruh kandidat ke posisi depan, bukan menyalin daftar kandidat yang tersisa. Bila urutan leksikografis penting, urutkan hasil atau gunakan pendekatan “pilih dari daftar kandidat tersisa”. Struktur tree keputusannya tetap sama.

N-Queens 4x4: Pemangkasan Cabang #

Permutasi menjelajah semua kemungkinan tanpa memeriksa apa pun di tengah jalan. Kekuatan backtracking yang sesungguhnya muncul saat kita menambahkan pemeriksaan yang memangkas cabang sejak dini. Masalah N-Queens menempatkan N ratu di papan NxN tanpa saling menyerang — dua ratu tidak boleh satu baris, satu kolom, atau satu diagonal. Kita menempatkan satu ratu per baris, sehingga yang perlu diperiksa hanya kolom dan dua diagonal:

cpp 
// N-Queens 4x4: backtracking dengan pemeriksaan aman kolom dan diagonal.
#include <iostream>
#include <vector>

const int N = 4;

// Aman bila tidak ada ratu lain pada kolom dan diagonal yang sama.
bool aman(const std::vector<int>& posisi, int baris, int kolom) {
    for (int b = 0; b < baris; ++b) {
        if (posisi[b] == kolom) return false;                        // satu kolom
        if (baris - b == (kolom - posisi[b] > 0 ? kolom - posisi[b]
                                                : posisi[b] - kolom)) {
            return false;                                            // dua diagonal
        }
    }
    return true;
}

void solusi(const std::vector<int>& posisi, int& jumlah) {
    ++jumlah;
    std::cout << "Solusi " << jumlah << ": ";
    for (int b = 0; b < N; ++b) {
        if (b > 0) std::cout << ' ';
        std::cout << posisi[b];
    }
    std::cout << '\n';
    for (int b = 0; b < N; ++b) {
        for (int k = 0; k < N; ++k) {
            if (k > 0) std::cout << ' ';
            std::cout << (posisi[b] == k ? 'Q' : '.');
        }
        std::cout << '\n';
    }
    std::cout << '\n';
}

void cari(std::vector<int>& posisi, int baris, int& jumlah) {
    if (baris == N) {                 // semua baris terisi: catat solusi
        solusi(posisi, jumlah);
        return;
    }
    for (int kolom = 0; kolom < N; ++kolom) {
        if (aman(posisi, baris, kolom)) {
            posisi[baris] = kolom;    // 1. PILIH kolom untuk baris ini
            cari(posisi, baris + 1, jumlah);  // 2. JELAJAHI baris berikut
            posisi[baris] = -1;       // 3. URUNGKAN pilihan
        }
    }
}

int main() {
    std::vector<int> posisi(N, -1);
    int jumlah = 0;
    cari(posisi, 0, jumlah);
    std::cout << "Total solusi 4x4: " << jumlah << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
Solusi 1: 1 3 0 2
. Q . .
. . . Q
Q . . .
. . Q .

Solusi 2: 2 0 3 1
. . Q .
Q . . .
. . . Q
. Q . .

Total solusi 4x4: 2

Bedah baris penting:

  1. Baris 8-17 (aman): posisi[b] == kolom menolak benturan kolom; baris - b == |kolom - posisi[b]| menolak kedua diagonal sekaligus — selisih baris sama dengan selisih kolom berarti satu garis diagonal.
  2. Baris 19-35 (solusi): solusi dicetak dua kali — sebagai deret kolom per baris dan sebagai papan; memudahkan verifikasi manual.
  3. Baris 37-49 (cari): pola tiga langkah yang sama; posisi[baris] = -1 setelah kembali menandai baris itu kosong lagi.
  4. Baris 38-40: basis — keempat baris terisi berarti konfigurasi ini sah, catat dan tampilkan.
  5. Baris 52-55: papan 4x4 menghasilkan tepat dua solusi: 1 3 0 2 dan 2 0 3 1 — saling cermin.

Angka pembandingnya mengesankan: tanpa pemeriksaan, ada 4^4 = 256 cara menempatkan empat ratu; dengan batasan kolom saja tersisa 4! = 24; pemeriksaan diagonal memangkas semuanya sampai tinggal 2 solusi dan banyak cabang buntu yang tidak pernah dijelajahi sama sekali. Backtracking pada dasarnya adalah pencarian menyeluruh yang hanya memasuki cabang yang masih punya harapan.

Kapan Backtracking Alat yang Tepat #

Backtracking adalah pilihan alami ketika solusi bertahap dibangun langkah demi langkah dan setiap langkah bisa divalidasi: puzzle seperti sudoku, pencarian jalur di labirin, pembangkitan kombinasi, dan pemenuhan kendala (constraint satisfaction). Biayanya tumbuh eksponensial pada kasus terburuk — jumlah cabang bisa bern faktorial — sehingga kualitas pemeriksaan aman lebih menentukan daripada kecepatan loop. Dua trik umum: pangkas sedini mungkin (pemeriksaan per langkah, bukan di akhir), dan urutkan kandidat supaya cabang menolak lebih cepat.

Menjelajah semua kemungkinan adalah satu ekstrem. Ekstrem lainnya adalah tidak menjelajah sama sekali: langsung mengambil pilihan yang tampak paling menguntungkan dan tidak pernah menoleh ke belakang. Itulah algoritma greedy — topik chapter berikutnya, lengkap dengan bukti kapan ia benar dan contoh nyata kapan ia gagal.

Rujukan resmi: std::swap dan std::vector .