C语言题_2n皇后问题
2n皇后问题
试题
中考模拟试题doc幼小衔接 数学试题 下载云南高中历年会考数学试题下载N4真题下载党史题库下载
来自:程设09秋(徐)(程序
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
基础课(清华大学 徐明星老师、吴文虎老师)2009秋)
【问题描述】
给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和
n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白
皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法,n小于等于8。
【输入格式】
输入的第一行为一个整数n，表示棋盘的大小。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如
果一个整数为0，表示对应的位置不可以放皇后。 【输出格式】
输出一个整数，表示总共有多少种放法。
【样例输入1】
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
【样例输出1】
2
【样例输入2】
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
【样例输出2】
0
分析:
每行的Q的位置，保存在一个数组中Q[6]，Q[1]表示第一行q的列数。 从第一行开始1到(n+1)/2遍历
Q Q Q
接下去的每行每列遍历，并检测是否符合，
Q
Q
如果Q[1]=1,那么Q[2]==Q[1]，则不符合
Q
Q
如果Q[1]>Q[2]，检测Q[2]是否在Q[1]的135度线上, Q[1]+([2]-[1])?=Q[2]，Q1与Q2的
行差加上Q1的列值是否等于Q2的列值
Q
Q
如果Q[1]
char NN[9][9]; //棋盘，初始设为‘-’，1表示在棋盘格为空，Q表示放置皇后
-N行Q的列数,q[1]=3表示第一行的Q在第三列 int q[6]; //记录1
int Cheak(int line) //检测要添加的Q是否符合要求 {
int i;
for(i=1;i0)
{
if(q[i]-(line-i)==q[line])
return 0;
}
else
{
if(q[i]+(line-i)==q[line])
return 0;
}
}
return 1;
}
void Search(int line,int N)
{
int i,j,n;
if(line==N) //如果最后一行的Q已经存在，则打印棋盘
for(i=1;i<9;i++)
{
for(j=1;j<9;j++)
printf("%c",NN[i][j]);
printf("\n");
}
else //遍历此行，并通过检测查询下一行
{
line++;
for(i=1;i<=N;i++)
{
NN[line][i]='Q';
q[line]=i;
if(n=Cheak(line)>0)
{
Search(line,N);
}
NN[line][i]='1';
}
}
}
void Begin(int N) {
int i;
for(i=1;i<=(N+1)/2;i++)
{
q[1]=i;
NN[1][i]='Q';
Search(1,N);
NN[1][i]='1';
}
}
void main()
{
//初始
int N,i,j;
for(i=1;i<9;i++)
for(j=1;j<9;j++)
NN[i][j]='-';
printf("Start:(8*8)\n");
for(i=1;i<9;i++)
{
for(j=1;j<9;j++)
printf("%c",NN[i][j]);
printf("\n");
}
//输入N
scanf("%d",&N);
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
NN[i][j]='1';
printf("Now you choice N=%d:(%d*%d)\n",N,N,N);
for(i=1;i<9;i++)
{
for(j=1;j<9;j++)
printf("%c",NN[i][j]);
printf("\n");
}
//开始计算
Begin(N);
}
上述的代码中，只实现了棋盘的打印，并未统计放法的数量，通过Begin()函数，第一行只检测一半，因为另一半是对称的(为了提高效率)，然而题目要求是有0，1限制的，所以，为了实现上述要求，代码还应改动去掉对称，因为棋盘添加了0后便不是对称的了。 所有改动后的代码，还应多添加一个检测0
通过添加个数组q_num[9]来记录Q在第一行，第i列的放法数目
如:N=5，num[1]=1,num[2]=2,num[3]=3,num[4]=4,num[5]=5
那么放置两种皇后的总方法:1*(2+3+4+5)+2*(1+3+4+5)+……..+5*(1+2+3+4)(不要以为里面有重复，因为1列放白皇后和黑皇后是算两种情况的)
最终代码:
#include
char NN[9][9]; //棋盘，初始设为'-'，1表示在棋盘格为空，Q表示放置皇后
int q[6]; //记录1-N行Q的列数,q[1]=3表示第一行的Q在第三列 int num=0; //方法种类统计
int q_num[9]={0}; //统计记录Q在第一行，第i列的放法数目
int Cheak(int line) //检测要添加的Q是否符合要求
{
int i;
for(i=1;i0)
{
if(q[i]-(line-i)==q[line])
return 0;
}
else
{
if(q[i]+(line-i)==q[line])
return 0;
}
}
return 1;
}
void Search(int line,int N) {
int i,j,n;
if(line==N) //如果最后一行的Q已经存在，则打印棋盘 ,统计加一
{
num++;
/* for(i=1;i<9;i++)
{
for(j=1;j<9;j++)
printf("%c",NN[i][j]);
printf("\n");
} */
}
else //遍历此行，并通过检测查询下一行
{
line++;
for(i=1;i<=N;i++)
{
if(NN[line][i]=='0')
continue;
NN[line][i]='Q';
q[line]=i;
if(n=Cheak(line)>0)
{
Search(line,N);
}
NN[line][i]='1';
}
}
}
void Begin(int N) {
int i,qnum; //qnum用于临时记录num的数目，在遍历完第一行的
一个位置后，与新的num相减得出q_num[]
for(i=1;i<=N;i++)
{
qnum=num;
if(NN[1][i]=='0')
continue;
NN[1][i]='Q';
q[1]=i;
Search(1,N);
NN[1][i]='1';
q_num[i]=num-qnum;
}
}
void End(int N)
{
int i,j,answer=0,add;
for(i=1;i<=N;i++)
{
add=0;
for(j=1;j<=N;j++)
if(i!=j)
add+=q_num[j];
answer+=q_num[i]*add;
}
/* //显示统计的结果
for(i=1;i<=N;i++)
printf("%d",q_num[i]);
*/
printf("%d",answer); }
void main()
{
//初始
int N,i,j;
for(i=1;i<9;i++)
for(j=1;j<9;j++)
NN[i][j]='-';
/* //显示初始棋盘
printf("Start:(8*8)\n");
for(i=1;i<9;i++)
{
for(j=1;j<9;j++)
printf("%c",NN[i][j]);
printf("\n");
} */
//输入N
scanf("%d",&N);
for(i=1;i<=N;i++)
scanf("%s",NN[i]);
for(i=1;i<=N;i++)
{
for(j=N;j>0;j--)
NN[i][j]=NN[i][j-1];
NN[i][0]='0';
}
/* //显示新的棋盘
printf("Now you choice N=%d:(%d*%d)\n",N,N,N);
for(i=1;i<9;i++)
{
for(j=1;j<9;j++)
printf("%c",NN[i][j]);
printf("\n");
}*/
//开始计算
Begin(N);
End(N);
}
浙公网安备 33021202002483