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