Backtracking în plan — problema damelor

Backtracking pe tablă: o decizie per linie

La problema damelor ai o tablă n × n și vrei să așezi n dame astfel încât nicio damă să nu atace alta. O damă atacă pe linie, pe coloană și pe ambele diagonale. Cheia care transformă problema dintr-una imposibilă într-una rezolvabilă e simplă: pui exact o damă pe fiecare linie.

Așa, „linia” devine pasul recursiv: funcția rezolva(linie) decide unde merge dama de pe linia curentă, apoi cheamă rezolva(linie + 1). Pe linie nu mai pot exista doi atacatori — deci rămâne să verifici doar coloana și cele două diagonale.

Pentru fiecare linie încerci, pe rând, fiecare coloană. Schema este aceeași „alege-recursie-dezalege” din capitol, dar acum starea pe care o marchezi este tabla:

• alegi: pui dama pe (linie, col) și marchezi coloana și diagonalele ca ocupate;
• recursie: cobori cu rezolva(linie + 1) — subarborele respectă dama tocmai pusă;
• dezalegi: dezmarchezi coloana și diagonalele, ca tabla să redevină curată pentru următoarea coloană testată.

Marcarea o ții în trei vectori de tip bool: coloana[], diag1[] și diag2[]. O coloană e liberă dacă toate trei sunt false pe pozițiile corespunzătoare.

De ce diagonalele se identifică prin i+j și i-j

Verificarea coloanei e ușoară: coloana[j]. Diagonalele par grele, dar au o proprietate elegantă.

Pe diagonala „/” (de la dreapta-sus spre stânga-jos), toate câmpurile au aceeași sumă i + j. Verifică: (0,2), (1,1), (2,0) au toate suma 2. Deci o diagonală „/” întreagă se identifică printr-un singur număr: i + j, care merge de la 0 la 2n - 2.

Pe diagonala „\” (de la stânga-sus spre dreapta-jos), toate câmpurile au aceeași diferență i - j. Verifică: (0,0), (1,1), (2,2) au toate diferența 0. Problema e că i - j poate fi negativ (de la -(n-1) la n-1), iar indecșii de vector trebuie să fie pozitivi. Soluția: adaugi un offset și folosești i - j + n, care cade frumos în intervalul 1 .. 2n - 1.

Așa, o damă pe (i, j) marchează exact o coloană și exact câte o celulă în fiecare vector de diagonale — verificare în O(1), fără să parcurgi tabla.

Exemplu pas cu pas pe tablă mică (4 dame)

Mergem pe n = 4. Notăm o damă cu D și punem una pe fiecare linie.

Pe linia 0 încercăm coloana 0. Marcăm coloana[0], diag1[0+0], diag2[0-0+n].

D . . .     linia 0: dama pe coloana 0
. . . .
. . . .
. . . .

Pe linia 1, coloanele 0 și 1 sunt atacate (coloana 0 ocupată, iar (1,1) e pe diagonala „\” a damei). Prima coloană liberă e 2:

D . . .
. . D .     linia 1: dama pe coloana 2
. . . .
. . . .

Pe linia 2, coloanele libere de coloană/diagonale ne lasă doar coloana... niciuna care să nu fie atacată mai jos. Încercăm 1? E pe diagonala „/” a damei de pe (1,2) (suma 3 = 3). Singura rămasă e o fundătură:

D . . .
. . D .
. . . ?     linia 2: nicio coloana nu duce la solutie

Te blochezi: niciun loc valid pe linia 3. Atunci dai înapoi (backtrack): dezmarchezi dama de pe linia 1, o muți de pe coloana 2 mai departe. Nu mai ai coloane libere pe linia 1 → dai înapoi și pe linia 0, muți prima damă pe coloana 1:

. D . .
. . . D
D . . .
. . D .     solutie completa pentru n = 4

Asta e prima dintre cele două soluții pentru n = 4 (cealaltă e oglinda ei). Esența: la fiecare „blocaj”, dezmarcarea readuce tabla exact cum era înainte de alegerea greșită.

Implementare C++

Funcția rezolva(linie) încearcă toate coloanele de pe linia curentă; pentru fiecare coloană validă marchează starea, recursivează și apoi dezmarchează.

#include <iostream>
using namespace std;

const int N = 4;        // dimensiunea tablei

bool coloana[N];        // coloana[j] = true daca pe coloana j e o dama
bool diag1[2 * N];      // diagonala "/" indexata prin i + j
bool diag2[2 * N];      // diagonala "\" indexata prin i - j + N

int pozitie[N];         // pozitie[i] = coloana damei de pe linia i
int solutii = 0;

void afiseaza() {
    cout << "solutia " << ++solutii << ":";
    for (int i = 0; i < N; i++) cout << " (" << i << "," << pozitie[i] << ")";
    cout << "\n";
}

void rezolva(int linie) {
    if (linie == N) {           // caz de baza: am asezat o dama pe fiecare linie
        afiseaza();
        return;
    }
    for (int col = 0; col < N; col++) {
        // sar peste coloanele atacate de o dama deja pusa
        if (coloana[col] || diag1[linie + col] || diag2[linie - col + N]) continue;

        // ALEG: pun dama si marchez starea pe tabla
        pozitie[linie] = col;
        coloana[col] = diag1[linie + col] = diag2[linie - col + N] = true;

        rezolva(linie + 1);     // RECURSIE: cobor pe linia urmatoare

        // DEZALEG: scot dama si dezmarchez, tabla redevine curata
        coloana[col] = diag1[linie + col] = diag2[linie - col + N] = false;
    }
}

int main() {
    rezolva(0);                 // incep cu prima linie
    cout << "total: " << solutii << " solutii\n";
    return 0;
}
// pentru N = 4 -> 2 solutii

La rulare obții cele două soluții și linia total: 2 solutii. Schimbi N în 8 și funcția raportează cele 92 de soluții ale tablei clasice de șah, fără nicio altă modificare.

Complexitate

Naiv, ai n opțiuni pentru fiecare dintre cele n linii: O(n^n) aranjamente. Constrângerile taie masiv acest spațiu: imediat ce o coloană sau o diagonală e ocupată, ramura respectivă e abandonată înainte de a coborî mai jos.

Backtrackingul rămâne exponențial în cel mai rău caz, dar tăierea timpurie e tot ce îl face folositor. Vezi lecția despre tăierea ramurilor pentru cum „atragi” abandonarea cât mai sus în arbore.

O singură linie a tablei, cu o damă pe coloana 2 și coloanele atacate marcate:

Recapitulare

• La damele n × n tratezi fiecare linie ca pas recursiv (o damă per linie), apoi încerci coloanele și aplici schema „alege-recursie-dezalege” cu starea ținută pe tablă.
• Coloana se verifică prin coloana[j], iar diagonalele prin diag1[i + j] și diag2[i - j + N] (offset N ca indexul să rămână pozitiv).
• Marchezi înainte de recursie, dezmarchezi după — altfel tabla rămâne murdară; cu tăierea pe coloane/diagonale, N = 4 dă 2 soluții, iar N = 8 dă 92.

DONE backtracking-in-plan | viz: niciunul | mistakebox: 4