八皇后乃至n皇后问题

题目：在棋盘上放置八个皇后，似的他们互不攻击，此时每个皇后的攻击范围为同行同列和同对角线，

要求找出所有解。

回溯：递归函数不在地柜调用它自身，而是返回上一层调用，这种现象叫做回溯。

解析：由题，皇后是逐行放置的，则皇后肯定不会横向攻击，因此，只需要检查是否纵向和斜向攻击即可。

判断条件：queen[hang]==queen[j]||hang-queen[hang]==j-queen[j]||hang+queen[hang]==j+queen[j]

判断条件如图：

0    1   2   3   4   5   6   7　　　　　　　　　　　　　　　　        0　　1　　2　　3　　4　　5　　6　　7

-1   0   1   2   3   4   5   6　　　　　　　　　　　　　　　　        1　　2　　3　　4　　5　　6　　7　　8

-2  -1   0   1   2   3   4   5　　　　　　　　　　　　　　　　        2　　3　　4　　5　　6　　7　　8　　9

-3  -2  -1   0   1   2   3   4　　　　　　　　　　　　　　　　        3　　4　　5　　6　　7　　8　　9　　10

-4  -3  -2  -1   0   1   2   3　　　　　　　　　　　　　　　　        4　　5　　6　　7　　8　　9　　10    11

-5  -4  -3  -2  -1   0   1   2　　　　　　　　　　　　　　　　        5　　6　　7　　8　　9　　10　 11    12

-6  -5  -4  -3  -2  -1   0   1　　　　　　　　　　　　　　　　　     6　　6　　7　　8　　9　　10　 11    13

-7  -6  -5  -4  -3  -2  -1   0 　　　　　　　　　　　　　　　　　    7　　8　　9　　10　 11    12    13    14

格子（x，y）的y-x值标志了主对角线    　　　　　　　　　　　　　　格子（x，y）的x+y值标识了副对角线

（几皇后问题，由n控制，在这里暂且设置为经典的八皇后。）

然后显示出来的是一个女生化的棋盘的模样。

所有结果均打印出来了。（一共92种，笑脸为皇后）如下图

//八皇后问题 
#include<stdio.h>
static int sum=0;
#define n 8
static int queen[n];
static char p[n][n];

void init()  //数组初始化 
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            p[i][j]=3;
        }
    }
}

void show()  //打印图形，笑脸代表皇后 
{
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            printf("%c ",p[i][j]);
        }
        printf("
");
    }
    printf("
");
}



void search(int hang)
{
    if(hang==n)
    {
        sum++;
        show();

    } 
    else
    for(int i=0;i<n;i++)//列 
    {
        int flag=1;
        queen[hang]=i;//尝试b把第hang行的皇后放在第i列 
        for(int j=0;j<hang;j++)//检查是否和之前的皇后冲突 
        {
            if(queen[hang]==queen[j]||hang-queen[hang]==j-queen[j]||hang+queen[hang]==j+queen[j])
            {
                flag=0;
                break;
            }
        }
        if(flag) //满足条件
        {
            p[hang][i]=1;
            search(hang+1);
            p[hang][i]=3;//清除放错的皇后 
        }
    
    }
}

int main()
{
    init();
    search(0);
    printf("%d",sum);
    return 0;
}