SemyonK
Мастер
(1180)
4 недели назад
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// Проверка, можно ли безопасно поставить ферзя в текущую строку и столбец
bool isSafe(const vector<int>& queens, int row, int col) {
for (int r = 0; r < row; ++r) {
int c = queens[r];
if (c == col || abs(c - col) == abs(row - r)) {
return false;
}
}
return true;
}
// Рекурсивная функция для поиска всех решений
void solveNQueens(int n, int row, vector<int>& queens, int& solutions) {
if (row == n) {
solutions++;
return;
}
for (int col = 0; col < n; ++col) {
if (isSafe(queens, row, col)) {
queens[row] = col;
solveNQueens(n, row + 1, queens, solutions);
queens[row] = -1; // сброс для возврата назад (backtracking)
}
}
}
int main() {
int n;
cout << "Введите размер доски (N): ";
cin >> n;
vector<int> queens(n, -1); // Вектор для хранения позиции ферзей в каждой строке
int solutions = 0; // Счетчик решений
solveNQueens(n, 0, queens, solutions);
cout << "Количество способов расстановки " << n << " ферзей: " << solutions << endl;
return 0;
}
Входные данные
5
Результат работы
10