Innholdsfortegnelse
N-Queens-problemet ved bruk av tilbakeporing i Java/C++
Introduksjon
N-Queens-problemet er et klassisk oppgave innen datavitenskapen som involverer å plassere N dronninger på et NxN-sjakkbrett slik at de ikke angriper hverandre, hverken horisontalt, vertikalt eller diagonalt. Å løse dette problemet krever en metodisk tilnærming for å utforske alle mulige plasseringer og eliminere ugyldige løsninger. Tilbakeporing er en effektiv algoritme som brukes til å løse dette problemet, og denne artikkelen vil utforske implementeringen av denne algoritmen i både Java og C++.
Metodikk
Tilbakeporing er en rekursiv algoritme som starter med en tom plassering av dronninger på sjakkbrettet. Den plasserer deretter dronninger på sjakkbrettet en etter en og sjekker om den gjeldende plasseringen er gyldig (ingen dronninger angriper hverandre). Hvis plasseringen er gyldig, fortsetter algoritmen å utforske dette sporet; ellers backer den opp og prøver et annet spor.
Algoritmen fortsetter denne prosessen rekursivt til den enten finner en gyldig løsning eller har utforsket alle mulige plasseringer. Hvis en gyldig løsning er funnet, returnerer algoritmen plasseringen; ellers returnerer den «ingen løsning».
Java-implementering
java
import java.util.Arrays;
public class NQueens {
public static void main(String[] args) {
int n = 4;
int[][] solution = solveNQueens(n);
if (solution != null) {
printSolution(solution);
} else {
System.out.println("Ingen løsning");
}
}
private static int[][] solveNQueens(int n) {
int[][] board = new int[n][n];
Arrays.fill(board, -1);
boolean[] colUsed = new boolean[n];
boolean[] diag1Used = new boolean[2 * n - 1];
boolean[] diag2Used = new boolean[2 * n - 1];
return solveNQueens(board, colUsed, diag1Used, diag2Used, 0);
}
private static int[][] solveNQueens(int[][] board, boolean[] colUsed, boolean[] diag1Used, boolean[] diag2Used, int row) {
if (row == board.length) {
return board;
}
for (int col = 0; col < board.length; col++) {
if (!colUsed[col] && !diag1Used[row + col] && !diag2Used[row - col + board.length - 1]) {
board[row][col] = 1;
colUsed[col] = true;
diag1Used[row + col] = true;
diag2Used[row - col + board.length - 1] = true;
int[][] solution = solveNQueens(board, colUsed, diag1Used, diag2Used, row + 1);
if (solution != null) {
return solution;
}
board[row][col] = 0;
colUsed[col] = false;
diag1Used[row + col] = false;
diag2Used[row - col + board.length - 1] = false;
}
}
return null;
}
private static void printSolution(int[][] solution) {
for (int i = 0; i < solution.length; i++) {
for (int j = 0; j < solution[i].length; j++) {
System.out.print(solution[i][j] + " ");
}
System.out.println();
}
}
}
C++-implementering
c++
#include <iostream>
#include <vector>
using namespace std;
// Sjakkbrettet representert som en 2D-vektor
vector<vector<int>> board;
// Brukes til å holde oversikt over brukte rader, kolonner og diagonaler
vector<bool> rowUsed;
vector<bool> colUsed;
vector<bool> diag1Used;
vector<bool> diag2Used;
// Løsning som en 2D-vektor
vector<vector<int>> solution;
// Funksjon for å sjekke om en plassering er gyldig
bool isValid(int row, int col) {
return !rowUsed[row] && !colUsed[col] && !diag1Used[row + col] && !diag2Used[row - col + board.size() - 1];
}
// Rekursiv funksjon for å finne en løsning
bool solveNQueens(int row) {
// Hvis vi har nådd bunnen av sjakkbrettet, har vi funnet en løsning
if (row == board.size()) {
solution = board;
return true;
}
// Prøv å plassere en dronning i hver kolonne på raden
for (int col = 0; col < board.size(); col++) {
// Sjekk om plasseringen er gyldig
if (isValid(row, col)) {
// Plasser dronningen
board[row][col] = 1;
rowUsed[row] = true;
colUsed[col] = true;
diag1Used[row + col] = true;
diag2Used[row - col + board.size() - 1] = true;
// Fortsett til neste rad
if (solveNQueens(row + 1)) {
return true;
}
// Hvis vi ikke finner en løsning på denne raden, fjern dronningen
board[row][col] = 0;
rowUsed[row] = false;
colUsed[col] = false;
diag1Used[row + col] = false;
diag2Used[row - col + board.size() - 1] = false;
}
}
// Ingen løsning funnet på denne raden
return false;
}
int main() {
// Les inn størrelsen på sjakkbrettet
int n;
cout << "Enter the size of the chessboard: ";
cin >> n;
// Initialiser sjakkbrettet og bruksmarkørene
board.resize(n, vector<int>(n, 0));
rowUsed.resize(n, false);
colUsed.resize(n, false);
diag1Used.resize(2 * n - 1, false);
diag2Used.resize(2 * n - 1, false);
// Finn en løsning
if (solveNQueens(0)) {
// Skriv ut løsningen
cout << "Solution:\n";
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[i].size(); j++) {
cout << board[i][j] << " ";
}
cout << endl;
}
} else {
cout << "No solution found" << endl;
}
return 0;
}
Konklusjon
Tilbakeporing er en effektiv algoritme for å løse N-Queens-problemet. Dens systematiske tilnærming garanterer at alle mulige løsninger utforskes, og dens tilbakeporingsmekanisme sørger for at kun gyldige plasseringer vurderes. Implementeringen av tilbakeporing i både Java og C++ gir klare og effektive løsninger på problemet.
Vanlige spørsmål
* Hva er N-Queens-problemet?
N-Queens-problemet er å plassere N dronninger på et NxN-sjakkbrett slik at de ikke angriper hverandre.
* Hvordan fungerer tilbakeporing for N-Queens-problemet?
Tilbakeporing starter med en tom plassering og plasserer dronninger en etter en, sjekker hver plasserings gyldighet og backer opp hvis nødvendig.
* Hvorfor er tilbakeporing effektiv for dette problemet?
Tilbakeporing utforsker systematisk alle mulige plasseringer, noe som garanterer at en løsning blir funnet hvis den finnes.
* Hvilke varianter av tilbakeporing kan brukes?
Dybde først, bredde først og iterativ fordypning er varianter av tilbakeporing som kan brukes.
* Finnes det andre algoritmer for å løse N-Queens-problemet?
Ja, det finnes andre algoritmer som f.eks. branch and bound og simulated annealing.
* Hva er kompleksiteten til tilbakeporingsløsningen?