FAX Lab 4 8_Queens

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

#define Q "Q"
#define Fil " "

struct cell {
    int x, y;
    int imp;
    cell() { x = -1; y = -1; imp = 0; }
};

cell toDraw[8];

inline bool draw_now(int x, int y)
{
    for (int i = 0; i < 8; i++)
    if (toDraw[i].x == x && toDraw[i].y == y) return true;
    return false;
}

void draw_board()
{
    int funcX = 0, funcY = 0;

    // Top board edge
    cout << "\n\t";

    cout << (char)218;
    for (int i = 0; i < 7; i++)
        cout << (char)196 << (char)194;
    cout << (char)196 << (char)191;

    cout << "\n\t";

    for (int i = 0; i < 7; i++) {
        // Base of every string
        cout << (char)179;
        for (int i = 0; i < 7; i++) {
            if (draw_now(funcX, funcY)) cout << Q;
            else cout << Fil;
            cout << (char)179;
            funcX++;
        }
        if (draw_now(funcX, funcY)) cout << Q;
        else cout << Fil;
        cout << (char)179;
        funcX = 0;

        cout << "\n\t";

        cout << (char)195;
        for (int i = 0; i < 7; i++)
            cout << (char)196 << (char)197;
        cout << (char)196 << (char)180;

        cout << "\n\t";
        funcY++;
    }

    // Last string
    cout << (char)179;
    for (int i = 0; i < 7; i++) {
        if (draw_now(funcX, funcY)) cout << Q;
        else cout << Fil;
        cout << (char)179;
        funcX++;
    }
    if (draw_now(funcX, funcY)) cout << Q;
    else cout << Fil;
    cout << (char)179;

    cout << "\n\t";

    // Bottom board edge
    cout << (char)192;
    for (int i = 0; i < 7; i++)
        cout << (char)196 << (char)193;
    cout << (char)196 << (char)217;

    cout << "\n";
}

bool isAllowed(const cell &forCh)
{
    int x = forCh.x, y = forCh.y;
    // Up
    while (x >= 0 && x < 8 && y >= 0 && y < 8)
    if (draw_now(x, y++)) return false;

    x = forCh.x;
    y = forCh.y;

    // Down
    while (x >= 0 && x < 8 && y >= 0 && y < 8)
    if (draw_now(x, y--)) return false;

    x = forCh.x;
    y = forCh.y;

    // Left
    while (x >= 0 && x < 8 && y >= 0 && y < 8)
    if (draw_now(x--, y)) return false;

    x = forCh.x;
    y = forCh.y;

    // Right
    while (x >= 0 && x < 8 && y >= 0 && y < 8)
    if (draw_now(x++, y)) return false;

    x = forCh.x;
    y = forCh.y;

    // Diag. left & up
    while (x >= 0 && x < 8 && y >= 0 && y < 8)
    if (draw_now(x--, y++)) return false;

    x = forCh.x;
    y = forCh.y;

    // Diag. right & up
    while (x >= 0 && x < 8 && y >= 0 && y < 8)
    if (draw_now(x++, y++)) return false;

    x = forCh.x;
    y = forCh.y;

    // Diag. left & down
    while (x >= 0 && x < 8 && y >= 0 && y < 8)
    if (draw_now(x--, y--)) return false;

    x = forCh.x;
    y = forCh.y;

    // Diag. right & down
    while (x >= 0 && x < 8 && y >= 0 && y < 8)
    if (draw_now(x++, y--)) return false;

    return true;
}

int ansLine = 0;

class answers {
    cell ans[92][8];
public:
    answers() {
        for (int i = 0; i < 92; i++)
        for (int j = 0; j < 8; j++) {
            ans[i][j].x = -1;
            ans[i][j].y = -1;
            ans[i][j].imp = 0;
        }
    }
    void push_ans(cell *ptr) {
        bool coinc = false;

        for (int i = 0; i < ansLine; i++) {
            for (int m = 0; m < 8; m++) {
                if (ptr[m].x == ans[i][m].x && ptr[m].y == ans[i][m].y)
                    coinc = true;
                else {
                    coinc = false;
                    break;
                }
            }
            if (coinc) break;
        }
        if (!coinc) {
            for (int n = 0; n < 8; n++) {
                ans[ansLine][n].x = ptr[n].x;
                ans[ansLine][n].y = ptr[n].y;
            }
            ansLine++; // max == 91(ansLine == 92)
        }
    }
    void print_ans() {
        if (!ansLine) {
            cout << "\nNo results!\n";
            return;
        }
        for (int i = 0; i < ansLine; i++) {
            for (int j = 0; j < 8; j++) {
                toDraw[j].x = ans[i][j].x;
                toDraw[j].y = ans[i][j].y;
            }
            if (ansLine) draw_board();
        }

    }
} ansList;

