Soal-soal batasan

Pada soal batasan, backtracking tidak lagi menelusuri semua kandidat lalu menyaring jawabannya di akhir. Setiap langkah diperiksa terhadap batasan, dan langkah yang melanggar langsung ditolak sebelum turun lebih dalam. Topik ini mempraktikkan pola itu pada dua soal klasik, N-queens dan sudoku, dalam dua bahasa sekaligus, lalu menutup modul ini dengan daftar soal untuk dipraktikkan.

Pemeriksaan batasan sebagai syarat lanjut#

Perbedaan soal batasan dengan soal pembangkitan murni ada pada gerbang penolakannya. Soal subhimpunan menerima setiap jalur yang tuntas sebagai jawaban, sedangkan soal batasan menolak cabang segera setelah satu batasan dilanggar. Karena penolakan terjadi di bagian atas pohon, pohon pencarian menyusut drastis. Itulah alasan N-queens terjangkau meskipun ruang pencariannya berukuran $n^n$, yaitu satu kolom pilihan untuk setiap baris tanpa pemeriksaan apa pun.

Struktur data pemeriksaan menentukan harga setiap pemeriksaan. Larik boolean atau set yang menandai kolom dan diagonal yang sudah dipakai memeriksa satu kotak dalam waktu $O(1)$, jauh lebih murah daripada memindai seluruh papan pada setiap langkah. Gambar berikut menunjukkan satu solusi N=6 beserta tiga kelompok batasan yang diperiksa pada setiap penempatan:

Ketiga kelompok batasan itu memegang informasi yang sama dengan tanda pakai pada topik permutasi, hanya bentuknya lebih banyak. Mempertahankan informasi ini secara bertahap, yakni menandai saat menempatkan dan melepas saat membatalkan, adalah seluruh kunci efisiensinya. Bentuk pemeriksaan seperti ini juga mudah diterjemahkan antarbahasa karena hanya membutuhkan set atau larik boolean.

N-queens dalam Python#

Tiga set memegang batasannya: kolom untuk kolom yang sudah terisi, diag1 untuk diagonal dengan selisih baris dikurangi kolom, dan diag2 untuk diagonal dengan jumlah baris tambah kolom. Setiap diagonal pada papan memiliki nilai selisih atau jumlah yang tetap, sehingga dua ratu saling menyerang tepat ketika keduanya berbagi satu nilai yang sama. Menempatkan ratu berarti menandai tiga nilai sekaligus, dan membatalkan penempatan berarti melepas ketiganya.

# nqueens.py
# Menghitung jumlah susunan n ratu dengan tiga set batasan.

def hitung_solusi(n):
    # set batasan: kolom, diagonal baris-kolom, dan diagonal baris+kolom
    kolom, diag1, diag2 = set(), set(), set()

    def tempatkan(baris):
        if baris == n:
            return 1   # semua baris terisi, satu susunan sah ditemukan
        total = 0
        for c in range(n):
            if c in kolom or (baris - c) in diag1 or (baris + c) in diag2:
                continue   # kotak diserang ratu lain, batalkan arah ini
            kolom.add(c); diag1.add(baris - c); diag2.add(baris + c)
            total += tempatkan(baris + 1)
            kolom.remove(c); diag1.remove(baris - c); diag2.remove(baris + c)
        return total

    return tempatkan(0)

for n in range(4, 9):
    print(f"N={n}: {hitung_solusi(n)} solusi")

N=4: 2 solusi
N=5: 10 solusi
N=6: 4 solusi
N=7: 40 solusi
N=8: 92 solusi

Angka yang dicetak sudah dikenal luas, dan N=6 memang menghasilkan tepat 4 solusi. Perhatikan bahwa pencacah ini tidak menyimpan papan sama sekali. Tiga set kecil mewakili seluruh keadaan, karena posisi ratu pada baris-baris di atas tidak dibutuhkan lagi selain melalui tanda pakainya. Varian yang perlu mencetak papan menambahkan satu larik kolom ratu per baris dan mencetaknya pada kasus dasar, tanpa mengubah logika penelusurannya.

N=8 adalah ukuran terbesar yang masih nyaman dipakai pada demonstrasi, karena 92 solusinya ditemukan dalam sepersekian detik. Ukuran yang lebih besar tetap selesai cepat pada mesin biasa, tetapi keluarannya tidak lagi berguna untuk dibaca dan hanya angka jumlahnya yang layak dicatat. Batasan ukuran seperti ini sebaiknya ditetapkan sejak awal saat menulis demo backtracking, agar program tidak berjalan lama karena nilai N yang dimasukkan terlalu besar.

