八皇后问题C语言解法

时间:2023-12-06 11:01:38

偶遇八皇后问题,随即自己写了一个仅供参考

#include<stdio.h>
#include<math.h>
#define SIZE 8 void Circumsribe(int(*checkerboard)[SIZE], int x, int y, int flag);
int EightQueen(int(*checkerboard)[SIZE], int num, int begin_x, int begin_y); void main()
{
int checkerboard[SIZE][SIZE] = {}, result; result = EightQueen(checkerboard, , , );
printf_s("%d\n", result);
} //划定或解除皇后攻击范围
void Circumsribe(int(*checkerboard)[SIZE], int x, int y, int flag)
{
int i, j; for (i = ; i < SIZE; i++)
{
for (j = ; j < SIZE; j++)
{
if (flag == )
{
//flag为1表示放置皇后,划定攻击范围
checkerboard[i][j] = (i == x || j == y || abs(j - y) == abs(i - x)) ? checkerboard[i][j] + : checkerboard[i][j];
}
else
{
//flag为0表示移走皇后,解除攻击范围
checkerboard[i][j] = (i == x || j == y || abs(j - y) == abs(i - x)) ? checkerboard[i][j] - : checkerboard[i][j];
}
}
}
} //num表示放置皇后的序号,begin_x与begin_y表示此序号皇后放置的坐标
//返回值表示余下num个皇后有多少种允许的摆法
int EightQueen(int(*checkerboard)[SIZE], int num, int begin_x, int begin_y)
{
int x, y, sum = ; //sum理解为皇后在不同位置上允许的摆法总和 if (num <= || num > SIZE || begin_x < || begin_y < || begin_x > SIZE || begin_y > SIZE)
{
//数据非法则返回0
return ;
}
else if (num == )
{
//若只有1个皇后,则从指定的(begin_x,begin_y)开始,往后统计摆法
for (x = begin_x; x < SIZE; x++)
{
for (y = (x == begin_x ? begin_y : ); y < SIZE; y++)
{
sum = checkerboard[x][y] == ? sum + : sum;
}
}
return sum;
}
else
{
//若多于1个皇后,则先将多余的皇后从指定的(begin_x,begin_y)开始摆好,在此基础上,统计最后1个皇后的摆法
//引入(begin_x,begin_y)是为了避免重复放置,每个皇后的位置都应该从上个皇后的位置处开始,否则有重复
for (x = begin_x; x < SIZE; x++)
{
for (y = (x == begin_x ? begin_y : ); y < SIZE; y++)
{
if (checkerboard[x][y] == )
{
Circumsribe(checkerboard, x, y, ); //若此(x,y)处可放置皇后,则划定这个皇后的攻击范围
sum = sum + EightQueen(checkerboard, num - , x, y); //在此基础上确定余下皇后的摆法
Circumsribe(checkerboard, x, y, ); //将此皇后移到下个位置前需要先解除其攻击范围
}
}
}
return sum;
}
}