Backtracking menyusun solusi dengan menambahkan pilihan satu per satu, lalu membatalkan pilihan terakhir ketika jalan buntu. Panduan langkah demi langkah menyusun algoritma backtracking ini menunjukkan struktur rekursif, contoh N-Queens, dan cara mengujinya. Cocok untuk kamu yang sudah paham rekursi dasar dan ingin menerapkannya pada masalah pencarian solusi.
Apa Itu Backtracking dan Kapan Dipakai
Backtracking bekerja seperti mencoba labirin: kamu maju selangkah, jika mentok kamu kembali dan mencoba jalur lain. Dalam kode, proses ini dijalankan secara rekursif. Setiap pemanggilan fungsi mewakili satu keputusan yang sudah diambil. Ketika kondisi tidak valid, fungsi berhenti dan mengembalikan kendali ke pemanggil sebelumnya untuk mencoba opsi berikutnya.
Teknik ini berguna untuk masalah yang meminta semua kemungkinan solusi atau satu solusi yang memenuhi batasan, seperti teka-teki N-Queens, sudoku, pencarian jalur di graf kecil, dan penyusunan kombinasi. Jika masalahnya hanya butuh solusi optimal dengan subproblem yang tumpang tindih, pemrograman dinamis lebih tepat. Backtracking unggul saat ruang solusi bercabang dan kita bisa memangkas cabang yang jelas salah.
Langkah 1: Definisikan Ruang Solusi dan Batasan
Sebelum menulis kode, tentukan apa yang dianggap solusi dan apa saja aturan yang harus dipenuhi. Untuk N-Queens, solusi adalah susunan N ratu di papan N×N sehingga tidak ada dua ratu yang saling menyerang. Batasannya: satu ratu per baris, satu per kolom, dan tidak boleh berada di diagonal yang sama.
Tulis batasan dalam bentuk yang bisa diperiksa dengan cepat. Pada N-Queens, kita bisa menyimpan posisi ratu per baris dalam array satu dimensi. Pemeriksaan konflik kolom dan diagonal menjadi operasi indeks sederhana, bukan perulangan dua dimensi.
Langkah 2: Tentukan Struktur Rekursif
Fungsi backtracking biasanya menerima state saat ini dan indeks keputusan. Di dalamnya ada tiga bagian: cek apakah state sudah lengkap, iterasi semua opsi yang mungkin, dan panggil fungsi lagi setelah memilih satu opsi. Setelah pemanggilan selesai, batalkan pilihan itu sebelum lanjut ke opsi berikutnya.
Pola umumnya seperti ini:
function backtrack(state, kandidat):
if state adalah solusi lengkap:
simpan solusi
return
for setiap opsi dalam kandidat:
if opsi valid untuk state:
tambahkan opsi ke state
backtrack(state, kandidat berikutnya)
hapus opsi dari state
Baris hapus opsi dari state adalah inti backtracking. Tanpa langkah pembatalan, state akan terus menumpuk dan fungsi tidak bisa mencoba cabang lain.
Langkah 3: Rancang Fungsi Pemeriksa Validitas
Fungsi ini menentukan seberapa cepat algoritma berjalan. Buat pemeriksaan yang hanya melihat state relevan, bukan seluruh papan. Untuk N-Queens, saat menempatkan ratu di baris r dan kolom c, cukup periksa ratu yang sudah ditempatkan di baris 0 sampai r-1. Cek apakah ada yang menempati kolom c atau berada di diagonal yang sama.
Dua ratu berada di diagonal yang sama jika selisih barisnya sama dengan selisih kolomnya. Jadi pemeriksaan diagonal cukup membandingkan abs(r - i) == abs(c - kolom[i]). Dengan cara ini, validasi berjalan dalam waktu linear terhadap jumlah ratu yang sudah terpasang, bukan kuadrat dari ukuran papan.
Langkah 4: Implementasikan Backtracking untuk N-Queens
Berikut implementasi dalam JavaScript. Kamu bisa memindahkannya ke Python atau bahasa lain dengan logika yang sama.
function solveNQueens(n) {
const hasil = [];
const kolom = Array(n).fill(-1);
function valid(baris, col) {
for (let i = 0; i < baris; i++) {
if (kolom[i] === col) return false;
if (Math.abs(baris - i) === Math.abs(col - kolom[i])) return false;
}
return true;
}
function backtrack(baris) {
if (baris === n) {
hasil.push([...kolom]);
return;
}
for (let col = 0; col < n; col++) {
if (valid(baris, col)) {
kolom[baris] = col;
backtrack(baris + 1);
kolom[baris] = -1;
}
}
}
backtrack(0);
return hasil;
}
Fungsi backtrack dipanggil untuk setiap baris. Jika baris sudah mencapai n, artinya semua ratu berhasil ditempatkan dan solusi disimpan. Jika belum, ia mencoba setiap kolom, memilih yang valid, lalu lanjut ke baris berikutnya. Baris kolom[baris] = -1 mengembalikan state seperti sebelum pilihan dibuat.
Jika kamu baru mulai belajar rekursi, latihan menulis fungsi rekursif sederhana akan memudahkan memahami alur pemanggilan dan pengembalian nilai seperti ini. Lihat panduan menulis algoritma rekursif untuk memperkuat dasar sebelum melanjutkan.
Langkah 5: Uji dengan Kasus Kecil dan Kasus Tepi
Mulai dari n = 1 yang seharusnya menghasilkan satu solusi. Lanjut ke n = 2 dan n = 3 yang tidak punya solusi. Untuk n = 4, seharusnya ada dua solusi. Jika hasilmu berbeda, periksa fungsi valid dan urutan pembatalan state.
Uji juga jumlah solusi untuk n = 8. Jika kode menghasilkan 92 solusi, implementasimu benar. Angka ini bisa kamu cari di literatur, tetapi jangan mengandalkan hafalan; pahami mengapa jumlahnya demikian dengan mencetak papan untuk beberapa solusi pertama.
Saat menguji, pisahkan pencetakan state dari logika inti. Kamu bisa menambahkan parameter debug untuk menampilkan papan setiap kali solusi ditemukan. Teknik mencetak state seperti ini juga berguna saat mendebug kode JavaScript di browser, seperti yang dibahas dalam tips jQuery untuk pemula: debug kode dengan console.
Langkah 6: Tambahkan Pemangkasan (Pruning)
Backtracking naif mencoba semua kolom di setiap baris. Pemangkasan memotong cabang yang sudah pasti tidak menghasilkan solusi. Pada N-Queens, pemeriksaan validitas sudah berfungsi sebagai pemangkasan karena kita tidak pernah menempatkan ratu di posisi yang diserang.
Untuk masalah lain, pruning bisa berupa batas atas nilai, sisa elemen yang tidak cukup, atau kondisi yang mustahil dipenuhi. Contohnya, saat mencari kombinasi angka yang jumlahnya tertentu, jika jumlah saat ini sudah melebihi target, hentikan cabang itu. Semakin awal kamu memangkas, semakin sedikit cabang yang dieksplorasi.
Langkah 7: Analisis Kompleksitas dan Batasan
Waktu tempuh backtracking sulit dinyatakan dalam satu rumus karena sangat bergantung pada pruning. Untuk N-Queens, ruang pencarian teoretis adalah n! jika kita menganggap satu ratu per baris. Pruning mengurangi jumlah itu, tetapi pertumbuhannya tetap eksponensial. Artinya, algoritma ini tidak cocok untuk n yang sangat besar.
Pahami batas praktisnya. Untuk n di bawah 20, backtracking masih bisa berjalan dalam hitungan detik atau menit tergantung implementasi. Jika masalahmu menuntut skala besar, pertimbangkan pendekatan lain atau gunakan heuristik. Mengetahui kapan harus berhenti mengoptimalkan sama pentingnya dengan menulis kode itu sendiri.
Kesalahan yang Sering Terjadi
Kesalahan paling umum adalah lupa membatalkan state setelah rekursi. Akibatnya, pilihan dari cabang sebelumnya tetap tersimpan dan memengaruhi cabang berikutnya. Gejalanya: solusi yang dihasilkan tidak valid atau jumlahnya salah.
Kesalahan kedua, memeriksa validitas terhadap seluruh papan padahal cukup sebagian. Ini membuat kode lambat tanpa alasan. Ketiga, tidak memiliki kondisi berhenti yang jelas, sehingga rekursi berjalan tanpa henti sampai stack overflow. Pastikan setiap cabang menuju ke state yang lebih lengkap dan ada batas kedalaman.
Terakhir, mencampur logika pencarian dengan pencetakan output. Pisahkan keduanya agar mudah diuji dan dimodifikasi. Jika kamu ingin membandingkan dengan teknik pencarian lain, lihat 7 algoritma pencarian yang sering muncul di soal coding interview untuk melihat kapan backtracking lebih tepat daripada BFS atau DFS biasa.
Ringkasan
Menyusun algoritma backtracking dimulai dari definisi ruang solusi dan batasan, lalu struktur rekursif dengan pembatalan state, fungsi validitas yang efisien, dan pengujian pada kasus kecil. Pemangkasan mempercepat eksekusi, tetapi kompleksitasnya tetap eksponensial sehingga perlu tahu batas penerapannya. Latih pola ini pada N-Queens, sudoku, atau kombinasi angka untuk membangun intuisi.
Pertanyaan yang Sering Diajukan
Apa perbedaan backtracking dan rekursi biasa?
Rekursi adalah cara fungsi memanggil dirinya sendiri. Backtracking menggunakan rekursi untuk menjelajahi ruang solusi sambil membatalkan pilihan yang gagal. Jadi backtracking adalah pola penggunaan rekursi, bukan teknik terpisah.
Apakah backtracking selalu lambat?
Tidak selalu. Kecepatannya bergantung pada seberapa efektif pruning memotong cabang. Untuk masalah dengan banyak batasan ketat, backtracking bisa sangat cepat. Untuk ruang solusi yang hampir semua cabang valid, waktu tempuhnya bisa eksponensial.
Bagaimana cara belajar backtracking untuk pemula?
Mulai dari masalah kecil seperti menghasilkan semua permutasi atau kombinasi, lalu naik ke N-Queens. Tulis pseudocode sebelum kode, dan telusuri manual untuk input kecil. Latihan rutin dengan variasi soal akan membantu mengenali pola state dan pembatalan yang diperlukan.