Problema celor N regine
Cum așezi 8 regine pe o tablă de șah astfel încât nicio regină să nu atace alta? Regina atacă pe rând, pe coloană și pe ambele diagonale. Este problema-emblemă a backtracking-ului: pui câte o regină pe fiecare rând, verifici conflictele în O(1) cu trei set-uri, iar când te blochezi te întorci și muți regina anterioară.
Problema
Pe o tablă n × n trebuie puse n regine fără ca două să se atace. Pentru n = 4 există 2 soluții, iată una (Q = regină):
tabla = ['.Q..', '...Q', 'Q...', '..Q.']
for rand in tabla:
print(rand) Scrie funcțiile numar_solutii(n) (câte așezări valide există) și prima_tabla(n) (prima soluție găsită, ca listă de texte cu . și Q), cu backtracking rând cu rând și set-uri pentru coloane și cele două diagonale (r - c, r + c).
- În backtrack(r): dacă r == n ai o soluție; altfel încerci fiecare coloană liberă.
- Adaugi în cele trei set-uri, mergi la r + 1, apoi scoți din set-uri.
- prima_tabla se oprește la prima soluție. Trebuie să apară: 4 2, 5 10, 6 4, 8 92, apoi tabla .Q.. / ...Q / Q... / ..Q.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Recursivitate, backtracking, sortare și căutare binară.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan