Задача N-Королев: Розв’язок за Допомогою Зворотного Відстеження в Java/C++
Вступ
Задача N-Королев – це класична задача обчислювальної геометрії, яка полягає у розміщенні N королев на дошці NxN таким чином, щоб жодні дві королеви не загрожували одна одній, ні по горизонталі, ні по вертикалі, ні по діагоналі. Ця задача була вперше поставлена Готхольдом Ейзештейном 1850 року і досі залишається популярною головоломкою та предметом академічних досліджень.
У цьому посібнику ми дослідимо розв’язок задачі N-Королев за допомогою алгоритму зворотного відстеження, реалізованого як у Java, так і в C++. Ми почнемо з огляду алгоритму зворотного відстеження, а потім перейдемо до деталей його реалізації в кожній мові програмування. Крім того, ми надамо приклади коду, щоб проілюструвати розв’язання задачі, а також обговоримо підходи до її оптимізації.
Алгоритм Зворотного Відстеження
Зворотне відстеження – це алгоритм для розв’язування комбінаторних задач оптимізації та пошуку. Він працює шляхом рекурсивного перебору всіх можливих комбінацій, зберігаючи потенційні рішення та відстежуючи ті, що не відповідають заданим обмеженням. Алгоритм зворотного відстеження складається з таких компонентів:
* Кандидати: Список усіх можливих варіантів вибору на поточному кроці алгоритму.
* Розв’язки: Список знайдених розв’язків, які задовольняють обмеженням задачі.
* Конфігурація: Поточна комбінація виборів, з якої ми будемо проводити розгалуження.
* Обмеження: Набір правил, які використовуються для перевірки, чи є розв’язок придатним.
Реалізація в Java
Реалізація алгоритму зворотного відстеження в Java для розв’язування задачі N-Королев може виглядати так:
java
import java.util.ArrayList;
import java.util.List;
public class NQueens {
private static List<List<Integer>> solutions = new ArrayList<>();
public static void main(String[] args) {
int n = 8;
solveNQueens(n);
}
public static void solveNQueens(int n) {
int[] board = new int[n]; // Розташування королев на дошці
solveNQueens(board, 0);
}
private static void solveNQueens(int[] board, int row) {
// Якщо ми розмістили всіх королев, додати розв'язок
if (row == board.length) {
solutions.add(copyBoard(board));
return;
}
// Спробувати всі можливі позиції королеви в поточному рядку
for (int col = 0; col < board.length; col++) {
if (isSafe(board, row, col)) {
board[row] = col; // Розмістити королеву
solveNQueens(board, row + 1); // Продовжити рекурсію для наступного рядка
board[row] = 0; // Зняти королеву після рекурсії
}
}
}
// Перевірити, чи є позиція (row, col) безпечною для розміщення королеви
private static boolean isSafe(int[] board, int row, int col) {
// Перевірити конфлікти у вертикальному напрямку
for (int i = 0; i < row; i++) {
if (board[i] == col) {
return false;
}
}
// Перевірити конфлікти у північно-східному напрямку
int i = row - 1;
int j = col + 1;
while (i >= 0 && j < board.length) {
if (board[i] == j) {
return false;
}
i--;
j++;
}
// Перевірити конфлікти у північно-західному напрямку
i = row - 1;
j = col - 1;
while (i >= 0 && j >= 0) {
if (board[i] == j) {
return false;
}
i--;
j--;
}
// Якщо конфліктів немає, то позиція безпечна
return true;
}
// Скопіювати дошку
private static List<Integer> copyBoard(int[] board) {
List<Integer> copy = new ArrayList<>();
for (int i : board) {
copy.add(i);
}
return copy;
}
}
Реалізація в C++
Реалізація алгоритму зворотного відстеження в C++ для розв’язування задачі N-Королев може виглядати так:
cpp
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> solutions; // Список розв'язків
bool isSafe(int board[][N], int row, int col) {
// Перевірити конфлікти у вертикальному напрямку
for (int i = 0; i < row; i++) {
if (board[i][col] == 1) {
return false;
}
}
// Перевірити конфлікти у північно-східному напрямку
int i = row - 1;
int j = col + 1;
while (i >= 0 && j < N) {
if (board[i][j] == 1) {
return false;
}
i--;
j++;
}
// Перевірити конфлікти у північно-західному напрямку
i = row - 1;
j = col - 1;
while (i >= 0 && j >= 0) {
if (board[i][j] == 1) {
return false;
}
i--;
j--;
}
// Якщо конфліктів немає, то позиція безпечна
return true;
}
void solveNQueens(int board[][N], int row) {
// Якщо ми розмістили всіх королев, додати розв'язок
if (row == N) {
vector<int> solution;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] == 1) {
solution.push_back(j + 1);
}
}
}
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); // Продовжити рекурсію для наступного рядка
board[row][col] = 0; // Зняти королеву після рекурсії
}
}
}
int main() {
int n = 8;
int board[N][N] = {0};
solveNQueens(board, 0);
return 0;
}
Висновок
Задача N-Королев є класичною і добре вивченою задачею, яку можна ефективно розв’язувати за допомогою алгоритму зворотного відстеження. Реалізації на Java та C++, наведені в цьому посібнику, демонструють силу цього підходу та можуть бути легко адаптовані до інших комбінаторних задач оптимізації та пошуку.
Зворотного відстеження є потужним методом для розв’язку задач зі скінченним рішенням, але його час виконання може бути експоненціальним у найгіршому випадку. Для великих значень N існує ряд технік оптимізації