Вступ
Завдання N-Ферзів є відомою головоломкою в галузі обчислювальної геометрії, яка вимагає розміщення N ферзів на шахівниці розміром NxN таким чином, щоб жоден з них не загрожував іншому. Ферзі можуть загрожувати один одному по горизонталі, вертикалі та діагоналі. Ця задача, запропонована Готхольдом Ейзенштейном у 1850 році, досі залишається цікавою як для любителів головоломок, так і для дослідників в академічних колах.
У цьому огляді ми розглянемо вирішення задачі N-Ферзів з використанням алгоритму зворотного відстеження, продемонстрованого на прикладах Java та C++. Спершу ми детально розглянемо принцип зворотного відстеження, а потім перейдемо до реалізації цього алгоритму в обох мовах програмування. Також ми надамо приклади коду для наочної ілюстрації процесу розв’язання задачі та обговоримо способи його оптимізації.
Суть Алгоритму Зворотного Відстеження
Зворотне відстеження є алгоритмом для вирішення комбінаторних завдань оптимізації та пошуку. Його дія базується на рекурсивному дослідженні всіх можливих комбінацій, при цьому зберігаються потенційні розв’язки, а ті, що не відповідають умовам, відкидаються. Алгоритм зворотного відстеження включає такі ключові складові:
- Кандидати: Набір усіх можливих варіантів дій на кожному етапі алгоритму.
- Розв’язки: Список знайдених конфігурацій, що задовольняють задані обмеження.
- Конфігурація: Поточна комбінація обраних варіантів, від якої алгоритм продовжує пошук.
- Обмеження: Набір правил, що використовуються для перевірки придатності кожного потенційного розв’язку.
Реалізація на Java
Реалізація алгоритму зворотного відстеження на Java для розв’язання задачі N-Ферзів може бути представлена наступним чином:
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);
// Друк усіх знайдених рішень (не обов'язково для кожного n, можна прибрати або переробити)
for(List<Integer> solution : solutions) {
System.out.println(solution);
}
}
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-Ферзів виглядає так:
#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() {
const int n = 8; // розмір дошки
int board[n][n] = {0};
solveNQueens(board, 0);
// Друк усіх знайдених рішень (не обов'язково для кожного n, можна прибрати або переробити)
for (const auto& solution : solutions) {
for (int pos : solution) {
cout << pos << " ";
}
cout << endl;
}
return 0;
}
Висновок
Задача N-Ферзів є класичним прикладом завдання, яке можна успішно вирішити за допомогою алгоритму зворотного відстеження. Наведені реалізації на Java та C++ наочно демонструють ефективність цього підходу та можуть бути легко адаптовані для інших комбінаторних задач оптимізації та пошуку.
Зворотне відстеження є потужним інструментом для розв’язання задач із скінченною кількістю розв’язків, але його складність може зростати експоненційно в найгіршому випадку. Для великих значень N існує ряд оптимізаційних технік, що дозволяють скоротити час виконання.