C语言八皇后问题

八皇后算法:

  • 规定每行放置一个皇后,从第一列开始逐个放
  • 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],将图中的负值转化为正值,构造成同一数组,从而相同值为同一上对角线
C语言八皇后问题下对角线图
d2[row+col]等效为d1[0…14],col+row值等于图中方块值,从而相同值为同一下对角线。
C语言八皇后问题因此,判断(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);
}
上一篇:找规律填数字(难AC,细节多)


下一篇:270【毕设课设】基于51单片机的人体热释传感器自动门控制系统设计