N-queens dalam Java#

Terjemahan Java-nya memakai larik boolean alih-alih set, sehingga indeks diagonal harus dipetakan ke rentang larik yang selalu positif. Selisih baris dikurangi kolom berpotensi negatif, maka indeksnya digeser dengan n - 1 sebelum dipakai. Perilaku rekursinya identik dengan versi Python, dan angka yang dicetaknya cocok persis, sesuatu yang layak selalu diperiksa setiap kali satu soal dipecahkan dalam dua bahasa:

public class Nqueens {
    // menghitung jumlah susunan n ratu dengan tiga larik boolean sebagai tanda pakai

    static int n;

    static int tempatkan(int baris, boolean[] kolom, boolean[] d1, boolean[] d2) {
        if (baris == n) {
            // semua baris terisi, satu susunan sah ditemukan
            return 1;
        }
        int total = 0;
        for (int c = 0; c < n; c++) {
            if (kolom[c] || d1[baris - c + n - 1] || d2[baris + c]) {
                continue;   // kotak diserang ratu lain, lewati
            }
            kolom[c] = true;
            d1[baris - c + n - 1] = true;
            d2[baris + c] = true;
            total += tempatkan(baris + 1, kolom, d1, d2);
            kolom[c] = false;
            d1[baris - c + n - 1] = false;
            d2[baris + c] = false;
        }
        return total;
    }

    public static void main(String[] args) {
        for (int b = 4; b <= 8; b++) {
            n = b;
            boolean[] kolom = new boolean[b];
            boolean[] d1 = new boolean[2 * b - 1];
            boolean[] d2 = new boolean[2 * b - 1];
            System.out.println("N=" + b + ": " + tempatkan(0, kolom, d1, d2) + " solusi");
        }
    }
}

N=4: 2 solusi
N=5: 10 solusi
N=6: 4 solusi
N=7: 40 solusi
N=8: 92 solusi

Waktu jalannya masih di bawah dua detik hingga N=8, karena pemeriksaan batasan menyaring hampir seluruh ruang pencarian sebelum sempat dituruni. Bagian yang berbeda dari Python hanya administrasi memorinya, yaitu larik yang dialokasikan sekali per nilai N lalu diubah lewat penandaan dan pembatalan. Pola larik boolean seperti ini dipakai juga oleh pemecah sudoku pada bagian di bawah.

Pemetaan indeks diagonalnya patut dicermati. Rentang selisih baris dikurangi kolom berada pada -(n-1) sampai n-1, sehingga ukuran lariknya 2n-1 dan indeksnya ditambah n-1. Rentang jumlah baris tambah kolom sudah selalu positif, yaitu 0 sampai 2n-2, sehingga pemetaannya langsung tanpa penggeser. Perhitungan rentang kecil seperti ini berguna untuk setiap soal kisi yang memakai larik tanda pakai.

Pemecah sudoku#

Sudoku menambahkan satu bentuk batasan, yaitu kotak 3x3. Sel kosong pertama dicari, fungsi kandidat mengumpulkan angka yang belum muncul pada baris, kolom, dan kotak sel tersebut, lalu setiap kandidat dicoba dengan backtracking yang sudah dikenal. Papan contohnya sengaja diisi dekat penyelesaian, sehingga jalur penyelesaiannya pendek dan mudah diikuti:

# sudoku.py
# Pemecah sudoku dengan backtracking dan kandidat per sel.

def cetak(papan):
    # cetak papan 9x9 dengan pemisah blok 3x3
    for r in range(9):
        if r % 3 == 0 and r > 0:
            print("------+-------+------")
        sel = ["." if papan[r][c] == 0 else str(papan[r][c]) for c in range(9)]
        print(" ".join(sel[:3]) + " | " + " ".join(sel[3:6]) + " | " + " ".join(sel[6:]))

