Materi
Runut balik (backtracking) mencari semua solusi, atau satu solusi, dengan membangun jawaban sebagian demi sebagian. Di setiap langkah satu pilihan ditambahkan, lalu diperiksa. Bila jawaban sebagian masih mungkin diteruskan, pencarian maju ke langkah berikutnya. Bila tidak, pilihan terakhir dibatalkan dan pilihan lain dicoba. Bentuk ini paling alami ditulis rekursif: satu panggilan untuk satu langkah.
Bedanya dengan pencarian menyeluruh ada di pemangkasan. itertools.combinations membangkitkan semua kombinasi lalu menyaringnya di akhir. Runut balik memeriksa sejak awal dan membuang seluruh cabang begitu satu jawaban sebagian sudah melanggar syarat. Pada soal yang syaratnya ketat, seperti menempatkan ratu catur yang tidak saling menyerang, sebagian besar cabang terbuang di tingkat atas dan tidak pernah dibangkitkan.
def susun(huruf, jalur, hasil):
if len(jalur) == len(huruf):
hasil.append("".join(jalur))
return
for h in huruf:
if h not in jalur: # pemeriksaan sebelum maju
jalur.append(h) # coba
susun(huruf, jalur, hasil)
jalur.pop() # mundur
hasil = []
susun("abc", [], hasil) # ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']Pola tiga barisnya selalu sama: tambahkan pilihan ke keadaan, panggil langkah berikutnya, lalu kembalikan keadaan seperti semula. Keadaan bersama seperti list jalur atau himpunan kolom terpakai dipakai bergantian oleh semua cabang, sehingga lupa mengembalikannya membuat cabang berikutnya mewarisi pilihan cabang sebelumnya.
