问题描述

要在8*8的国际象棋中放八个皇后，使任意两个皇后不能相互吃掉，在同一行，同一列，同一对角线会相互吃掉，求所有的可能。

回溯法思想

我们可以先在第一行找出相应的位置，然后再在下一行找符合条件的位置，当我们找到一种解决方法是便将结果输出，继续回溯寻找。

代码

#include<stdlib.h>
#include<stdio.h>
int a[100];
int output(int n)
{
    for(int i=1;i<=n;++i)
        printf("%d ",a[i]);
    printf("\n");
}
int huisu(int n)
{
    int k=1;
    a[1]=0;
    while(k>0)
    {
        a[k]+=1;
        while(k<=n && (check(k)==0))
            a[k]+=1;   //表示第k行向后移一个位置
        if(a[k]<=n)
        {
            if(k==n)  //表示遍历到最后一行
            {
                output(n);
            }
            else
            {
                k+=1;   //开始下一行
                a[k]=0;
            }
        }
        else
            k-=1;
    }
}

int check(int k)
{
    //检查是否冲突
    int i;
    for(i=1;i<k;++i)     //下标是从1开始的
    {
        if(abs(a[i]-a[k])==abs(i-k) || a[i]==a[k])
            return 0;
    }
    return 1;
}
int main()
{
    int n;
    printf("输入个数:\n");
    scanf("%d",&n);
    huisu(n);
}

代码分析

• 主要是huisu()这个函数，我们介绍一下这个函数的作用。

 while(k<=n && (check(k)==0))
            a[k]+=1;   //表示第k行向后移一个位置

这个的作用是寻找第k行符合条件的位置，即不冲突，寻找位置的方法是将第k行的每个位置顺序和前k-1个位置进行检查看是否冲突，当都不冲突时便表示这个位置可以用，将这个位置保存到a[k]当中，当第k行没有满足条件的时最后a[k]=n+1，后面可以使用这个条件判断是否进行回溯，当a[k]=n+1便表示这一行已经没有可以使用的位置了，因此便会回溯到第k-1行。

• 下面的代码。

if(a[k]<=n)
        {
            if(k==n)  //表示遍历到最后一行
            {
                output(n);
            }
            else
            {
                k+=1;   //开始下一行
                a[k]=0;
            }
        }
        else
            k-=1;
    }

首先判断a[k]是否小于等于n，如果大于n，表示这一行已经没有符合条件的了，便回溯。否则判断k是否为n，如果为n，表示已经全部挑选出位置了，便可以输出了，如果k<n,表示还没有将所有的皇后都安排到合适的位置，便将k=k
+1，开始查找下一行，下一行从头开始进行寻找。