Problema N-Queens folosind backtracking în Java/C++

Cuprins

Problema N-Regine reprezintă o provocare clasică în domeniul algoritmilor de backtracking, având ca obiectiv plasarea a N regine pe o tablă de șah de dimensiuni NxN, astfel încât niciuna dintre ele să nu se afle sub atacul vreuneia dintre celelalte. O regină poate ataca oricare altă piesă situată pe aceeași linie, coloană sau diagonală.

Această problemă a captat atenția matematicienilor și informaticienilor de-a lungul timpului. Există diverse modalități de abordare a acesteia, dar backtracking-ul se evidențiază ca una dintre cele mai populare și eficiente metode.

Ce este Backtracking?

Backtracking-ul este o strategie de rezolvare a problemelor care presupune construirea pas cu pas a unei soluții candidate. În fiecare etapă, se verifică dacă soluția parțială este încă validă. Dacă nu este, algoritmul revine la o stare anterioară și explorează o altă alternativă.

În contextul problemei N-Regine, soluția candidat se construiește plasând reginele pe tablă, rând cu rând. După ce o regină este așezată pe un rând, se efectuează verificări pentru a vedea dacă este amenințată de oricare dintre reginele deja plasate. Dacă se constată un conflict, se revine la pasul anterior și se încearcă o altă poziționare a reginei.

Implementarea Algoritmului N-Regine

Implementare în 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) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 1) {
                return false;
            }
        }

        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();
        }
    }
}

Implementare în C++:

#include 
#include 

using namespace std;

class NQueens {
private:
    vector> board;
    int size;

public:
    NQueens(int size) {
        board = vector>(size, vector(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) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 1) {
                return false;
            }
        }

        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;
}

Complexitatea Algoritmului

Complexitatea algoritmului de backtracking pentru problema N-Regine este de ordinul O(N^N). Asta implică faptul că timpul necesar pentru execuție crește exponențial odată cu dimensiunea tablei de șah.

Strategii de Optimizare

Pentru a crește performanța algoritmului, se pot aplica următoarele optimizări:

Restaurarea parțială a soluțiilor: În cazul unei soluții candidate invalide, se poate reveni doar la ultimii pași, nu la starea inițială.
Utilizarea euristicilor: Euristicile pot ghida algoritmul către soluții mai promițătoare. Una dintre ele este plasarea reginelor pe coloanele atacate de cele mai puține regine deja plasate.
Paralelizarea: Procesarea nodurilor arborelui de căutare poate fi distribuită între mai multe procesoare pentru a reduce timpul de execuție.

Concluzie

Problema N-Regine este un exemplu excelent de problemă care poate fi abordată eficient folosind backtracking. Algoritmul prezentat este relativ simplu și eficient în rezolvarea acesteia.

Prin aplicarea unor optimizări, cum ar fi restaurarea parțială a soluțiilor, utilizarea de euristici sau paralelizarea, performanța algoritmului poate fi îmbunătățită.

Problema N-Regine demonstrează puterea backtracking-ului în rezolvarea problemelor complexe și rămâne un subiect de studiu fundamental în informatică.

Întrebări Frecvente

Ce reprezintă problema N-Regine?
Problema N-Regine este o provocare algoritmică de backtracking în care obiectivul este așezarea a N regine pe o tablă de șah de NxN, astfel încât nicio regină să nu amenințe alta.
Cum se poate rezolva această problemă?
Problema N-Regine se poate rezolva folosind backtracking, o tehnică ce presupune construirea graduală a unei soluții, validarea ei la fiecare pas și revenirea la o stare anterioară în caz de insucces.
Care este complexitatea algoritmului de backtracking pentru N-Regine?
Complexitatea algoritmului de backtracking pentru problema N-Regine este O(N^N).
Există modalități de a optimiza algoritmul?
Da, se pot aplica diverse optimizări cum ar fi restaurarea parțială a soluțiilor, utilizarea de euristici și paralelizarea.
Unde se aplică problema N-Regine?
Problema N-Regine este un model teoretic util, cu aplicabilitate în diverse domenii ce implică căutarea de soluții, cum ar fi optimizarea, planificarea sau analiza conflictelor.