Решение задачи о восьми ферзях. Нахождение одного решения. - EcsFlash/DataTypes GitHub Wiki
Для решения этой задачи мы используем бэктрекинг. Только в нашем случае мы размещаем 8 ферзей.
В векторе индекс - номер строки на шахматной доске(условно ибо нумерация у нас смещенная), а значение лежащее по данному индексу - номер столбца в котором стоит ферзь. Соответственно если positions[4] = 3 то значит на пятой строке в 4 столбце стоит ферзь.
bool canPlace(int row, int col, const vector<int>& positions) {
for (int i = 0; i < row; i++) {
if (positions[i] == col ||
positions[i] - i == col - row ||
positions[i] + i == col + row) {
return false;
}
}
return true;
}
bool placeQueens(int n, int row, vector<int>& positions) {
if (row == n) {
return true;
}
for (int col = 0; col < n; col++) {
if (canPlace(row, col, positions)) {
positions[row] = col;
if (placeQueens(n, row + 1, positions)) {
return true;
}
// Если не получилось, откатываемся (backtrack)
}
}
return false;
}
Суть такова, что мы берем 1-ого ферзя, рассматриваем 1-ую строку, и для первой строки рассматриваем все столбцы и проверяем, можно ли поставить туда ферзя - если да, то переходим к след. ферзю. Теперь мы рассматриваем 2-ую строку и пытаемся воткнуть ферзя в какой-то столбец(столбцы перебираем все, начиная с первого)так, чтобы он не бил других ферзей. Если получилось переходим к 3 строке и тд... Сложность O(N!)