Помогите, пожалуйста, написать код или переделать код, который будет считать количество отказов при расстановке 8 ферзей.
Буду благодарна за помощь.
Спасибо тем, кто откликнется на мою просьбу.
Вот на всякий случай условие задачи : В программе о восьми ферзях (рекурсивной) подсчитайте, сколько было сделано возвратов назад.
Вот код.
| Код |
#include <iostream>
using namespace std;
const int n = 8;
int board[n][n]; // доска
void setQueen(int i, int j)
{
for (int x = 0; x < n; ++x)
{
++board[x][j]; //горизонтали
++board[i][x]; //вертикали
int foo;
foo = j - i + x; //диагонали
if (foo >= 0 && foo <n)
++board[x][foo];
foo = j + i - x;//другая диагонали
if (foo >= 0 && foo <n)
++board[x][foo];
}
board[i][j] = -1; //означает стоит ферзь
}
void resetQueen(int i, int j)
{
for (int x = 0; x < n; ++x)
{
--board[x][j];
--board[i][x];
int foo;
foo = j - i + x;
if (foo >= 0 && foo <n)
--board[x][foo];
foo = j + i - x;
if (foo >= 0 && foo <n)
--board[x][foo];
}
board[i][j] = 0;
}
bool tryQueen(int i)
{
bool result = false; //
for (int j = 0; j < n; ++j) {
if (board[i][j] == 0) // если ячейка, которою проверяем = 0, то можно ставить королеву
{
setQueen(i, j);
if (i == n - 1) // если столбец равен 7, то всех королев поставили
result = true;
else // иначе пробуем поставить ферзя на следующий столбец
{
if (!(result = tryQueen(i + 1))) // если не удалось поставить в столбец ферзя
resetQueen(i, j); // убираем ферзя с позиции [i][j]
}
}
if (result)
break;
}
return result;
}
int main()
{
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
board[i][j] = 0;
tryQueen(0);
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (board[i][j] == -1)
cout << "[F]";
else
cout << " * ";
}
cout << endl;
}
}
|
|