在 n 行 n 列的国际象棋棋盘上,最多可布n个皇后。 若两个皇后位于同一行、同一列、同一对角线上,则称为它们为互相攻击。 n皇后问题是指找到这 n 个皇后的互不攻击的布局。 n 行 n 列的棋盘上,主次对角线各有2n-1条。
不好意思,邮箱写漏了,应为szf2004szf@tom.com
/皇后问题好象要忘的差不多了,但如果对角线只是
主对角线上不能攻击的话,那这样就可以了。
/*********************************************/
#include<stdio.h>
int b[200],n;
int ok(int i)
{
int j,yes1=1,yes2=1;
for (j=1;j<=i-1;j++)
{
if (b[j]==b[i]) return(0);
if (b[j]==j) yes1=0;
if ((b[j]+j)==(n+1)) yes2=0;
}
if (!yes1) {if (b[i]==i) return(0);
else return(1);}
if (!yes2) {if ((b[i]+i)==(n+1)) return(0);
else return(1);}
if ((yes1)&&(yes2)) return(1);
}
void main()
{
int i,j;
long m=0;
printf("input n:");
scanf ("%d",&n);
for (i=1;i<=n;i++) b[i]=1;
i=1;
while (i>=0)
{
i=i+1;
while (b[i]>n)
{
b[i]=1;
i=i-1;
b[i]=b[i]+1;
}
if (!ok(i)) {b[i]=b[i]+1;i=i-1;}
if (i==n) {
for (j=1;j<=n;j++) printf("%5d",b[j]);
printf("\n");
m=m+1;
b[i]=b[i]+1;i=i-1;}
}
printf("total:%ld\n",m);
}
/*write by Cherryfly*/
#include <stdio.h>
#define MAX_NUM 20 /*皇后的最大个数*/
/*棋盘 */
int QArray[MAX_NUM+1][MAX_NUM+1];
/*安排的结果,answer[i]中的数字代表第i个皇后所在的列*/
int answer[MAX_NUM+1];
int Ans_num=0;
/*初始化*/
void init(int n)
{
int i=0,j=0;
for(i=1;i<n+1;i++)
answer[i]=0;
for(i=1;i<n+1;i++)
for(j=1;j<n+1;j++)
QArray[i][j]='*';
}
/*输出皇后结果*/
void prf(int n)
{
int i=0,j=0;
printf("\nAnswer %d:\n",++Ans_num);
/*在皇后的位置放上皇后*/
for(i=1;i<n+1;i++)
QArray[i][answer[i]]=1;
for(i=1;i<n+1;i++)
{
printf("\t");
for(j=1;j<n+1;j++)
printf("%c",QArray[i][j]);
printf("\n");
}
/*恢复棋盘,为下次放皇后做准备*/
for(i=1;i<n+1;i++)
QArray[i][answer[i]]='*';
}
/*判断在第k行的l列是否可以放一个皇后,
判断以前前k-1行已经放好了k-1个皇后*/
int adjust(int k,int l)
{
int i=0;
/*answer[i]==l在同一列,(answer[i]-i)==(k-l)||(answer[i]-i)==(l-k)
表示在同一条对角线*/
for(i=1;i<k;i++)
if((answer[i]==l)||((answer[i]-l)==(i-k))||((answer[i]-l)==(k-i)))
return 0;
return 1;
}
/*使用回溯法实现*/
void queen(int n)
{
int k=0;
k=1;/*第一行*/
while(k>0)
{
answer[k]=answer[k]+1;/*从第一列开始找*/
while((answer[k]<n+1)&&(!adjust(k,answer[k])))
answer[k]=answer[k]+1;
if(answer[k]<n+1)/*找到了一个可以放置的位置*/
{
if(k==n)
{
prf(n); /*打印一个答案*/
printf("\nThe is the No.%d answer,",Ans_num);
printf("press any key to continue...");
getch();
}
else
{k++;answer[k]=0;} /*到下一行*/
}
else
k--; /*回溯*/
}
}
main()
{
int n=0; /*queen number */
printf("\nInput the queen's number:");
scanf("%d",&n);
init(n);
queen(n);
if(Ans_num==0)
printf("\n\nNo Answer!");
getch();
}
/*write by Cherryfly*/
我大概测试了一下,应该是正确的
由于如果输入的数比较大的话,答案过多
由于为了看到没一个结果
在每一次输出的结果以后,你要按一下键,程序继续
所以输入的数大的话,你就比较惨
要按好多次的键盘
不要说我没有提醒
如果有错和我说,我再修改