Problem Królowych N: Rozwiązanie z Cofaniem w Java/C++
Wprowadzenie
Problem Królowych N to klasyczny problem z zakresu informatyki, który polega na rozmieszczeniu N królowych na szachownicy N×N w taki sposób, aby żadne dwie królowe nie atakowały się nawzajem. Problem ten można rozwiązać za pomocą wielu algorytmów, a jednym z najprostszych jest algorytm z cofaniem.
Algorytm z cofaniem polega na systematycznym rozmieszczaniu królowych na szachownicy, a następnie cofaniu się i próbowaniu innych rozmieszczeń, jeśli obecne rozmieszczenie jest nieprawidłowe. Poniżej przedstawiono szczegółowy opis algorytmu:
Algorytm z Cofaniem dla Problemu Królowych N
1. Ustawienie początkowe:
– Ustaw pierwszą królową na pierwszym wierszu i pierwszej kolumnie szachownicy.
2. Generowanie kolejnych rozmieszczeń:
– Jeśli obecne rozmieszczenie jest bezpieczne (żadne dwie królowe nie atakują się nawzajem), przejdź do kolejnego wiersza i ustaw królową w pierwszej kolumnie.
– Jeśli obecne rozmieszczenie nie jest bezpieczne, spróbuj ustawić królową w następnej kolumnie tego samego wiersza.
3. Cofanie:
– Jeśli nie można ustawić królowej w żadnej kolumnie bieżącego wiersza, usuń królową z ostatniego wiersza i spróbuj ustawić ją w następnej kolumnie.
4. Powtarzanie:
– Powtarzaj kroki 2-3, aż rozmieszczone zostaną wszystkie królowe lub dopóki nie będzie już żadnych możliwych rozmieszczeń.
Implementacja w Java
java
import java.util.ArrayList;
import java.util.List;
public class NQueensBacktracking {
public static void main(String[] args) {
int n = 8;
List<List<Integer>> solutions = solveNQueens(n);
for (List<Integer> solution : solutions) {
System.out.println(solution);
}
}
public static List<List<Integer>> solveNQueens(int n) {
List<List<Integer>> solutions = new ArrayList<>();
int[] board = new int[n];
solveNQueens(board, 0, solutions);
return solutions;
}
private static void solveNQueens(int[] board, int row, List<List<Integer>> solutions) {
if (row == board.length) {
List<Integer> solution = new ArrayList<>();
for (int i = 0; i < board.length; i++) {
solution.add(board[i]);
}
solutions.add(solution);
return;
}
for (int col = 0; col < board.length; col++) {
if (isSafe(board, row, col)) {
board[row] = col;
solveNQueens(board, row + 1, solutions);
board[row] = 0;
}
}
}
private static boolean isSafe(int[] board, int row, int col) {
for (int i = 0; i < row; i++) {
if (board[i] == col || Math.abs(board[i] - col) == row - i) {
return false;
}
}
return true;
}
}
Implementacja w C++
cpp
#include <iostream>
#include <vector>
using namespace std;
bool isSafe(int board[][N], int row, int col) {
for (int i = 0; i < row; i++) {
if (board[i][col] || abs(board[i][col] - col) == row - i) {
return false;
}
}
return true;
}
void solveNQueens(int board[][N], int row, vector<vector<int>> &solutions) {
if (row == N) {
vector<int> solution(N);
for (int i = 0; i < N; i++) {
solution[i] = board[i][i];
}
solutions.push_back(solution);
return;
}
for (int col = 0; col < N; col++) {
if (isSafe(board, row, col)) {
board[row][col] = 1;
solveNQueens(board, row + 1, solutions);
board[row][col] = 0;
}
}
}
vector<vector<int>> solveNQueens(int n) {
vector<vector<int>> solutions;
int board[N][N] = {0};
solveNQueens(board, 0, solutions);
return solutions;
}
int main() {
int n = 8;
vector<vector<int>> solutions = solveNQueens(n);
for (vector<int> solution : solutions) {
for (int i = 0; i < n; i++) {
cout << solution[i] << " ";
}
cout << endl;
}
return 0;
}
Wnioski
Algorytm z cofaniem to prosta i wydajna metoda rozwiązywania problemu Królowych N. Jego złożoność czasowa wynosi O(n^n), gdzie n to liczba królowych. Algorytm ten można również wykorzystać do rozwiązywania innych problemów związanych z umiejscowieniem lub przypisaniem.
Pomimo swojej prostoty, algorytm z cofaniem może być czasochłonny dla dużych wartości n. Inne algorytmy, takie jak rekurencja z ograniczeniami, mogą być bardziej wydajne dla dużych wartości n.
Często Zadawane Pytania (FAQs)
1. Co to jest problem Królowych N?
To problem z zakresu informatyki, polegający na rozmieszczeniu N królowych na szachownicy N×N w taki sposób, aby żadne dwie królowe nie atakowały się nawzajem.
2. Co to jest algorytm z cofaniem?
Algorytm, który systematycznie próbuje różnych rozwiązań, a następnie cofa się, jeśli rozwiązanie jest nieprawidłowe.
3. Jak wdrożyć algorytm z cofaniem dla problemu Królowych N?
Ustaw początkowo królowe na szachownicy, a następnie iteruj przez różne rozmieszczenia, cofając się, jeśli rozmieszczenie jest nieprawidłowe.
4. Jaka jest złożoność czasowa algorytmu z cofaniem?
O(n^n), gdzie n to liczba królowych.
5. Czy istnieją inne algorytmy do rozwiązywania problemu Królowych N?
Tak, istnieją inne algorytmy, takie jak rekurencja z ograniczeniami, które mogą być bardziej wydajne dla dużych wartości n.
6. Jaki jest cel rozwiązywania problemu Królowych N?
Rozwiązywanie tego problemu jest ćwiczeniem z zakresu algorytmów i może pomóc w zrozumieniu złożoności algorytmów.
7. Czy problem Królowych N ma jakiekolwiek zastosowania w praktyce?
Tak, problem ten ma zastosowania w różnych dziedzinach, takich jak planowanie zadań, optymalizacja i sztuczna inteligencja.
8. Czy można rozwiązać problem Królowych N za pomocą uczenia maszynowego?
Tak, można wykorzystać uczenie maszynowe do trenowania modelu, który może rozwiązywać problem Królowych N, ale jest to bardziej złożone i mniej wydajne niż tradycyjne algorytmy.
9. Czy problem Królowych N jest odpowiedni dla początkujących w programowaniu?
Tak, problem ten jest stosunkowo prosty i może pomóc początkującym w zrozumieniu podstawowych algorytmów, ale może być trudny do rozwiązania dla dużych wartości n.
10. Gdzie mogę znaleźć więcej informacji na temat problemu Królowych N?
https://en.wikipedia.org/wiki/Eight_queens_puzzle„>Wikipedia
https://www.geeksforgeeks.org/n-queen-problem-backtracking-3/„>GeeksforGeeks