Задача о 8 ферзях, но с исключением симметрий на c++
В обычной задаче о 8 ферзях просто выводится 92 решения, но мне задали сделать так, чтобы в задаче выводились только не симметричные решения, т. е:
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .
Result #1
симметричен с по вертикали:
. . . . . . . Q
. . . Q . . . .
Q . . . . . . .
. . Q . . . . .
. . . . . Q . .
. Q . . . . . .
. . . . . . Q .
. . . . Q . . .
Result #92
и с по горизонтали:
. . . Q . . . .
. Q . . . . . .
. . . . . . Q .
. . Q . . . . .
. . . . . Q . .
. . . . . . . Q
. . . . Q . . .
Q . . . . . . .
Result #33
У меня даже теоретически нет понятия, как это реализовать, а методом проб и ошибок я не успею сдать вовремя. Очень буду рад помощи.
Так же, вот весь код с выводом всех решений:
#include "stdafx.h"
#include <iostream>
using namespace std;
const int SIZE = 8;
int board[SIZE][SIZE];
int results_count = 0;
void showBoard()
{
for(int a = 0; a < SIZE; ++a)
{
for(int b = 0; b < SIZE; ++b)
{
cout << ((board[a][b]) ? "Q " : ". ");
}
cout << endl;
}
}
bool tryQueen(int a, int b)
{
for(int i = 0; i < a; ++i)
{
if(board[i][b])
{
return false;
}
}
for(int i = 1; i <= a && b-i >= 0; ++i)
{
if(board[a-i][b-i])
{
return false;
}
}
for(int i = 1; i <= a && b+i < SIZE; i++)
{
if(board[a-i][b+i])
{
return false;
}
}
return true;
}
void setQueen(int a)
{
if(a == SIZE)
{
showBoard();
cout << "Result #" << ++results_count << endl << endl;
return;
}
for(int i = 0; i < SIZE; ++i)
{
if(tryQueen(a, i))
{
board[a][i] = 1;
setQueen(a+1);
board[a][i] = 0;
}
}
return;
}
int main()
{
setQueen(0);
system("pause");
}
Источник: Stack Overflow на русском