八皇后问题

问题描述：在一个8*8的国际棋盘上有8个皇后，每个皇后占一格，要求任意两个皇后都不能处在同一行，同一列或同一对角线上。

#include<stdio.h>
#include<math.h>

const int N=8;

int site[N];

int isValid(int n)
{
    int i;

    for(i = 0 ; i < n ; i++)
    {
        if(site[i] == site[n])
            return 0;

        if(abs(site[i] - site[n]) == (n - i))
            return 0;
    }

    return 1;
}

void queen(int depth)
{
    int i;

    if(depth == N)                
    {
        for(int i=0;i<N;i++)
            printf("%4d",site[i]);
        printf("\n");

        return;
    }

    for(i = 1 ; i <= N ; i++)
    {
        site[depth] = i;

        if(isValid(depth))
            queen(depth+ 1);                    
    }
}

int main()
{
queen(0);

return 0;
}

 

八皇后采用深度优先搜索的方式从前到后依次枚举每一行上的位置，当该位置满足要求时，就向下搜索