八皇后问题的学习

方法一：（穷举法与剪支）

void main()
{
int a[9];
int i,t=1;
for(a[1]=1;a[1]<9;a[1]++)
for(a[2]=1;a[2]<9;a[2]++)
{
if(!Check(a,2)) continue;
for(a[3]=1;a[3]<9;a[3]++)
{
if(!Check(a,3)) continue;
for(a[4]=1;a[4]<9;a[4]++)
{
if(!Check(a,4)) continue;
for(a[5]=1;a[5]<9;a[5]++)
{
if(!Check(a,5)) continue;
for(a[6]=1;a[6]<9;a[6]++)
{
if(!Check(a,6)) continue;
for(a[7]=1;a[7]<9;a[7]++)
{
if(!Check(a,7)) continue;
for(a[8]=1;a[8]<9;a[8]++)
{
if(!Check(a,8)) continue;
else
{
printf("第%d种解法： ",t++);
for(i=1;i<9;i++)
printf("第%d个皇后：%d ",i,a[i]);
printf(" ");
} } } } } } } } }

/////////////////////////////////Check函数功能：检验第n行的皇后是否和之前的皇后有冲突，没有的话返回1
int Check(int a[],int n)
{
for(int i=1;i<n;i++)
{
if(abs(a[i]-a[n])==abs(i-n) || a[i]==a[n])//////////////见下面注释
return 0;
}
return 1;
}

方法二：（回溯算法）

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

int Check(int a[], int n);
int main()
{
   int a[256] = { 0 };
   int i = 1, j, n, t = 1;////////////////////////////////////i表示当前正在搜索第i行的皇后位置
   printf("请输入几皇后？n=");
   scanf_s("%d", &n);
   while (i>0)
   {
       for (a[i]++; a[i] <= n; a[i]++)   ////////////////当前行的皇后试探
       {
           if (Check(a, i))//////////////////////////////如果第i行的皇后与之前的皇后位置上没有冲突，则break跳出循环
               break;
       }
       if (a[i] <= n)/////////////////////////////////////如果a[i]<=n，即上面的for循环是由“break;”跳出来的,即第i行皇后的位置符合条件
       {
           if (i == n)////////////////////////////////////找到一组解，输出
           {
               printf("第%d种解法： ", t++);
               for (j = 1; j <= n; j++)
                   printf("第%d个皇后：%d ", j, a[j]);
               printf(" ");
           }
           else////////////////////////////////////////未找完
           {
               i++;
               a[i] = 0;
           }
       }
       else
           i--;////////////////////////////////////////回溯 ---当前行的位置全部找完
   }
}

int Check(int a[], int n)
{
   for (int i = 1; i<n; i++)
   {
       if (abs(a[i] - a[n]) == abs(i - n) || a[i] == a[n])//////////////见下面注释
           return 0;
   }
   return 1;
}

方法三：（递归算法）

#include<stdio.h>
#include<stdlib.h>
int a[20], n, i, j, t = 1;////////////////////////////////////////全局变量

int Check(int a[], int n)
{
   for (int i = 1; i<n; i++)
   {
       if (abs(a[i] - a[n]) == abs(i - n) || a[i] == a[n])//////////////见下面注释
           return 0;
   }
   return 1;
}

void Try(int i)
{
   int j, k;
   for (j = 1; j <= n; j++)
   {
       a[i] = j;   ///////////////////////////////////////////当前行解法的所有尝试
       if (Check(a, i))///////////////////////////////////////如果第j列不会与之前的皇后冲突
       {
           if (i<n)//////////////////////////////////////////如果i<n，即还没有找到八个皇后，继续递归
               Try(i + 1);
           else ////////////////////////////////////////////如果找到了一组解就输出
           {
               printf("第%d种解法： ", t++);
               for (k = 1; k <= n; k++)
                   printf("第%d个皇后：%d ", k, a[k]);
               printf(" ");
           }
       }
   }
}

void main()
{
   printf("几皇后？n=");
   scanf_s("%d", &n);
   Try(1);
}

（原文链接：http://blog.csdn.net/bone_ace/article/details/41419695）