Permutări: generează toate aranjamentele elementelor unei liste. La fiecare poziție, încerci fiecare element care nu e deja folosit.
Problema reginelor: plasează n regine pe o tablă n×n astfel încât nicio două să nu se atace (aceeași linie, coloană sau diagonală).
python.py
def regine(n):
sol = []
def valid(lin, col):
for i in range(lin):
if sol[i] == col or abs(sol[i] - col) == lin - i:
return False
return True
def bk(lin):
if lin == n:
print(sol); return
for col in range(n):
if valid(lin, col):
sol.append(col); bk(lin + 1); sol.pop()
bk(0)
Nu uita pasul de revenire
La fiecare apel recursiv din backtracking — la permutări sau la problema reginelor — trebuie să anulezi alegerea făcută înainte de a încerca următoarea variantă: sol.pop() după bk(lin + 1), sau marcarea unui element ca nefolosit după ce revii dintr-un apel pentru permutări. Dacă omiți acest pas, starea rămâne "murdară" de la o ramură la alta, iar soluțiile generate vor fi greșite sau incomplete.