Tartalomjegyzék
N-Queens probléma visszafelé követéssel Java/C++ nyelven
Bevezetés
Az N-Queens probléma egy klasszikus rejtvény és számítástudományi probléma, amelyben egy N×N-es sakktáblán meg kell helyezni N darab királynőt úgy, hogy azok ne üssék egymást. A probléma azért kapta a nevét, mert a királynők sakkfigurák, amelyek bármely irányba (vízszintesen, függőlegesen vagy átlósan) tetszőleges számú mezőt meg tudnak támadni.
A probléma visszafelé követéssel való megoldása egy olyan algoritmus, amely a megoldások keresésére iteratív megközelítést alkalmaz. Egy lépésben egy lehetséges megoldást figyelembe vesz, és ha az nem vezet megoldáshoz, akkor visszalép és egy másik lehetséges megoldást próbál ki.
Algoritmus
Az N-queens probléma visszafelé követéssel való megoldása a következő lépésekből áll:
1. Inicializálás: Hozzon létre egy N×N-es mátrixot, amely eleinte mindegyik mezőjét hamisra állítja. Ez a mátrix jelzi majd, hogy melyik mezőkön helyezkednek el királynők.
2. Sorok iterálása: Iteráljon a mátrix sorain 0-tól N-1-ig.
3. Oszlopok iterálása: Az aktuális sor minden oszlopánál:
– Ha az oszlop szabad (azaz a mátrix megfelelő mezője hamis), akkor helyezzen el egy királynőt az adott mezőre.
– Ha az oszlop nem szabad, akkor folytassa a következő oszloppal.
4. Ellenőrzés: Ellenőrizze, hogy az aktuális elrendezés érvényes-e (azaz nem fenyegeti egyik királynő sem a másikat).
– Ha érvényes, akkor haladjon tovább a következő sorral.
– Ha nem érvényes, akkor távolítsa el a királynőt az aktuális mezőről, és folytassa a következő oszloppal.
5. Megoldás: Ha az összes soron végigiterált, és minden oszlopban szabad mezőt talált, akkor az aktuális elrendezés egy megoldás.
Java megvalósítás
java
public class NQueens {
// Mátrix a királynők helyzetének tárolására
private int[][] board;
// Királynők száma
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;
}
}
}
// Visszafelé követéses megoldás
public boolean solve() {
return solve(0);
}
// Visszafelé követéses segédfunkció
private boolean solve(int row) {
if (row == n) {
// Minden sorra találtunk királynőelhelyezést
return true;
}
for (int col = 0; col < n; col++) {
// Ha a mező szabad
if (isSafe(row, col)) {
// Királynő elhelyezése
board[row][col] = 1;
// Következő sor rekurzívan
if (solve(row + 1)) {
return true;
}
// Visszalépés
board[row][col] = 0;
}
}
// Nem sikerült megoldást találni az aktuális sorban
return false;
}
// Ellenőrzi, hogy az adott mezőre elhelyezhető-e királynő
private boolean isSafe(int row, int col) {
// Ugyanazon oszlopban
for (int i = 0; i < row; i++) {
if (board[i][col] == 1) {
return false;
}
}
// Bal felső átló
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 1) {
return false;
}
}
// Jobb felső átló
for (int i = row, j = col; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 1) {
return false;
}
}
// Szabad mező
return true;
}
// Megoldás kiírása
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();
}
}
}
C++ megvalósítás
cpp
#include <iostream>
#include <vector>
using namespace std;
// Tábla mérete
const int N = 4;
// Királynők pozícióinak jelzése
const int QUEEN = 1;
const int SAFE = 0;
// N-queens probléma megoldása visszafelé követéssel
bool solveNQueens(vector<vector<int>>& board, int col) {
// Ha az összes oszlop le lett fedezve
if (col >= N) {
return true;
}
// Minden sor átvizsgálása
for (int row = 0; row < N; row++) {
// Ha a mező szabad
if (isSafe(board, row, col)) {
// Királynő elhelyezése
board[row][col] = QUEEN;
// Következő oszlop rekurzívan
if (solveNQueens(board, col + 1)) {
return true;
}
// Visszalépés
board[row][col] = SAFE;
}
}
// Nem sikerült megoldást találni az aktuális oszlopban
return false;
}
// Ellenőrzi, hogy az adott mezőre elhelyezhető-e királynő
bool isSafe(vector<vector<int>>& board, int row, int col) {
// Ugyanazon oszlopban
for (int i = 0; i < row; i++) {
if (board[i][col] == QUEEN) {
return false;
}
}
// Bal felső átló
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == QUEEN) {
return false;
}
}
// Jobb felső átló
for (int i = row, j = col; i >= 0 && j < N; i--, j++) {
if (board[i][j] == QUEEN) {
return false;
}
}
// Szabad mező
return true;
}
// Megoldás kiírása
void printSolution(vector<vector<int>>& board) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << board[i][j] << " ";
}
cout << endl;
}
}
int main() {
// Tábla inicializálása
vector<vector<int>> board(N, vector<int>(N, SAFE));
// Megoldás keresése
if (solveNQueens(board, 0)) {
cout << "Megoldás található." << endl;
printSolution(board);
} else {
cout << "Nem található megoldás." << endl;
}
return 0;
}
Következtetés
Az N-Queens probléma visszafelé követéssel való megoldása egy hatékony algoritmus, amely használható tetszőleges méretű sakktáblák megoldására. Ez az algoritmus a lehetséges megoldások térén alkalmaz iteratív megközelítést, és a visszalépés lehetőségét használja a nem eredményes megoldások elvetésére.
A probl