0

I have this code for solving eight queens problem. There are 92 solutions but there are only 12 unique solutions by rotating/inverting. I cant seem to figure out how to make the program show only 12 unique solutions. Can someone help me getting that code?

#include <iostream>

using namespace std;

class ChessBoard {
public:
    ChessBoard();    // 8 x 8 chessboard;
    ChessBoard(int); // n x n chessboard;
    void findSolutions();
private:
    const bool available;
    const int squares, norm;
    bool *column, *leftDiagonal, *rightDiagonal;
    int  *positionInRow, howMany;
    void putQueen(int);
    void printBoard(ostream&);
    void initializeBoard();
};

ChessBoard::ChessBoard() : available(true), squares(8), norm(squares-1) {
    cout <<"squares: " << squares << endl;
    initializeBoard();
}
ChessBoard::ChessBoard(int n) : available(true), squares(n), norm(squares-1) {
    cout <<"squares: " << squares << endl;
    initializeBoard();
}
void ChessBoard::initializeBoard() {
    register int i;
    column = new bool[squares];
    positionInRow = new int[squares];
    leftDiagonal  = new bool[squares*2 - 1];
    rightDiagonal = new bool[squares*2 - 1];
    for (i = 0; i < squares; i++)
        positionInRow[i] = -1;
    for (i = 0; i < squares; i++)
        column[i] = available;
    for (i = 0; i < squares*2 - 1; i++)
        leftDiagonal[i] = rightDiagonal[i] = available;
    howMany = 0;
}
void ChessBoard::printBoard(ostream& out) 
{
    cout << "Solution # " <<howMany<< endl;
    for (int row = 0; row < squares; row++)
    {
        out << "(" << row <<" , " << positionInRow[row] << ")\n";
    }
    cout << endl;
}
void ChessBoard::putQueen(int row) {
    for (int col = 0; col < squares; col++)
        if (column[col] == available &&
            leftDiagonal [row+col] == available &&
            rightDiagonal[row-col+norm] == available) {
            positionInRow[row] = col;
            column[col] = !available;
            leftDiagonal[row+col] = !available;
            rightDiagonal[row-col+norm] = !available;
            if (row < squares-1)
                putQueen(row+1);
            else
            {
                howMany++;
                printBoard(cout);
            }
            column[col] = available;
            leftDiagonal[row+col] = available;
            rightDiagonal[row-col+norm] = available;
        }
}
void ChessBoard::findSolutions() {
    putQueen(0);
    cout << howMany << " solutions found.\n";
}

int main() {
    ChessBoard board;
    board.findSolutions();
    system("pause");
    return 0;
}
2
Contributors
1
Reply
2
Views
6 Years
Discussion Span
Last Post by raptr_dflo
0

Each unique solution has 4 possible rotations (original, 90 degrees, 180 degrees, 270 degrees) and for each of those, 3 possible inversion/reflection states (original, reflected left-to-right, reflected top-to-bottom [*]). Once you have one of your solutions (knowing which column the queen is in for each row), how would you come up with rotated/inverted versions of that solution, to compare against saved unique solutions? And how would you save a solution as a unique one, once you determined it wasn't a rotated/inverted version of an previously-found solution?

[*] Note that reflecting a solution left-to-right AND top-to-bottom is the same as rotating it 180 degrees. As a result, reflecting a solutions left-to-right is the same as reflecting its 180-degree rotation top-to-bottom, and vice versa, so I'm pretty sure that makes 8 non-overlapping states for a single unique solution.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.