#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];
}
// 初始化皇后狀態
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;
// 當前位置合法，賦值后，進入下一行
queen(array, row + 1, fp);
// 如果退回來后是結果，則打印出來
if (isResult(array)) {
// 把結果寫入文件
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;
}
}
// 檢查對角向左上
i = row;
j = column;
while (i >= 0 && j >= 0) {
if (array[i][j] != 0) {
return false;
}
i--;
j--;
}
// 檢查對角向右上
i = row;
j = column;
while (i >= 0 && j < 8) {
if (array[i][j] != 0) {
return false;
}
i--;
j++;
}
// 檢查對角向左下
i = row;
j = column;
while (i < 8 && j >= 0) {
if (array[i][j] != 0) {
return false;
}
i++;
j--;
}
// 檢查對角向右下
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; // 皇后個數
// 統計皇后個數
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (array[i][j] != 0) {
size++;
}
}
}
// 沒有８個皇后，說明不是結果
// 有8個皇后,因為每個皇后的放置都是在合法位置, 所以只需要簡單的計算皇后個數就知道是不是結果.
if (size != 8) {
return false;
}
return true;
}