BKT Hub — N-Regine

♟ Ce este problema?

Trebuie să plasăm N regine pe o tablă de șah N×N astfel încât nicio regină să nu fie atacată de alta.

O regină atacă toate celulele de pe aceeași linie, aceeași coloană și ambele diagonale.

♛

Celulele atacate de o regină (×)

🔁 Abordarea Backtracking

Plasăm câte o regină pe fiecare rând. Pentru fiecare rând, încercăm fiecare coloană:

✓ Coloana e sigură → plasăm regina, trecem la rândul următor

✗ Coloana are conflict → sărim la coloana următoare

↩ Nicio coloană nu e validă → backtrack la rândul anterior

💻 Cod C++ — N-Regine BKT

💻 Cod C++

#include <iostream> using namespace std; int n, x[20], sol = 0; void INIT(int k) { x[k] = 0; } int EXISTA(int k) { if(x[k] < n) return 1; else return 0; } int VALID(int k) { for(int i = 1; i < k; i++) if(x[i] == x[k] || abs(x[i] - x[k]) == abs(i - k)) return 0; return 1; } int SOLUTIE(int k) { if(k == n) return 1; else return 0; } void TIPAR(int k) { int i; sol++; cout << "Solutia " << sol << ": "; for(i = 1; i <= k; i++) cout << x[i] << " "; cout << endl; } void BCK() { int k = 1; INIT(k); while(k > 0) if(EXISTA(k)) { x[k]++; if(VALID(k)) { if(SOLUTIE(k)) TIPAR(k); else { k++; INIT(k); } } } else k--; } int main() { cout << "Numarul de regine: "; cin >> n; BCK(); cout << "S-au generat " << sol << " solutii." << endl; return 0; }

Problema N-Reginelor

♟ Ce este problema?

🔁 Abordarea Backtracking

💻 Cod C++ — N-Regine BKT