#include <iostream>
#include <cstdio>
#include <ctime>
#include <cmath>

using namespace std;

void queen(int** array, int row, FILE* fp);
bool isAvailable(int** array, int y, int x);
bool isResult(int** array);

int main(int arg, char** argv) {
        int** array;
        
        // 分配空間
        array = new int*[8];
        for (int i = 0; i < 8; i++) {
                array[i] = new int[8];
        }
        
        // 初始化皇后狀態(tài)
        for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                        array[i][j] = 0;
                }
        }
        
        FILE* fp = fopen("data.txt", "w");
        queen(array, 0, fp);
        fclose(fp);
        
        // 釋放空間
        for (int i = 0; i < 8; i++) {
                delete[] array[i];
        }
        delete array;
        array = NULL;

        return 0;
}

void queen(int** array, int row, FILE* fp) {
        static int size = 1;
        if (row > 7) {
                return;
        }
        for (int j = 0; j < 8; j++) {
                // 如果合法
                if (isAvailable(array, row, j)) {
                        array[row][j] = 1;
                        
                        // 當(dāng)前位置合法，賦值后，進(jìn)入下一行
                        queen(array, row + 1, fp);

                        // 如果退回來后是結(jié)果，則打印出來
                        if (isResult(array)) {
                                // 把結(jié)果寫入文件
                                fputc('\n', fp);
                                fputs("***********************************", fp);
                                fprintf(fp, " %d ", size++);
                                fputs("***********************************", fp);
                                fputc('\n', fp);
                                for (int m = 0; m < 8; m++) {
                                        for (int n = 0; n < 8; n++) {
                                                if (array[m][n] == 1) {
                                                        fputc('#', fp);
                                                        fputc(' ', fp);
                                                        fputc(' ', fp);
                                                } else {
                                                        fputc('O', fp);
                                                        fputc(' ', fp);
                                                        fputc(' ', fp);
                                                }
                                        }
                                        fputc('\n', fp); 
                                }

                        }
                        array[row][j] = 0;

                }
        }
}

bool isAvailable(int** array, int row, int column) { // 第row行，column列
        int i, j;

        // 檢查row行
        for (i = 0; i < 8; i++) {
                if (array[row][i] != 0) {
                        return false;
                }
        }

        // 檢columnx列
        for (j = 0; j < 8; j++) {
                if (array[j][column] != 0) {
                        return false;
                }
        }

        // 檢查對(duì)角向左上
        i = row;
        j = column;
        while (i >= 0 && j >= 0) {
                if (array[i][j] != 0) {
                        return false;
                }
                i--;
                j--;
        }

        // 檢查對(duì)角向右上
        i = row;
        j = column;
        while (i >= 0 && j < 8) {
                if (array[i][j] != 0) {
                        return false;
                }
                i--;
                j++;
        }

        // 檢查對(duì)角向左下
        i = row;
        j = column;
        while (i < 8 && j >= 0) {
                if (array[i][j] != 0) {
                        return false;
                }
                i++;
                j--;
        }

        // 檢查對(duì)角向右下
        i = row;
        j = column;
        while (i < 8 && j < 8) {
                if (array[i][j] != 0) {
                        return false;
                }
                i++;
                j++;
        }

        return true;
}

bool isResult(int** array) {
        int size = 0; // 皇后個(gè)數(shù)

        // 統(tǒng)計(jì)皇后個(gè)數(shù)
        for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                        if (array[i][j] != 0) {
                                size++;
                        }
                }
        }

        // 沒有８?jìng)€(gè)皇后，說明不是結(jié)果

       // 有8個(gè)皇后,因?yàn)槊總€(gè)皇后的放置都是在合法位置, 所以只需要簡單的計(jì)算皇后個(gè)數(shù)就知道是不是結(jié)果.
        if (size != 8) {
                return false;
        }

        return true;
}