Question

关于八皇后问题

1.功能：输出八皇后问题的每种解法。
2.原理：利用回溯法和递归法。
3.程序：
#include<stdio.h>

int solution=1;
int chess[8];

//根据前面几行的放子情况
//检查这一行放子是否合法

int attack(int n)
{
int i;
for(i=1;i<=n-1;i++)
{
if(chess[n]==chess[i]+(n-i)||
chess[n]==chess[i]-(n-i)||
chess[n]==chess[i])
return 0;
}
return 1;

}

//输出每种可行解
void display()
{
int i;
printf("Solution %d:\n",solution);
for(i=1;i<=8;i++)
printf("%d ",chess[i]);
printf("\n");
++solution;
}

//递归求解函数
void putchess(int n )
{
int i;
//从第n行第一格(i)开始放棋子
for( i=1;i<=8;i++)
{
chess[n]=i;
if(attack(n)==1)
{
if(n==8)
display();
else
putchess(n+1);
}

}

}

int main()
{
printf("八皇后问题的解法如下:\n");
//开始放棋子
putchess(1);
return 0;

}

我的问题：
1.我的问题主要集中在此程序是怎样判定放棋子是否合法的算法上。即attack函数的原理。int attack(int n)
{
int i;
for(i=1;i<=n-1;i++)
{
if(chess[n]==chess[i]+(n-i)||
chess[n]==chess[i]-(n-i)||
chess[n]==chess[i])
return 0;
}
return 1;

}
由上下文可知，当if(chess[n]==chess[i]+(n-i)||chess[n]==chess[i]-(n-i)||chess[n]==chess[i]) 这一句生效时，皇后的放置是非法的。哪位高手能予以详解啊。本人是菜鸟，实在对chess[n]==chess[i]+(n-i)||chess[n]==chess[i]-(n-i)||chess[n]==chess[i]这一句是怎么结合棋盘来判定的搞不懂，承蒙赐教，将不胜感激！！！

Answer 1

n表示横坐标
chess[n]表示纵坐标
对角线是就是斜率为1或-1的直线
chess[n]==chess[i]是纵坐标相等
chess[n]==chess[i]+(n-i)||chess[n]==chess[i]-(n-i)
即（chess[n]-chess[i])/(n-i)==1或-1
即在同一对角线上
当n=i（即横坐标相等）也满足
综上
这一条件排除了同行同列和同对角线的情况

Answer 2

八皇后的定义是不能同行同列和同对角线上出现皇后。
for(i=1;i<=n-1;i++)
{
if(chess[n]==chess[i]+(n-i)||
chess[n]==chess[i]-(n-i)||
chess[n]==chess[i])
return 0;
}
这个循环中，对这当前放置的棋子的上面所说的三种情况的所有可能出现不合理放置的位置进行枚举检测，只要发现冲突，就返回一个0直。
该if语句中，一个三个表达式相连的或语句，对应了三种情况。