八皇后算法:
- 规定每行放置一个皇后,从第一列开始逐个放
- 1.flag[col]表示n列能否放置皇后,1表示可以放置,0表示无法放置;
- 2.place[row]表示第row行放置的皇后列号;
- 3.d1[0…14]为(row,col)的上对角线是否被占领,row-col+7相同的在同一对角线,1表示可以被占领,0表示不可以;
- 4.d2[0…14]同理为下对角线,row+col相同的在同一次对角线
上对角线图
d1[row-col+7]等效于d1[0…14],将图中的负值转化为正值,构造成同一数组,从而相同值为同一上对角线
下对角线图
d2[row+col]等效为d1[0…14],col+row值等于图中方块值,从而相同值为同一下对角线。
因此,判断(row,col)是否可以放皇后,就要看(flag[col]&&d1[row-col]&&d2[row+col])是否成立,即col列没有皇后,(row,col)的上下对角线都没有皇后。(为啥不判断行上是否有皇后?因为我们规定每一行开始放皇后,放完第row行后,只考虑row+1行,以此类推)
#include<stdio.h>
int flag[8] = {1,1,1,1,1,1,1,1};
int place[8] = { 0 };
int d1[15] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
int d2[15] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
int num = 0;//八皇后可以放置的可能性
void print() {
int row,col;
int table[8][8] = { 0 };
printf("No.%d\n", num);
for (row = 0; row < 8; row++) {
table[row][place[row]] = 1;
}
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
printf("%d ", table[i][j]);
}
printf("\n");
}
printf("================\n");
}
void generate(int row) {
int col;
if (row > 7) {
num++;
print();
return;
}
for (col = 0; col < 8; col++) {
if (flag[col] && d1[row - col + 7] && d2[row + col]) {
place[row] = col;
d1[row - col + 7] = 0;
d2[row + col] = 0;
flag[col] = 0;
generate(row + 1);
flag[col] = 1;
d1[row - col + 7] = 1;
d2[row + col] = 1;
}
}
}
void main() {
generate(0);
}