A
Part 1 (see part 2 below)Perhaps you wanted us to comment on your decision in response, or find mistakes. I decided, as a response, to implement my decision, that might be useful, for example, to compare the answers.You have a very interesting and super-famous task, and it's been a pleasure to write one more time from scratch, and I've already written this task several times. Decided, of course, a classic approach through the approach called https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D1%81_%D0%B2%D0%BE%D0%B7%D0%B2%D1%80%D0%B0%D1%82%D0%BE%D0%BC (Back-tracking in English).The target was set for boards of any size, not only 8x8, and I'm not even supported by a square board. Size can be applied in the first line of main(s) rows (number of ranks) and cols (number of columns) and N - number of ferzees.I also decided to visualize all the decisions in the form of a dose of sunshine. After the code below, look at the example of the withdrawal of the consoles where the boards are issued, wet the very end of the withdrawal, there are a number of decisions. Number of solutions: 92 (92 for 8x8 boards and 8 pheres). If only a number of decisions are to be taken but not to remove the boards themselves, it is not far from the start of the Solve(s) function to replace if (1) { ♪ if (0) {♪The entire code is detailed in Russian. https://godbolt.org/z/8r89M9fv1 #include <iostream>
#include <vector>
#include <string>
void Output(std::vector<std::vector<bool>> & board, std::vector<std::string> & lines, bool last);
// Рекурсивная функция для решения бэк-трэкингом.
// board - доска, board[i][j] == true если стоит ферзь в [i][j], иначе false.
// lines - вспомогательный массив для сбора выводимых в консоль строк.
// N - количество ферзей, cnt - сколько ферзей уже удалось расставить
// (start_i, start_j) - с какой позиции пытаться расставлять следующего ферзя
void Solve(std::vector<std::vector<bool>> & board, std::vector<std::string> & lines,
int N, int & num_sol, int cnt = 0, int start_i = 0, int start_j = 0, int depth = 0) {
if (cnt >= N) {
Output(board, lines, false);
// Увеличиваем счётчик числа решений.
++num_sol;
return;
}
// Обходим всю доску, начиная с позиции последнего ферзя.
for (int i = start_i; i < board.size(); ++i)
for (int j = i == start_i ? start_j : 0; j < board[i].size(); ++j) {
bool attacked = false;
// Цикл по k проверяет атакована ли позиция [i][j]
for (int k = 0; k < (board.size() > board[i].size() ?
board.size() : board[i].size()); ++k)
if (
// Есть ли атака по горизонтали
k < board[i].size() && k != j && board[i][k] ||
// Атака по вертикали
k < board.size() && k != i && board[k][j] ||
// Атака по главной диагонали
k < board.size() && k != i && 0 <= j - i + k &&
j - i + k < board[i].size() && board[k][j - i + k] ||
// Атака по второстепенной диагонали
k < board.size() && k != i && 0 <= j + i - k &&
j + i - k < board[i].size() && board[k][j + i - k]
) {
attacked = true;
break;
}
if (attacked)
continue;
// Позиция [i][j] не под атакой, потому ставим ферзя
board[i][j] = true;
// Рекурисвный спуск для расстановки следующего ферзя
Solve(board, lines, N, num_sol, cnt + 1, i, j + 1, depth + 1);
// Бэктрэкинг, удаляем прошлого установленного ферзя
board[i][j] = false;
}
if (depth == 0)
Output(board, lines, true);
}
// Функция для вывода решений.
void Output(std::vector<std::vector<bool>> & board, std::vector<std::string> & lines, bool last) {
// Вывод решения в консоль. Поставить тут if (0) если не нужно выводить доски в консоль.
if (1) {
if (!last) {
// Добавление одной доски к текущим строкам.
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[i].size(); ++j)
lines[i].push_back(board[i][j] ? 'Q' : '.');
// Символ | в качестве разделителя между досок.
lines[i] += "|";
}
}
// Если длина строк превысила ширину консоли (70), то выводим строки и разделитель.
if (lines.at(0).size() >= 70 || last && !lines.at(0).empty()) {
for (int i = 0; i < lines.size(); ++i)
std::cout << lines[i] << std::endl;
for (int j = 0; j < lines.at(0).size(); ++j)
std::cout << (lines.at(0)[j] == '|' ? '+' : '-');
std::cout << std::endl;
// Очищаем строки для следующих выводов досок.
lines.clear();
lines.resize(board.size());
}
}
}
int main() {
// Входные параметры, rows - число рядов доски, cols - число столбцов
// N - число ферзей которые нужно расставить
int const rows = 8, cols = 8, N = 8;
// Заполняем пустыми значениями доску размером [rows][cols]
std::vector<std::vector<bool>> board(rows, std::vector<bool>(cols));
std::vector<std::string> lines(rows);
// Ответ, число решений
int num_sol = 0;
// Запускаем бэк-трэкинг поиск решений.
Solve(board, lines, N, num_sol);
// Вывод ответа.
std::cout << "Number of solutions: " << num_sol << std::endl;
}
Consoli withdrawal (total number of decisions at the end):
Q.......|Q.......|Q.......|Q.......|.Q......|.Q......|.Q......|.Q......|
....Q...|.....Q..|......Q.|......Q.|...Q....|....Q...|....Q...|.....Q..|
.......Q|.......Q|...Q....|....Q...|.....Q..|......Q.|......Q.|Q.......|
.....Q..|..Q.....|.....Q..|.......Q|.......Q|Q.......|...Q....|......Q.|
..Q.....|......Q.|.......Q|.Q......|..Q.....|..Q.....|Q.......|...Q....|
......Q.|...Q....|.Q......|...Q....|Q.......|.......Q|.......Q|.......Q|
.Q......|.Q......|....Q...|.....Q..|......Q.|.....Q..|.....Q..|..Q.....|
...Q....|....Q...|..Q.....|..Q.....|....Q...|...Q....|..Q.....|....Q...|
--------+--------+--------+--------+--------+--------+--------+--------+
.Q......|.Q......|.Q......|.Q......|..Q.....|..Q.....|..Q.....|..Q.....|
.....Q..|......Q.|......Q.|.......Q|Q.......|....Q...|....Q...|....Q...|
.......Q|..Q.....|....Q...|.....Q..|......Q.|.Q......|.Q......|......Q.|
..Q.....|.....Q..|.......Q|Q.......|....Q...|.......Q|.......Q|Q.......|
Q.......|.......Q|Q.......|..Q.....|.......Q|Q.......|.....Q..|...Q....|
...Q....|....Q...|...Q....|....Q...|.Q......|......Q.|...Q....|.Q......|
......Q.|Q.......|.....Q..|......Q.|...Q....|...Q....|......Q.|.......Q|
....Q...|...Q....|..Q.....|...Q....|.....Q..|.....Q..|Q.......|.....Q..|
--------+--------+--------+--------+--------+--------+--------+--------+
..Q.....|..Q.....|..Q.....|..Q.....|..Q.....|..Q.....|..Q.....|..Q.....|
....Q...|.....Q..|.....Q..|.....Q..|.....Q..|.....Q..|.....Q..|.....Q..|
.......Q|.Q......|.Q......|.Q......|...Q....|...Q....|.......Q|.......Q|
...Q....|....Q...|......Q.|......Q.|Q.......|.Q......|Q.......|Q.......|
Q.......|.......Q|Q.......|....Q...|.......Q|.......Q|...Q....|....Q...|
......Q.|Q.......|...Q....|Q.......|....Q...|....Q...|......Q.|......Q.|
.Q......|......Q.|.......Q|.......Q|......Q.|......Q.|....Q...|.Q......|
.....Q..|...Q....|....Q...|...Q....|.Q......|Q.......|.Q......|...Q....|
--------+--------+--------+--------+--------+--------+--------+--------+
..Q.....|..Q.....|..Q.....|..Q.....|...Q....|...Q....|...Q....|...Q....|
.....Q..|......Q.|......Q.|.......Q|Q.......|Q.......|.Q......|.Q......|
.......Q|.Q......|.Q......|...Q....|....Q...|....Q...|....Q...|......Q.|
.Q......|.......Q|.......Q|......Q.|.......Q|.......Q|.......Q|..Q.....|
...Q....|....Q...|.....Q..|Q.......|.Q......|.....Q..|.....Q..|.....Q..|
Q.......|Q.......|...Q....|.....Q..|......Q.|..Q.....|Q.......|.......Q|
......Q.|...Q....|Q.......|.Q......|..Q.....|......Q.|..Q.....|Q.......|
....Q...|.....Q..|....Q...|....Q...|.....Q..|.Q......|......Q.|....Q...|
--------+--------+--------+--------+--------+--------+--------+--------+
...Q....|...Q....|...Q....|...Q....|...Q....|...Q....|...Q....|...Q....|
.Q......|.Q......|.Q......|.Q......|.....Q..|.....Q..|.....Q..|......Q.|
......Q.|......Q.|.......Q|.......Q|Q.......|.......Q|.......Q|Q.......|
..Q.....|....Q...|....Q...|.....Q..|....Q...|.Q......|..Q.....|.......Q|
.....Q..|Q.......|......Q.|Q.......|.Q......|......Q.|Q.......|....Q...|
.......Q|.......Q|Q.......|..Q.....|.......Q|Q.......|......Q.|.Q......|
....Q...|.....Q..|..Q.....|....Q...|..Q.....|..Q.....|....Q...|.....Q..|
Q.......|..Q.....|.....Q..|......Q.|......Q.|....Q...|.Q......|..Q.....|
--------+--------+--------+--------+--------+--------+--------+--------+
...Q....|...Q....|...Q....|...Q....|...Q....|...Q....|....Q...|....Q...|
......Q.|......Q.|......Q.|.......Q|.......Q|.......Q|Q.......|Q.......|
..Q.....|....Q...|....Q...|Q.......|Q.......|....Q...|...Q....|.......Q|
.......Q|.Q......|..Q.....|..Q.....|....Q...|..Q.....|.....Q..|...Q....|
.Q......|.....Q..|Q.......|.....Q..|......Q.|Q.......|.......Q|.Q......|
....Q...|Q.......|.....Q..|.Q......|.Q......|......Q.|.Q......|......Q.|
Q.......|..Q.....|.......Q|......Q.|.....Q..|.Q......|......Q.|..Q.....|
.....Q..|.......Q|.Q......|....Q...|..Q.....|.....Q..|..Q.....|.....Q..|
--------+--------+--------+--------+--------+--------+--------+--------+
....Q...|....Q...|....Q...|....Q...|....Q...|....Q...|....Q...|....Q...|
Q.......|.Q......|.Q......|.Q......|.Q......|..Q.....|..Q.....|..Q.....|
.......Q|...Q....|...Q....|.....Q..|.......Q|Q.......|Q.......|.......Q|
.....Q..|.....Q..|......Q.|Q.......|Q.......|.....Q..|......Q.|...Q....|
..Q.....|.......Q|..Q.....|......Q.|...Q....|.......Q|.Q......|......Q.|
......Q.|..Q.....|.......Q|...Q....|......Q.|.Q......|.......Q|Q.......|
.Q......|Q.......|.....Q..|.......Q|..Q.....|...Q....|.....Q..|.....Q..|
...Q....|......Q.|Q.......|..Q.....|.....Q..|......Q.|...Q....|.Q......|
--------+--------+--------+--------+--------+--------+--------+--------+
....Q...|....Q...|....Q...|....Q...|....Q...|....Q...|....Q...|....Q...|
......Q.|......Q.|......Q.|......Q.|......Q.|......Q.|.......Q|.......Q|
Q.......|Q.......|.Q......|.Q......|.Q......|...Q....|...Q....|...Q....|
..Q.....|...Q....|...Q....|.....Q..|.....Q..|Q.......|Q.......|Q.......|
.......Q|.Q......|.......Q|..Q.....|..Q.....|..Q.....|..Q.....|......Q.|
.....Q..|.......Q|Q.......|Q.......|Q.......|.......Q|.....Q..|.Q......|
...Q....|.....Q..|..Q.....|...Q....|.......Q|.....Q..|.Q......|.....Q..|
.Q......|..Q.....|.....Q..|.......Q|...Q....|.Q......|......Q.|..Q.....|
--------+--------+--------+--------+--------+--------+--------+--------+
.....Q..|.....Q..|.....Q..|.....Q..|.....Q..|.....Q..|.....Q..|.....Q..|
Q.......|.Q......|.Q......|..Q.....|..Q.....|..Q.....|..Q.....|..Q.....|
....Q...|......Q.|......Q.|Q.......|Q.......|Q.......|....Q...|....Q...|
.Q......|Q.......|Q.......|......Q.|.......Q|.......Q|......Q.|.......Q|
.......Q|..Q.....|...Q....|....Q...|...Q....|....Q...|Q.......|Q.......|
..Q.....|....Q...|.......Q|.......Q|.Q......|.Q......|...Q....|...Q....|
......Q.|.......Q|....Q...|.Q......|......Q.|...Q....|.Q......|.Q......|
...Q....|...Q....|..Q.....|...Q....|....Q...|......Q.|.......Q|......Q.|
--------+--------+--------+--------+--------+--------+--------+--------+
.....Q..|.....Q..|.....Q..|.....Q..|.....Q..|.....Q..|.....Q..|.....Q..|
..Q.....|..Q.....|..Q.....|...Q....|...Q....|...Q....|...Q....|.......Q|
......Q.|......Q.|......Q.|Q.......|.Q......|......Q.|......Q.|.Q......|
.Q......|.Q......|...Q....|....Q...|.......Q|Q.......|Q.......|...Q....|
...Q....|.......Q|Q.......|.......Q|....Q...|..Q.....|.......Q|Q.......|
.......Q|....Q...|.......Q|.Q......|......Q.|....Q...|.Q......|......Q.|
Q.......|Q.......|.Q......|......Q.|Q.......|.Q......|....Q...|....Q...|
....Q...|...Q....|....Q...|..Q.....|..Q.....|.......Q|..Q.....|..Q.....|
--------+--------+--------+--------+--------+--------+--------+--------+
......Q.|......Q.|......Q.|......Q.|......Q.|......Q.|......Q.|......Q.|
Q.......|.Q......|.Q......|..Q.....|..Q.....|...Q....|...Q....|....Q...|
..Q.....|...Q....|.....Q..|Q.......|.......Q|.Q......|.Q......|..Q.....|
.......Q|Q.......|..Q.....|.....Q..|.Q......|....Q...|.......Q|Q.......|
.....Q..|.......Q|Q.......|.......Q|....Q...|.......Q|.....Q..|.....Q..|
...Q....|....Q...|...Q....|....Q...|Q.......|Q.......|Q.......|.......Q|
.Q......|..Q.....|.......Q|.Q......|.....Q..|..Q.....|..Q.....|.Q......|
....Q...|.....Q..|....Q...|...Q....|...Q....|.....Q..|....Q...|...Q....|
--------+--------+--------+--------+--------+--------+--------+--------+
.......Q|.......Q|.......Q|.......Q|
.Q......|.Q......|..Q.....|...Q....|
...Q....|....Q...|Q.......|Q.......|
Q.......|..Q.....|.....Q..|..Q.....|
......Q.|Q.......|.Q......|.....Q..|
....Q...|......Q.|....Q...|.Q......|
..Q.....|...Q....|......Q.|......Q.|
.....Q..|.....Q..|...Q....|....Q...|
--------+--------+--------+--------+
Number of solutions: 92
Part 2 (Part 3 below)At the author ' s request, the decision in Part 1 was simplified to avoid using std::vector, instead, used the usual Cy masses.The comment, the size of the C-band, I did more than the challenge, is because the size of the C-band is required to be specified in the compilation phase, and the real dimensions of the task (number of rows and columns) can already be requested from the user at the start of the program by reading them from the start of the program. std::cin♪ Also note that the sizes are put through enum at the beginning of the programme if enum No, they can be asked through macroes. #define max_rows 16 and #define max_cols 16 or simply encoded the number locations max_rows and max_cols♪ https://godbolt.org/z/Wfh6bjExW #include <iostream>
#include <string>
// Максимальное допустимое число рядов и колонок на доске
enum { max_rows = 16, max_cols = 16 };
// Декларирование функции Output, определённой ниже.
void Output(bool (& board)[max_rows][max_cols], std::string (& lines)[max_rows],
int rows, int cols, bool last);
// Рекурсивная функция для решения бэк-трэкингом.
// board - доска, board[i][j] == true если стоит ферзь в [i][j], иначе false.
// lines - вспомогательный массив для сбора выводимых в консоль строк.
// N - количество ферзей, cnt - сколько ферзей уже удалось расставить
// (start_i, start_j) - с какой позиции пытаться расставлять следующего ферзя
void Solve(bool (& board)[max_rows][max_cols], std::string (& lines)[max_rows],
int rows, int cols, int N, int & num_sol, int cnt = 0, int start_i = 0,
int start_j = 0, int depth = 0) {
if (cnt >= N) {
Output(board, lines, rows, cols, false);
// Увеличиваем счётчик числа решений.
++num_sol;
return;
}
// Обходим всю доску, начиная с позиции последнего ферзя.
for (int i = start_i; i < rows; ++i)
for (int j = i == start_i ? start_j : 0; j < cols; ++j) {
bool attacked = false;
// Цикл по k проверяет атакована ли позиция [i][j]
for (int k = 0; k < (rows > cols ? rows : cols); ++k)
if (
// Есть ли атака по горизонтали
k < cols && k != j && board[i][k] ||
// Атака по вертикали
k < rows && k != i && board[k][j] ||
// Атака по главной диагонали
k < rows && k != i && 0 <= j - i + k &&
j - i + k < cols && board[k][j - i + k] ||
// Атака по второстепенной диагонали
k < rows && k != i && 0 <= j + i - k &&
j + i - k < cols && board[k][j + i - k]
) {
// Ферзь в позиции [i][j] под атакой.
attacked = true;
break;
}
if (attacked)
continue;
// Позиция [i][j] не под атакой, потому ставим ферзя
board[i][j] = true;
// Рекурисвный спуск для расстановки следующего ферзя
Solve(board, lines, rows, cols, N, num_sol, cnt + 1, i, j + 1, depth + 1);
// Бэктрэкинг, удаляем прошлого установленного ферзя
board[i][j] = false;
}
if (depth == 0)
Output(board, lines, rows, cols, true);
}
// Функция для вывода решений.
void Output(bool (& board)[max_rows][max_cols], std::string (& lines)[max_rows],
int rows, int cols, bool last) {
// Вывод решения в консоль. Поставить тут if (0) если не нужно выводить доски в консоль.
if (1) {
if (!last) {
// Добавление одной доски к текущим строкам.
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j)
lines[i].push_back(board[i][j] ? 'Q' : '.');
// Символ | в качестве разделителя между досок.
lines[i] += "|";
}
}
// Если длина строк превысила ширину консоли (70), то выводим строки и разделитель.
if (lines[0].size() >= 70 || last && !lines[0].empty()) {
for (int i = 0; i < rows; ++i)
std::cout << lines[i] << std::endl;
for (int j = 0; j < lines[0].size(); ++j)
std::cout << (lines[0][j] == '|' ? '+' : '-');
std::cout << std::endl;
// Очищаем строки для следующих выводов досок.
for (int i = 0; i < rows; ++i)
lines[i].clear();
}
}
}
int main() {
// Входные параметры, rows - число рядов доски, cols - число столбцов
// N - число ферзей которые нужно расставить
int const rows = 8, cols = 8, N = 8;
// Заполняем пустыми значениями доску размером [rows][cols]
bool board[max_rows][max_cols] = {};
std::string lines[max_rows] = {};
// Ответ, число решений
int num_sol = 0;
// Запускаем бэк-трэкинг поиск решений.
Solve(board, lines, rows, cols, N, num_sol);
// Вывод ответа.
std::cout << "Number of solutions: " << num_sol << std::endl;
}
The conclusion of the console is the same as in Part One.Part 3There have been time constraints, and only 70 per cent of the tests were time-consuming from Part Two. Decided to make significant improvements.Instead of an internal cycle, k marked the employed verticals and diagons with bool-massivities.After the k-cycle has been removed, the rate of the programme should be about to increase. 40-50 times♪Update♪ Two more optimizations have just been made - (1) an early exit if the free rows or columns are not sufficient for the remaining areas, (2) the collection of free columns in a separate set to speed up the internal cycle several times. j♪ Both these optimizations are still 3-5 speed things up. https://godbolt.org/z/KK6qGPK6q #include <iostream>
#include <string>
#define MAX(a, b) ((a) >= (b) ? (a) : (b))
// Максимальное допустимое число рядов и колонок на доске
enum { max_rows = 32, max_cols = 32, max_max_rows_cols = MAX(max_rows, max_cols) };
// Декларирование функции Output, определённой ниже.
void Output(bool (& board)[max_rows][max_cols], std::string (& lines)[max_rows],
int rows, int cols, bool last);
// Рекурсивная функция для решения бэк-трэкингом.
// board - доска, board[i][j] == true если стоит ферзь в [i][j], иначе false.
// lines - вспомогательный массив для сбора выводимых в консоль строк.
// N - количество ферзей, cnt - сколько ферзей уже удалось расставить
// (start_i, start_j) - с какой позиции пытаться расставлять следующего ферзя
void Solve(bool (& board)[max_rows][max_cols], std::string (& lines)[max_rows],
bool (& busy_cols)[max_cols], bool (& busy_diagA)[2 * max_max_rows_cols],
bool (& busy_diagB)[2 * max_max_rows_cols],
int rows, int cols, int N, int & num_sol, int cnt = 0, int start_i = 0, int depth = 0) {
if (cnt >= N) {
Output(board, lines, rows, cols, false);
// Увеличиваем счётчик числа решений.
++num_sol;
return;
}
int const max_rows_cols = MAX(rows, cols);
// Больше не хватаят свободных рядов для расстановки оставшихся ферзей.
if (rows - start_i < N - cnt)
return;
// Выписываем все свободные столбцы, нам это потом даст ускорение.
int avail_cols[max_cols];
int avail_cols_cnt = 0;
for (int j = 0; j < cols; ++j)
if (!busy_cols[j]) {
avail_cols[avail_cols_cnt] = j;
++avail_cols_cnt;
}
// Больше не хватаят свободных столбцов для расстановки оставшихся ферзей.
if (avail_cols_cnt < N - cnt)
return;
// Обходим всю доску, начиная со следующего ряда после последнего ферзя.
for (int i = start_i; i < rows; ++i)
for (int jj = 0; jj < avail_cols_cnt; ++jj) {
int const j = avail_cols[jj];
// Пропускаем занаятые диагонали. Вертикаль уже не надо проверять.
if (busy_diagA[max_rows_cols + j - i] || busy_diagB[j + i])
continue;
// Больше проверок атаки не нужно.
// Позиция [i][j] не под атакой, потому ставим ферзя
board[i][j] = true;
// Помечаем j-й столбец занятым.
busy_cols[j] = true;
// Помечаем главную диагональ занятой.
busy_diagA[max_rows_cols + j - i] = true;
// Помечаем второстепенную диагональ занятой.
busy_diagB[j + i] = true;
// Рекурисвный спуск для расстановки следующего ферзя
Solve(board, lines, busy_cols, busy_diagA, busy_diagB,
rows, cols, N, num_sol, cnt + 1, i + 1, depth + 1);
// Бэктрэкинг, удаляем прошлого установленного ферзя
board[i][j] = false;
// Убираем пометки вертикали, и диагоналей.
busy_cols[j] = false;
busy_diagA[max_rows_cols + j - i] = false;
busy_diagB[j + i] = false;
}
if (depth == 0)
Output(board, lines, rows, cols, true);
}
// Функция для вывода решений.
void Output(bool (& board)[max_rows][max_cols], std::string (& lines)[max_rows],
int rows, int cols, bool last) {
// Вывод решения в консоль. Поставить тут if (0) если не нужно выводить доски в консоль.
if (1) {
if (!last) {
// Добавление одной доски к текущим строкам.
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j)
lines[i].push_back(board[i][j] ? 'Q' : '.');
// Символ | в качестве разделителя между досок.
lines[i] += "|";
}
}
// Если длина строк превысила ширину консоли (70), то выводим строки и разделитель.
if (lines[0].size() >= 70 || last && !lines[0].empty()) {
for (int i = 0; i < rows; ++i)
std::cout << lines[i] << std::endl;
for (int j = 0; j < lines[0].size(); ++j)
std::cout << (lines[0][j] == '|' ? '+' : '-');
std::cout << std::endl;
// Очищаем строки для следующих выводов досок.
for (int i = 0; i < rows; ++i)
lines[i].clear();
}
}
}
int main() {
// Входные параметры, rows - число рядов доски, cols - число столбцов
// N - число ферзей которые нужно расставить
int const rows = 8, cols = 8, N = 8;
// Заполняем пустыми значениями доску размером [rows][cols]
bool board[max_rows][max_cols] = {};
std::string lines[max_rows] = {};
// Следующие массивы указывают, заняты ли вертикаль и диагонали.
bool busy_cols[max_cols] = {};
bool busy_diagA[2 * max_max_rows_cols] = {};
bool busy_diagB[2 * max_max_rows_cols] = {};
// Ответ, число решений
int num_sol = 0;
// Запускаем бэк-трэкинг поиск решений.
Solve(board, lines, busy_cols, busy_diagA, busy_diagB, rows, cols, N, num_sol);
// Вывод ответа.
std::cout << "Number of solutions: " << num_sol << std::endl;
}
The withdrawal of the consoles is like Part One.