//国际象棋“皇后”问题处理头文件
//国际象棋“皇后”问题的回溯算法
/**//*
作者：成晓旭
时间：2001年10月9日(17:35:38-18:00:00)
内容：完成“皇后”问题的程序序言部分
时间：2001年10月9日(14:00:00-15:00:00)
内容：完成“皇后”问题的程序序言部分
===================================================
问题描述:
在一个n*n的棋盘上放置n个不能互相捕捉的国际象棋“皇后”,
并输出所有合理的布局情况.(在国际象棋中,皇后可以沿着纵、横
及两条斜线共4个方向捕捉对手,可见,合适的解是在每行、每列及
在一条斜线上只能有一个皇后<皇后相互捕捉>)
编程思想:
算法描述:
{
输入棋盘大小值n;
m=0; //从空配置开始
notcatch=1; //空配置中皇后不能相互捕捉
do
{
if(notcatch)
{
if(m==n)
{
输出解;
调整(形成下一个候选解);
}
else
扩展当前候选解至下一列; //向前试探
}
else
调整(形成下一个候选解); //向后回溯
notcatch = 检查当前候选解的合理性
}while(m!=0)
}
*/
#include "stdlib.h"
#define MAXN 100
//全局变量及全局工作数组定义
int m,n,NotCatch;
int ColFlag[MAXN+1]; /**//*表示第i列的第ColFlag[i]行有皇后,(1:有;0:没有)*/
int RowFlag[MAXN+1]; /**//*RowFlag[i]:表示第i行没有皇后(1:没有;0:有)*/
int upBiasFlag[2*MAXN+1]; /**//*upBiasFlag[i]:表示第i条上斜线(右高左斜)没有皇后(1:没有;0:有)*/
int dnBiasFlag[2*MAXN+1]; /**//*dnBiasFlag[i]:表示第i条下斜线(左高右斜)没有皇后(1:没有;0:有)*/
//显示输入填写的数字
void ArrangeQueen()
...{
int i;
char answer;
printf("输入棋盘边格数：");
scanf("%d",&n);
for(i=0;i<=n;i++) /**//*设置程序初始状态*/
ColFlag[i] = 1;
for(i=0;i<=2*n;i++)
upBiasFlag[i] = dnBiasFlag[i] = 1;
m = 1;
ColFlag[1] = 1;
NotCatch = 1;
ColFlag[0] = 0;
do
...{
if(NotCatch)
...{
if(m==n)
...{
printf("列行");
for(i=1;i<=n;i++) /**//*找到可行解,输出*/
printf("%3d%3d ",i,ColFlag[i]);
printf("还要继续搜索吗(Q/q for Exit)？ ");
scanf("%c",&answer);
if(answer=='Q' || answer=='q')
exit(0);
while(ColFlag[m] == n)
...{
m--; /**//*清除第m-1列,第RowFlag[ColFlag[m-1]]行有皇后的标志*/
RowFlag[ColFlag[m]] = upBiasFlag[m+ColFlag[m]] = dnBiasFlag[n+m-ColFlag[m]] = 1;
}
ColFlag[m]++; /**//*调整第m列的皇后配置(扩展调整)*/
}
else
...{
/**//*设置第m列,第RowFlag[ColFlag[m-1]]行有皇后的标志*/
RowFlag[ColFlag[m]] = upBiasFlag[m+ColFlag[m]] = dnBiasFlag[n+m-ColFlag[m]] = 0;
ColFlag[++m] = 1; /**//*向前试探*/
}
}
else
...{
while(ColFlag[m]==n) /**//*向后回溯*/
...{
m--; /**//*清除第m-1列,第RowFlag[ColFlag[m-1]]行有皇后的标志*/
RowFlag[ColFlag[m]] = upBiasFlag[m+ColFlag[m]] = dnBiasFlag[n+m-ColFlag[m]] = 1;
}
ColFlag[m]++; /**//*调整第m列的皇后配置(回溯调整)*/
}
NotCatch = RowFlag[ColFlag[m]] && upBiasFlag[m+ColFlag[m]] && dnBiasFlag[n+m-ColFlag[m]];
}while(m!=0);
}
void dArrange_Queen_All(int k,int n)
...{
int i,j;
char answer;
for(i=1;i<=n;i++)
...{
if(RowFlag[i] && upBiasFlag[k+i] && dnBiasFlag[n+k-i])
...{
ColFlag[k] = i;
RowFlag[i] = upBiasFlag[k+i] = dnBiasFlag[n+k-i] = 0;
if(k==0)
...{
printf("列行");
for(j=1;j<=n;j++) /**//*找到可行解,输出*/
printf("%3d%3d ",i,ColFlag[i]);
printf("还要继续搜索吗(Q/q for Exit)？ ");
scanf("%c",&answer);
if(answer=='Q' || answer=='q')
exit(0);
}
else
dArrange_Queen_All(k+1,n);
RowFlag[i] = upBiasFlag[k+i] = dnBiasFlag[n+k-i] = 1;
}
}
}
void dArrangeQueenAll()
...{
int i;
printf("输入棋盘边格数：");
scanf("%d",&n);
for(i=0;i<=n;i++) /**//*设置程序初始状态*/
ColFlag[i] = 1;
for(i=0;i<=2*n;i++)
upBiasFlag[i] = dnBiasFlag[i] = 1;
dArrange_Queen_All(1,n);
}
免责声明：本文为网络用户发布，其观点仅代表作者个人观点，与本站无关，本站仅提供信息存储服务。文中陈述内容未经本站证实，其真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
