Belajar Algoritm - Backtracking

#Pendahuluan

Setelah di episode 10 kita membahas Sliding Window & Two Pointer untuk masalah array linear, pada episode ini kita masuk ke backtracking — teknik yang mengeksplorasi semua kemungkinan solusi secara sistematis. Backtracking seperti DFS pada pohon keputusan: kalian membuat pilihan, mengeksplorasi konsekuensinya, lalu mundur (backtrack) jika pilihan tersebut tidak mengarah ke solusi.

Backtracking menjadi powerful ketika dikombinasikan dengan pruning — memotong cabang pohon yang sudah pasti tidak menghasilkan solusi. Tanpa pruning, backtracking hanyalah brute force. Dengan pruning, ia bisa menyelesaikan masalah yang brute force-nya membutuhkan waktu eksponensial menjadi jauh lebih cepat.

#Pola Backtracking

Setiap backtracking mengikuti tiga langkah:

Pilih: buat satu keputusan (tempatkan elemen, pilih angka, isi sel).
Eksplorasi: rekursif lanjutkan dengan state yang sudah diubah.
Undo: kembalikan state ke kondisi sebelum pilihan (backtrack).

text

         pilih A
          /     \
    eksplorasi  undo A
    /            \
pilih B         pilih C
  /                \
eksplorasi       eksplorasi

#N-Queens

N-Queens menempatkan N ratu di papan N×N sehingga tidak ada dua ratu yang saling menyerang (sama baris, kolom, atau diagonal).

python

def solve_n_queens(n):
    solutions = []
    
    def backtrack(row, cols, diag1, diag2, board):
        if row == n:
            solutions.append(["".join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue  # pruning: posisi ini attacked
            # Pilih
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            board[row][col] = 'Q'
            # Eksplorasi
            backtrack(row + 1, cols, diag1, diag2, board)
            # Undo
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)
            board[row][col] = '.'
    
    backtrack(0, set(), set(), set(), [['.' for _ in range(n)] for _ in range(n)])
    return solutions
 
# 4×4: 2 solusi, 8×8: 92 solusi, 12×12: 14,200 solusi

Pruning kunci: jika posisi sudah di-attack, skip (jangan coba tempatkan ratu). Ini memotong sebagian besar cabang pohon.

#Sudoku Solver

Sudoku solver mengisi papan 9×9 sehingga setiap baris, kolom, dan box 3×3 mengandung semua angka 1-9.

python

def solve_sudoku(board):
    def is_valid(row, col, num):
        for i in range(9):
            if board[row][i] == num or board[i][col] == num:
                return False
        box_row, box_col = 3 * (row // 3), 3 * (col // 3)
        for i in range(box_row, box_row + 3):
            for j in range(box_col, box_col + 3):
                if board[i][j] == num:
                    return False
        return True
    
    def backtrack():
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for num in '123456789':
                        if is_valid(i, j, num):
                            board[i][j] = num
                            if backtrack():
                                return True
                            board[i][j] = '.'  # undo
                    return False  # tidak ada angka valid
        return True  # semua terisi
    
    backtrack()

#Permutasi & Kombinasi

Generate semua permutasi dari array:

python

def permutations(nums):
    result = []
    
    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])
            return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]  # pilih
            backtrack(start + 1)  # eksplorasi
            nums[start], nums[i] = nums[i], nums[start]  # undo
    
    backtrack(0)
    return result

Generate semua kombinasi (tanpa pengulangan urutan):

python

def combinations(nums, k):
    result = []
    
    def backtrack(start, current):
        if len(current) == k:
            result.append(current[:])
            return
        for i in range(start, len(nums)):
            current.append(nums[i])  # pilih
            backtrack(i + 1, current)  # eksplorasi (i+1, bukan i)
            current.pop()  # undo
    
    backtrack(0, [])
    return result

Tip

Perbedaan permutasi vs kombinasi: permutasi memanggil backtrack(start) (bisa menggunakan elemen yang sama), kombinasi memanggil backtrack(i + 1) (setiap elemen hanya dipakai sekali). Perhatikan parameter start — ini yang membedakan backtracking dari brute force tanpa urutan.

#Praktik

Implementasi N-Queens solver dengan pruning — cetak jumlah solusi untuk papan 4×4 hingga 12×12.
Implementasi Sudoku solver — uji dengan puzzle nyata.
Generate semua permutasi dan kombinasi — verifikasi jumlah hasil.

Masalah	Jumlah Solusi (N=8)
N-Queens 8×8	92
N-Queens 12×12	14.200
Permutasi 8 elemen	40.320
Kombinasi 8 ambil 4	70

#Penutup

Pada episode 11 ini, kalian telah memahami:

Pola backtracking: pilih → eksplorasi → undo, dengan pruning untuk efisiensi.
N-Queens: tempatkan ratu baris per baris, skip posisi yang attacked.
Sudoku solver: isi sel per sel, backtrack jika tidak ada angka valid.
Permutasi & kombinasi: modifikasi parameter start untuk membedakan keduanya.

Di episode 12 selanjutnya kita akan membahas Bit Manipulation Tricks — operator bitwise, bit shifting, bitmasking untuk subset enumeration, dan trik-trik efisien yang sering muncul di competitive programming. Sampai jumpa di episode 12!