Backtracking adalah teknik rekursif untuk mengeksplorasi semua kemungkinan solusi secara sistematis. Bila sebuah pilihan tidak mengarah ke solusi, algoritma mundur (backtrack) dan mencoba pilihan lain. Bayangkan Sudoku: kita menebak angka, lanjut mengisi, bila buntu mundur dan ganti angka sebelumnya. Backtracking adalah jantung dari banyak algoritma kombinatorial: N-Queens, Sudoku solver, subset generation, maze solving. Pada Chapter ini kita akan mempelajari kerangka umum backtracking, menerapkannya pada N-Queens, dan melihat sekilas struktur Sudoku solver.

Kerangka Backtracking: Choose, Explore, Unchoose #

Setiap algoritma backtracking memiliki tiga langkah wajib per pemanggilan rekursif:

  1. Choose: pilih satu opsi dari kandidat yang tersedia.
  2. Explore: panggil rekursif dengan opsi tersebut dipasang.
  3. Unchoose: batalkan pilihan (undo) untuk mencoba opsi lain.

Pola pseudocode:

text 
def backtrack(state):
    if is_solution(state):
        record(state)
        return
    for option in candidates(state):
        choose(option)         # modify state
        backtrack(state)       # recurse
        unchoose(option)        # restore state

Kunci sukses backtracking: state harus dapat dimodifikasi dan dipulihkan dengan murah. Untuk vector, ini berarti push_back/pop_back. Untuk array, tetapkan nilai dan reset.

Aturan N-Queens: Solitaire Klasik #

Aturan #

Tempatkan n ratu pada papan catur n × n sehingga tidak ada dua ratu yang saling serang. Dua ratu saling serang bila berada di baris, kolom, atau diagonal yang sama.

Mekanisme: Backtrack per Baris #

Tempatkan ratu satu per satu per baris dari atas ke bawah. Untuk setiap baris, coba setiap kolom:

  1. Choose: letakkan ratu di (row, col).
  2. Explore: rekursi ke baris berikutnya.
  3. Unchoose: hapus ratu dari (row, col) sebelum mencoba kolom lain.

Bila row == n, semua ratu terpasang → catat solusi.

Kode: N-Queens Solver #

cpp 
#include <iostream>
#include <vector>
#include <string>

int g_solutions = 0;

bool aman(const std::vector<int>& pos, int row, int col) {
    for (int r = 0; r < row; ++r) {
        int c = pos[r];
        if (c == col) return false;                       // kolom sama
        int dr = row - r;
        int dc = c - col;
        if (dc < 0) dc = -dc;
        if (dr == dc) return false;                       // diagonal
    }
    return true;
}

void solve_nqueens(std::vector<int>& pos, int row, int n) {
    if (row == n) {
        ++g_solutions;
        std::cout << "solusi " << g_solutions << ": ";
        for (int c : pos) std::cout << c << ' ';
        std::cout << '\n';
        return;
    }
    for (int col = 0; col < n; ++col) {
        if (aman(pos, row, col)) {
            pos[row] = col;            // choose
            solve_nqueens(pos, row + 1, n);  // explore
            // unchoose: pos[row] akan ditimpa di iterasi berikutnya
        }
    }
}

