注释转载代码

/*n皇后问题（该程序用回溯法解答）
 *
 *(C) LC
 */

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

#define MAX    20
static int    x[MAX];//利用一个一维数组表示棋盘，从1-8的数字分别表示皇后放在这一行的第几列
static int    sum;//全局变量用来求解一共有多少解法

/***************************************************

***判断k行放置在第i（in main）列的皇后是否可行******

***************************************************/
int Place(int k)//判断该位置可不可以放置皇后

{
    int     j;
    for(j = 1; j < k; j++)
        if((abs(k-j) == abs(x[j] - x[k])) || (x[j] == x[k]))  

/*由于算法是以行为数组分割的，所以不可能行重复，于是检测斜角是否重复和列是否重复，如果有斜角重复，则有两个元素的行列坐标的差值绝对值相等，如果有列重复，则有两个数组元素值（即列坐标）相等！***************************************************************************************/
            return    1;//如果重复则返回1 表示不能放置皇后
    return    0;//表示这样放置没有问题
}

void output(int x[], int n)
{
    int    i, j;
    int    a[n][n];
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            a[i][j] = 0;
    for(i = 1; i <= n; i++)
    {
        if(x[i])
            a[i - 1][x[i] - 1] = 1;
    }
    for(i = 0; i < n; i++)
                {
            for(j = 0; j < n; j++)
                            printf("%d\t", a[i][j]);
            printf("\n");
        }

    printf("\n");
}

void Backtrack(int t, int n)
{
    int    i;
    if(t > n)//n为行列数，如果完全放下8行8列进入下一个
    {
        output(x, n);
        sum++;
    }
    else
        for(i = 1; i <= n; i++)
        {
            x[t] = i;//向第t行第i列放置一个皇后
     //     printf("good!%d\t%d\t%d\n", x[t], t, i);
/******************************************************

*************如果能放置，则计算t+1行的放置位置*********

******************************************************/
            if(!Place(t))
                Backtrack(t + 1, n);
        }
}



int main(void)
{
    int    n;
    printf("------------------------------\n");
    printf("please input n of the game!\n");
    scanf("%d", &n);
    Backtrack(1, n);
    printf("sum = %d\n", sum);
        
    return    0;    
}

 

回溯法的关键在于遍历到每一种情况，本例使用了函数的递归实现成功后的下一步；

好像没能找到用迭代法解的八皇后程序，想来还是需要8个循环嵌套实现，不知道又没有更简单的迭代算法