N-dronninger-problem ved hjælp af backtracking i Java/C++

N-dronninger-problemet ved hjælp af backtracking i Java/C++

Introduktion

N-dronninger-problemet er et klassisk kombinatorisk problem, hvor målet er at placere N dronninger på et NxN skakbræt, således at ingen af dronningerne kan slå hinanden. Dette problem er blevet studeret i århundreder og har mange anvendelser inden for computer science, matematik og andre videnskaber.

I denne artikel vil vi udforske N-dronninger-problemet og præsentere en løsning ved hjælp af backtracking-algoritmen, implementeret i både Java og C++. Vi vil diskutere algoritmens kompleksitet, fordele og ulemper samt præsentere eksempler på løsninger for forskellige størrelser af skakbrættet.

N-dronninger-problemet

Definition:

N-dronninger-problemet er defineret som følger:

“Givet et NxN skakbræt, placér N dronninger på brættet, således at ingen af dronningerne kan slå hinanden, det vil sige, at de ikke står på samme række, søjle eller diagonal som en anden dronning.”

Eksempel:

For et 4×4 skakbræt er én mulig løsning på N-dronninger-problemet:


[1, 3, 0, 2]
[2, 0, 3, 1]
[3, 1, 2, 0]
[0, 2, 1, 3]


hvor hver tal repræsenterer dronningens placering på den tilsvarende række i den tilsvarende søjle.

Backtracking-algoritme

Backtracking er en algoritme, der bruges til at løse problemer, hvor der er flere mulige løsninger, og den bedste løsning skal findes. Algoritmen fungerer ved at generere alle mulige løsninger og derefter eliminere de ugyldige løsninger indtil den når frem til den bedste løsning.

I tilfældet med N-dronninger-problemet kan vi bruge backtracking til at finde en gyldig løsning ved at placere dronninger på brættet én ad gangen. For hver dronning kan vi placere den på alle mulige positioner på den aktuelle række. Hvis den placering ikke er gyldig (det vil sige, hvis den kan slås af en anden dronning), så går vi tilbage og prøver en anden placering. Vi fortsætter på denne måde, indtil vi finder en gyldig løsning.

Java-implementering

Følgende Java-kode implementerer backtracking-algoritmen for at løse N-dronninger-problemet:

java
public class NQueens {

private int[][] board;
private int n;

public NQueens(int n) {
this.n = n;
board = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = 0;
}
}
}

public boolean solve() {
return solve(0);
}

private boolean solve(int col) {
if (col == n) {
return true;
}

for (int i = 0; i < n; i++) {
if (isSafe(i, col)) {
board[i][col] = 1;
if (solve(col + 1)) {
return true;
} else {
board[i][col] = 0;
}
}
}

return false;
}

private boolean isSafe(int row, int col) {
for (int i = 0; i < col; i++) {
if (board[row][i] == 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 < n && j >= 0; i++, j--) {
if (board[i][j] == 1) {
return false;
}
}

return true;
}

public void printSolution() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}

public static void main(String[] args) {
int n = 4;
NQueens nQueens = new NQueens(n);
if (nQueens.solve()) {
nQueens.printSolution();
} else {
System.out.println("Ingen løsning");
}
}
}


C++-implementering

Følgende C++-kode implementerer backtracking-algoritmen for at løse N-dronninger-problemet:

cpp
#include <iostream>
#include <vector>

using namespace std;

class NQueens {
private:
vector<vector<int>> board;
int n;

public:
NQueens(int n) : n(n) {
board.resize(n, vector<int>(n, 0));
}

bool solve() {
return solve(0);
}

private:
bool solve(int col) {
if (col == n) {
return true;
}

for (int i = 0; i < n; i++) {
if (isSafe(i, col)) {
board[i][col] = 1;
if (solve(col + 1)) {
return true;
} else {
board[i][col] = 0;
}
}
}

return false;
}

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

return true;
}

void printSolution() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << board[i][j] << " ";
}
cout << endl;
}
}
};

int main() {
int n = 4;
NQueens nQueens(n);
if (nQueens.solve()) {
nQueens.printSolution();
} else {
cout << "Ingen løsning" << endl;
}

return 0;
}


Kompleksitet

Backtracking-algoritmen til N-dronninger-problemet har en eksponentiel kompleksitet, da den skal overveje alle mulige kombinationer af dronningplaceringer. Den nøjagtige kompleksitet af algoritmen er Oo(n^n), hvor n er antallet af dronninger (og størrelsen af brættet).

Fordele og ulemper

Fordele:

* Backtracking er en enkel algoritme at implementere.
* Den kan finde en løsning til N-dronninger-problemet, hvis en sådan løsning findes.
* Den kan bruges til at finde alle mulige løsninger til problemet.

Ulemper:

* Algoritmen har en eksponentiel kompleksitet, hvilket kan gøre den upraktisk for store værdier af n.
* Den kan være ineffektiv, hvis der er mange ugyldige løsninger, da den skal overveje dem alle.

Konklusion

N-dronninger-problemet er et klassisk problem inden for computer science med mange anvendelser. Backtracking er en effektiv algoritme til at løse problemet for små og mellemstore værdier af n. For større værdier af n kan mere avancerede algoritmer, såsom genetiske algoritmer eller heuristik, være nødvendige for at finde en løsning i rimelig tid.

N-dronninger-problemet har også betydning for andre områder, såsom matematik