c语言题_2n皇后问题

《c语言题_2n皇后问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2n皇后问题试题来自：程设09秋(徐)(程序设计基础课(清华大学徐明星老师、吴文虎老师)2009秋)【问题描述】给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。【输入格式】输入的第一行为一个整数n，表示棋盘的大小。接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。【输出格式】输出一个整数，表示总共有多少种放法。【样例输入

2、1】41111111111111111【样例输出1】2【样例输入2】41011111111111111【样例输出2】0分析：每行的Q的位置，保存在一个数组中Q[6]，Q[1]表示第一行q的列数。从第一行开始1到（n+1）/2遍历QQQ接下去的每行每列遍历，并检测是否符合，QQ如果Q[1]=1,那么Q[2]==Q[1]，则不符合QQ如果Q[1]>Q[2]，检测Q[2]是否在Q[1]的135度线上,Q[1]+（[2]-[1]）?=Q[2]，Q1与Q2的行差加上Q1的列值是否等于Q2的列值QQ如果Q[1]

3、?=Q[2]，Q1的列值减去Q1与Q2的行差是否等于Q2的列值如果只要求一种颜色的N皇后问题，并且没有0，1的限制，实现代码：#includecharNN[9][9];//棋盘，初始设为‘-’，1表示在棋盘格为空，Q表示放置皇后intq[6];//记录1-N行Q的列数,q[1]=3表示第一行的Q在第三列intCheak(intline)//检测要添加的Q是否符合要求{inti;for(i=1;i0){if(q[i]-(line-i)==q[lin

4、e])return0;}else{if(q[i]+(line-i)==q[line])return0;}}return1;}voidSearch(intline,intN){inti,j,n;if(line==N)//如果最后一行的Q已经存在，则打印棋盘for(i=1;i<9;i++){for(j=1;j<9;j++)printf("%c",NN[i][j]);printf("");}else//遍历此行，并通过检测查询下一行{line++;for(i=1;i<=N;i++){NN[line][i]='Q';q[line]=i;if(n=Cheak(line)>0){Sea

5、rch(line,N);}NN[line][i]='1';}}}voidBegin(intN){inti;for(i=1;i<=(N+1)/2;i++){q[1]=i;NN[1][i]='Q';Search(1,N);NN[1][i]='1';}}voidmain(){//初始intN,i,j;for(i=1;i<9;i++)for(j=1;j<9;j++)NN[i][j]='-';printf("Start:(8*8)");for(i=1;i<9;i++){for(j=1;j<9;j++)printf("%c",NN[i][j]);printf("");}//输入Ns

6、canf("%d",&N);for(i=1;i<=N;i++)for(j=1;j<=N;j++)NN[i][j]='1';printf("NowyouchoiceN=%d:(%d*%d)",N,N,N);for(i=1;i<9;i++){for(j=1;j<9;j++)printf("%c",NN[i][j]);printf("");}//开始计算Begin(N);}上述的代码中，只实现了棋盘的打印，并未统计放法的数量，通过Begin（）函数，第一行只检测一半，因为另一半是对称的（为了提高效率），然而题目要求是有0，1限制的，所以，为了实现上述要求，代码还应改动去掉对称

7、，因为棋盘添加了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列放白皇后和黑皇后是算两种情况的）最终代码：#includecharNN[9][9];//棋盘，初始设为'