int main()
{
    cell board[8][8];

    // Add information about every cell
    for (int i = 0; i < 8; i++)
    for (int j = 0; j < 8; j++) {
        board[i][j].x = j;
        board[i][j].y = i;
        board[i][j].imp += 15;
        i <= j ? board[i][j].imp += i : board[i][j].imp += j;
        (7 - i) <= j ? board[i][j].imp += (7 - i) : board[i][j].imp += j;
        (7 - i) <= (7 - j) ? board[i][j].imp += (7 - i) : board[i][j].imp += (7 - j);
        i <= (7 - j) ? board[i][j].imp += i : board[i][j].imp += (7 - j);
    }

    int impMin = 22, solutions = 0, drwIndx = 0;
    int startPosA = 0, startPosB = 0, startPosC = 0, startPosD = 0,
        startPosE = 0, startPosF = 0, startPosG = 0;
    register int i = 0, j = 0;
    double startCl, endCl;

    cout << "Search for solution...\n";

    startCl = clock();
    while (startPosG < 8) {
        while (startPosF < 8) {
            while (startPosE < 8) {
                while (startPosD < 8) {
                    while (startPosC < 8) {
                        while (startPosB < 8) {
                            while (startPosA < 8) {
                                for (i = 0; i < 8; i++) { // Bust starts here
                                    while (j < 8) {
                                        if (i == 0 && j == 0) j = startPosA;
                                        if (i == 1 && j == 0) j = startPosB;
                                        if (i == 2 && j == 0) j = startPosC;
                                        if (i == 3 && j == 0) j = startPosD;
                                        if (i == 4 && j == 0) j = startPosE;
                                        if (i == 5 && j == 0) j = startPosF;
                                        if (i == 6 && j == 0) j = startPosG;
                                        //if (board[i][j].imp == 22) {
                                        if (isAllowed(board[i][j])) {
                                            toDraw[drwIndx++] = board[i][j];
                                            continue;
                                        }
                                        //}
                                        j++;
                                    }
                                    j = 0;
                                }
                                if (drwIndx == 8) { // How many results must be found
                                    ansList.push_ans(toDraw);
                                    solutions++;
                                    /*cout << solutions << ") ";
                                    for (int i = 0; i < 8; i++) {
                                    cout << "[" << toDraw[i].x << ", " << toDraw[i].y << "]  ";
                                    }
                                    cout << "\n\n";*/
                                }
                                for (int p = 0; p < 8; p++) {
                                    toDraw[p].x = -1;
                                    toDraw[p].y = -1;
                                    toDraw[p].imp = 0;
                                }
                                drwIndx = 0;
                                startPosA++;
                            }
                            startPosA = 0;
                            startPosB++;
                        }
                        startPosA = 0;
                        startPosB = 0;
                        startPosC++;
                    }
                    startPosA = 0;
                    startPosB = 0;
                    startPosC = 0;
                    startPosD++;
                }
                startPosA = 0;
                startPosB = 0;
                startPosC = 0;
                startPosD = 0;
                startPosE++;
            }
            startPosA = 0;
            startPosB = 0;
            startPosC = 0;
            startPosD = 0;
            startPosE = 0;
            startPosF++;
        }
        startPosA = 0;
        startPosB = 0;
        startPosC = 0;
        startPosD = 0;
        startPosE = 0;
        startPosF = 0;
        startPosG++;
    }
    endCl = clock();

    ansList.print_ans();
    cout << "\nFound " << solutions << " solutions\nEstimated " << (endCl - startCl) / CLOCKS_PER_SEC << " seconds\n\n";
    cout << "Unique placement: " << ansLine << "\n\n";

    system("pause");
    return 0;
}