#define MAXN 16
/* 定义栈结点,表示一个皇后的位置 */
typedef struct node
{
int row; /* 行 */
int col; /* 列 */
int tag; /* 布局标记 */
} NODE;
/* 进行皇后问题处理
* 参数 n 表示棋盘的大小
* 返回找到的答案个数
*/
int queens(int n)
{
/* 定义解答树堆栈 */
NODE stack[MAXN * MAXN];
/* 栈顶索引,初始化为 -1(栈空) */
int top = -1;
/* 攻击标志,表示同一列及对角线上是否有皇后 */
int col[MAXN] = {0},
md[2 * MAXN - 1] = {0},
sd[2 * MAXN - 1] = {0};
int str, stc, i;
/* 解决方案个数 */
int scount = 0;
/* 初始化栈 */
for(i = 0; i < n; i++)
{
stack[++top].row = 0;
stack[top].col = n - 1 - i;
stack[top].tag = 0;
}
/* 以行为单位开始回溯 */
while(top >= 0)
{
str = stack[top].row;
stc = stack[top].col;
if(stack[top].tag == 0)
{
/* 如果栈顶元素的位置并没有确立 */
if(col[stc] || md[str - stc + n - 1] || sd[str + stc])
{
/* 如果同一列或同一对角线上已有皇后,则退回 */
top--;
}
else
{
/* 占据这个位置,设置列、对角线上的攻击标志 */
col[stc] = 1;
md[str - stc + n - 1] = 1;
sd[str + stc] = 1;
/* 标记栈顶元素的 tag 值 */
stack[top].tag = 1;
if(str == n - 1)
{
/* 如果此时已经到达最后一行
* 则表示此种布局方法是成功的
* 输出相关信息
*/
printf("A solution is:\n");
for(i = 0; i <= top; i++)
{
if(stack[i].tag)
printf("%4d,%3d;", stack[i].row, stack[i].col);
}
printf("\n");
/* 解决方案数增 1 */
scount++;
}
else
{
/* 如果此时没有到达最后一行
* 则继续进栈并初始化
*/
for(i = 0; i < n; i++)
{
stack[++top].row = str + 1;
stack[top].col = n - 1 - i;
stack[top].tag = 0;
}
}
}
}
else
{
/* 如果栈顶元素位置已确立
* 则栈顶元素出栈,初始化攻击标志
* 准备继续寻找其它的方法
*/
col[stc] = 0;
md[str - stc + n - 1] = 0;
sd[str + stc] = 0;
top--;
}
}
return(scount);
}
void main()
{
int n;
int scount = 0;
printf("\nInput n (n <= 15) = ");
scanf("%d", &n);
if(n > MAXN - 1)
{
printf("### n > %d ###\n", MAXN - 1);
exit(1);
}
scount = queens(n);
printf("%d sulotions found.\n", scount);
getch();
}
评论0
最新资源