def kandidat(papan, r, c):
    # angka yang belum muncul pada baris, kolom, dan kotak 3x3 sel (r, c)
    terpakai = set(papan[r]) | {papan[i][c] for i in range(9)}
    br, bk = 3 * (r // 3), 3 * (c // 3)
    for i in range(br, br + 3):
        terpakai |= set(papan[i][bk:bk + 3])
    return [a for a in range(1, 10) if a not in terpakai]

def pecahkan(papan):
    # backtracking: isi sel kosong pertama, mundur bila macet
    for r in range(9):
        for c in range(9):
            if papan[r][c] == 0:
                for a in kandidat(papan, r, c):
                    papan[r][c] = a
                    if pecahkan(papan):
                        return True
                    papan[r][c] = 0   # batalkan pilihan bila cabang gagal
                return False   # tidak ada kandidat yang sah, sel ini punya kesalahan di atasnya
    return True   # tidak ada sel kosong tersisa

papan = [
    [5, 3, 0, 6, 7, 8, 9, 1, 2],
    [6, 7, 2, 0, 9, 5, 3, 4, 8],
    [1, 9, 8, 3, 4, 2, 5, 0, 7],
    [8, 5, 9, 7, 0, 1, 4, 2, 3],
    [4, 2, 6, 8, 5, 3, 0, 9, 1],
    [7, 1, 3, 9, 2, 4, 8, 5, 6],
    [9, 6, 0, 5, 3, 7, 2, 8, 4],
    [2, 0, 7, 4, 1, 9, 6, 3, 5],
    [3, 4, 5, 2, 8, 6, 1, 7, 0],
]

if pecahkan(papan):
    cetak(papan)
else:
    print("tidak ada 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

Fungsi kandidat adalah seluruh logika batasannya, sedangkan sisanya murni templat pilih, jelajahi, batalkan pilihan. Fungsi pecahkan mengembalikan boolean agar cabang yang gagal dapat diketahui tanpa memeriksa papan, karena nilai False berarti satu sel buntu sehingga pemanggil di atasnya mencoba kandidat lain. Perhatikan baris papan[r][c] = 0 yang mengembalikan papan ke keadaan semula, padanan jalur.pop() pada templat dasar. Tanpa pembatalan itu, papan membawa sisa pilihan cabang yang gagal dan solusi yang dicetak menjadi tidak konsisten.

Pemilih sel kosong pertama sudah cukup cepat untuk papan dengan banyak petunjuk seperti contoh di atas. Papan yang jarang berpetunjuk membutuhkan pemilihan sel dengan kandidat paling sedikit agar pohonnya tetap ramping, dan itulah pengoptimalan pertama yang biasanya ditambahkan. Contoh di atas selesai tanpa mundur yang dalam, sehingga jejaknya masih dapat diikuti langsung dari keluaran.

Soal untuk dipraktikkan#

Soal-soal berikut memakai templat pilih, jelajahi, batalkan pilihan beserta indeks mulai, tanda pakai, dan pemangkasan yang sudah dibahas pada modul ini. Urutannya naik mengikuti kesulitan yang lazim. Kerjakan pada masukan kecil terlebih dahulu, pastikan keluarannya terurut dan lengkap, baru naik ke ukuran yang lebih besar:

• Subsets : latihan templat subhimpunan yang paling polos, tanpa duplikat dan tanpa batasan tambahan.
• Permutations : melatih tanda pakai pakai[] pada soal yang jumlah jawabannya $n!$.
• Combinations : menguji parameter indeks mulai agar satu kombinasi tidak dihitung dua kali.
• Combination Sum : memasang pemangkasan pada sisa target dengan elemen yang boleh dipakai ulang.
• Subsets II : menambahkan penanganan elemen kembar pada tingkat yang sama di atas templat subhimpunan.
• Word Search : backtracking pada kisi huruf dengan tanda pakai per sel dan pembatalannya.
• N-Queens : mengubah penghitung solusi menjadi pencatat papan pada soal batasan yang sudah dikenal.
• Sudoku Solver : versi lengkap pemecah sudoku dengan tiga batasan yang diperiksa sekaligus.

Ringkasan#

• Soal batasan menolak cabang segera setelah batasan dilanggar, sehingga pohon pencarian menyusut jauh sebelum jawaban tercapai.
• Tiga set atau larik boolean pada N-queens, yaitu kolom dan dua arah diagonal, memeriksa satu kotak dalam waktu $O(1)$.
• Versi Python dan Java menghasilkan angka yang sama persis, dengan 4 solusi pada N=6 dan 92 pada N=8.
• Pemecah sudoku memisahkan logika batasan pada fungsi kandidat, sedangkan kerangkanya tetap templat pilih, jelajahi, batalkan pilihan.

Referensi#

• Eight queens puzzle — Wikipedia — Daftar jumlah solusi N-queens per ukuran papan yang dipakai memverifikasi keluaran kode.
• Sudoku solving algorithms — Wikipedia — Tinjauan pendekatan penyelesaian sudoku termasuk varian backtracking yang dipakai di sini.