int main() {
    int n = 4;
    std::vector<int> pos(n, -1);
    std::cout << "N-Queens untuk n=" << n << ":\n";
    solve_nqueens(pos, 0, n);
    std::cout << "total solusi: " << g_solutions << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
N-Queens untuk n=4:
solusi 1: 1 3 0 2 
solusi 2: 2 0 3 1 
total solusi: 2
  1. std::vector<int> pos(n, -1): pos[row] = col menyimpan posisi ratu per baris. -1 berarti belum ada ratu.
  2. Fungsi aman: cek apakah ratu di (row, col) aman dari semua ratu di baris 0..row-1. Cek kolom sama (c == col) dan diagonal (|dr| == |dc|).
  3. Baris pos[row] = col;: choose — letakkan ratu di kolom col baris row.
  4. Baris solve_nqueens(pos, row + 1, n);: explore — rekursi ke baris berikutnya.
  5. Tidak ada unchoose eksplisit: pos[row] akan ditimpa di iterasi berikutnya dari loop for. Bila tidak ada iterasi lagi, pos[row] tidak relevan karena pemanggil akan menimpa di level atas.
  6. Hasil 2 solusi: untuk n = 4, ada 2 solusi. Solusi [1, 3, 0, 2] artinya ratu di (0,1), (1,3), (2,0), (3,2).

Sketsa Sudoku Solver #

N-Queens adalah kasus khusus dengan struktur sederhana. Sudoku lebih kompleks: ada constraint awal (angka yang sudah terisi), dan pemilihan sel berikutnya tidak trivial.

Kode: Sketsa Sudoku Solver #

cpp 
#include <iostream>
#include <vector>

bool valid(const std::vector<std::vector<int>>& grid, int r, int c, int num) {
    // Cek baris dan kolom
    for (int i = 0; i < 9; ++i) {
        if (grid[r][i] == num) return false;
        if (grid[i][c] == num) return false;
    }
    // Cek kotak 3x3
    int br = (r / 3) * 3, bc = (c / 3) * 3;
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            if (grid[br + i][bc + j] == num) return false;
    return true;
}

bool solve_sudoku(std::vector<std::vector<int>>& grid) {
    for (int r = 0; r < 9; ++r) {
        for (int c = 0; c < 9; ++c) {
            if (grid[r][c] == 0) {  // sel kosong
                for (int num = 1; num <= 9; ++num) {
                    if (valid(grid, r, c, num)) {
                        grid[r][c] = num;            // choose
                        if (solve_sudoku(grid))      // explore
                            return true;
                        grid[r][c] = 0;              // unchoose
                    }
                }
                return false;  // tidak ada angka valid → backtrack
            }
        }
    }
    return true;  // semua sel terisi → solusi
}

int main() {
    std::vector<std::vector<int>> grid = {
        {5, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}
    };

    if (solve_sudoku(grid)) {
        std::cout << "solusi:\n";
        for (const auto& row : grid) {
            for (int x : row) std::cout << x << ' ';
            std::cout << '\n';
        }
    } else {
        std::cout << "tidak ada solusi\n";
    }
    return 0;
}

Output yang Dihasilkan:

text 
solusi:
5 3 4 6 7 8 9 1 2 
6 7 2 1 9 5 3 4 8 
1 9 8 3 4 2 5 6 7 
8 5 9 7 6 1 4 2 3 
4 2 6 8 5 3 7 9 1 
7 1 3 9 2 4 8 5 6 
9 6 1 5 3 7 2 8 4 
2 8 7 4 1 9 6 3 5 
3 4 5 2 8 6 1 7 9
  1. Fungsi valid: cek apakah angka num dapat ditempatkan di (r, c) tanpa melanggar aturan Sudoku (baris, kolom, kotak 3×3).
  2. Loop dua tingkat: cari sel kosong (grid[r][c] == 0). Bila tidak ada sel kosong, semua terisi → return true.
  3. Baris grid[r][c] = num;: choose — isi dengan angka kandidat.
  4. Baris if (solve_sudoku(grid)) return true;: explore — rekursi untuk mengisi sel berikutnya.
  5. Baris grid[r][c] = 0;: unchoose — kosongkan kembali sebelum mencoba angka lain.
  6. Baris return false;: bila tidak ada angka 1-9 yang valid untuk sel saat ini, backtrack ke pemanggil.
  7. Hasil: Sudoku terisi lengkap dan valid.

State-Space Tree #

Backtracking mengeksplorasi state-space tree: pohon di mana setiap node adalah state parsial, anak-anaknya adalah pilihan yang mungkin, dan daun adalah solusi atau dead-end.

Kunci: algoritma memangkas cabang yang tidak menjanjikan lebih awal. Tanpa pruning, backtracking menjadi exhaustive search — eksponensial penuh.

Pola Umum Backtracking #

Berikut pola umum untuk berbagai soal backtracking:

cpp 
void backtrack(state, params...) {
    if (is_solution(state)) {
        record_solution(state);
        return;
    }
    for (auto& choice : candidates(state)) {
        if (is_valid(choice, state)) {
            apply(choice, state);        // choose
            backtrack(state, params...);  // explore
            undo(choice, state);          // unchoose
        }
    }
}

Empat komponen kunci:

  1. is_solution(state): kondisi terminasi. Bila state adalah solusi lengkap, catat.
  2. candidates(state): daftar pilihan yang mungkin pada state saat ini.
  3. is_valid(choice, state): filter pilihan yang melanggar constraint.
  4. apply/undo: pasang dan pulihkan state. Harus berpasangan simetris.

Ringkasan #

  • Backtracking mengeksplorasi pohon kemungkinan dengan pola choose-explore-unchoose.
  • Tiga langkah wajib: pilih opsi, rekursi, batalkan pilihan.
  • N-Queens: tempatkan ratu per baris, cek konflik kolom/diagonal sebelum rekursi.
  • Sudoku: isi sel kosong dengan angka 1-9, cek aturan baris/kolom/kotak.
  • State-space tree: visualisasi pohon keputusan. Backtracking memangkas cabang tidak valid lebih awal.
  • Tanpa pruning, backtracking = exhaustive search. Pruning efektif mengecilkan state space.