DFS专练1 八皇后经典问题

基本题意：八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？
也就是说，使得棋盘中每个横向、纵向、左上至右下斜向、右上至左下斜向均只有一枚皇后。求出所有可能情况并打印。

——————————————————————————————————————————————————————————————————————————————

思路：因为八枚棋子不在同一个列行和对角线上，所以就是说每行只会有一个皇后，每列只有一个皇后，所以说每一个棋子在每一行有八种情况，我们只需一行行放棋子，判断哪一列符合条件就放上，然后继续判断下一行直到第八行，注意： 1.用a[i]=j,来表示第i行第j列，大大减少了空间复杂度提高了效率！2.对角线上时，斜率为+-1,即（a[i]-lie)/(i-row)=+-1;==>fabs(a[i]-lie)=row-i;

代码如下：

#include <stdio.h>
int sum=0;//全局变量用来统计总情况数目。
int a[8]= {0};//用来记录八枚棋子各放在哪一行那一列
int judge(int row,int line)//判断棋子可不可以放在这个位置
{
    int i;
    for(i=0;i<row;i++)
    {
        if(a[i]==line||fabs(a[i]-line)==row-i)//同一行上肯定没有俩棋子了，只判断同一列跟对角线上有没有棋子即可（只判断该行之前的所有行即可）
            return 0;
    }
    return 1;
}
void Display()//打印情况
{
    int i,j;
    printf("第 %d 种解法如下:\n",++sum);
    for(i=0;i<8;i++)
    {
        for(j=0;j<8;j++)
        {
            if(a[i]==j)
                printf("%d",j);a[i]==哪一列就说明该行的棋子放在了哪一列
            else
                printf("#");
        }
        printf("\n");
    }
    printf("\n");
}
void DFS(int row)
{
    int line;
    for(line=0; line<8; line++)
    {
        if(judge(row,line))//如果可放
        {
            a[row]=line;//记录位置
            if(row==7)//退出条件
                Display();
            else
                DFS(row+1);//否则继续走下一行
        }
    }
}

int main()
{
    DFS(0);//从第0行开始
    printf("综上：总解法有 %d 种\n",sum);
    return 0;

}

以上：八皇后问题