Problema N-Queens folosind Backtracking în Java/C++
Cuprins
Introducere
Problema N-Queens este o problemă clasică de backtracking în care scopul este de a plasa N regine pe o tablă de șah de NxN, astfel încât acestea să nu se atace reciproc. O regină poate ataca alte piese pe aceeași linie, coloană sau diagonală.
Problema N-Queens a fost studiată de-a lungul secolelor de matematicieni și informaticieni. Există mai multe abordări pentru rezolvarea acestei probleme, dar una dintre cele mai comune este backtracking-ul.
Backtracking
Backtracking-ul este o tehnică de rezolvare a problemelor care implică construirea unei soluții candidat, verificarea dacă soluția este validă și, dacă nu, revenirea la o stare anterioară și încercarea unei soluții alternative.
În cazul problemei N-Queens, putem construi o soluție candidat plasând reginele pe tablă rând cu rând. După plasarea unei regine pe un rând, verificăm dacă este atacată de oricare dintre reginele plasate anterior. Dacă este atacată, revenim la starea anterioară și încercăm o altă plasare a reginei.
Algoritmul N-Queens
Algoritmul în Java:
java
public class NQueens {
private int[][] board;
private int size;
public NQueens(int size) {
this.board = new int[size][size];
this.size = size;
}
public boolean solve() {
return solve(0);
}
private boolean solve(int row) {
if (row == size) {
return true;
}
for (int col = 0; col < size; col++) {
if (isSafe(row, col)) {
board[row][col] = 1;
if (solve(row + 1)) {
return true;
} else {
board[row][col] = 0;
}
}
}
return false;
}
private boolean isSafe(int row, int col) {
// Verifică linii
for (int i = 0; i < row; i++) {
if (board[i][col] == 1) {
return false;
}
}
// Verifică diagonale
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 1) {
return false;
}
}
for (int i = row, j = col; i >= 0 && j < size; i--, j++) {
if (board[i][j] == 1) {
return false;
}
}
return true;
}
public static void main(String[] args) {
NQueens nQueens = new NQueens(4);
nQueens.solve();
nQueens.printSolution();
}
private void printSolution() {
for (int[] row : board) {
for (int cell : row) {
System.out.print(cell + " ");
}
System.out.println();
}
}
}
Algoritmul în C++:
c++
#include <iostream>
#include <vector>
using namespace std;
class NQueens {
private:
vector<vector<int>> board;
int size;
public:
NQueens(int size) {
board = vector<vector<int>>(size, vector<int>(size, 0));
this->size = size;
}
bool solve() {
return solve(0);
}
bool solve(int row) {
if (row == size) {
return true;
}
for (int col = 0; col < size; col++) {
if (isSafe(row, col)) {
board[row][col] = 1;
if (solve(row + 1)) {
return true;
} else {
board[row][col] = 0;
}
}
}
return false;
}
bool isSafe(int row, int col) {
// Verifică linii
for (int i = 0; i < row; i++) {
if (board[i][col] == 1) {
return false;
}
}
// Verifică diagonale
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 1) {
return false;
}
}
for (int i = row, j = col; i >= 0 && j < size; i--, j++) {
if (board[i][j] == 1) {
return false;
}
}
return true;
}
void printSolution() {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
cout << board[i][j] << " ";
}
cout << endl;
}
}
};
int main() {
NQueens nQueens(4);
nQueens.solve();
nQueens.printSolution();
return 0;
}
Complexitate
Complexitatea algoritmului de backtracking N-Queens este O(N^N). Aceasta înseamnă că timpul de execuție crește exponențial pe măsură ce dimensiunea tablei de șah crește.
Optimizări
Există mai multe optimizări care pot fi aplicate algoritmului de backtracking N-Queens pentru a îmbunătăți performanța. Aceste optimizări includ:
* Restaurarea parțială a soluțiilor: Dacă o soluție candidat nu este validă, putem restaura parțial soluția prin anularea doar a ultimilor câțiva pași, în loc să revenim la starea inițială.
* Utilizarea de euristice: Putem folosi euristice pentru a ghida algoritmul de backtracking către soluții mai promițătoare. O euristică obișnuită este de a plasa reginele pe coloane care au fost atacate de cele mai puține regine în prezent.
* Paralelizarea: Algoritmul de backtracking N-Queens poate fi paralelizat prin atribuirea diferitelor noduri ale arborelui de căutare procesorului.
Concluzie
Problema N-Queens este o problemă clasică de backtracking care poate fi rezolvată folosind o varietate de algoritmi. Algoritmul de backtracking descris în acest articol este unul dintre cele mai simple și mai eficiente.
Există mai multe optimizări care pot fi aplicate algoritmului de backtracking N-Queens pentru a îmbunătăți performanța. Aceste optimizări includ restaurarea parțială a soluțiilor, utilizarea de euristice și paralelizarea.
Problema N-Queens este un exemplu excelent de modul în care backtracking-ul poate fi folosit pentru a rezolva probleme complexe. Este o problemă fundamentală în informatică și a fost studiată de-a lungul secolelor.
Întrebări frecvente
1. Ce este problema N-Queens?
Problema N-Queens este o problemă clasică de backtracking în care scopul este de a plasa N regine pe o tablă de șah de NxN, astfel încât acestea să nu se atace reciproc.
2. Cum poate fi rezolvată problema N-Queens?
Problema N-Queens poate fi rezolvată folosind backtracking. Backtracking-ul este o tehnică de rezolvare a problemelor care implică construirea unei soluții candidat, verificarea dacă soluția este validă și, dacă nu, revenirea la o stare anterioară și încercarea unei soluții alternative.
3. Care este complexitatea algoritmului de backtracking N-Queens?
Complexitatea algoritmului de backtracking N-Queens este O(N^N).
4. Există optimizări care pot fi aplicate algoritmului de backtracking N-Queens?
Da, există mai multe optimizări care pot fi aplicate algoritmului de backtracking N-Queens pentru a îmbunătăți performanța. Aceste optimizări includ restaurarea parțială a soluțiilor, utilizarea de euristice și paralelizarea.
5. Care sunt unele aplicații ale problemei N-Queens?
Problema N-Queens are aplicații în mai