n皇后问题【非递归回溯】

#include<stdio.h>

#include <math.h>

int a[20];//最多可以解决20皇后问题

int check(int n)

{

 int i,flag;

 flag = 1;

 for (i=1;i<n;i++)

 {

  if (abs(a[i]-a[n])==abs(i-n) || a[i]==a[n])

  {

   flag=0;

   break;

  }

 }

 return flag;

}

void output(int k)

{

 int i;

 for (i=1;i<=k;i++)

 {

  printf("%4d",a[i]);

 }

 printf("\n");

}

void Queens(int n)

{

 int k;

 k=1;

 a[k]=0;

 while (k>0)

 {

  a[k]++;//①新的皇后位置置1、②回溯之后查找下一个位置

  while (a[k]<=n && check(k)==0)//为第k个皇后找一个合适的位置

  {

   a[k]++;

  }

  if (a[k]<=n)//第k个皇后的位置是否越界

  {

   if (k==n)//如果k=n，说明已经找到一组合适的解，输出。

   {

    output(k);

   }

   else//如果k=n，则继续寻找下一个皇后的位置

   {

    k++;

    a[k]=0;//新的皇后位置置0

   }

  }

  else//如果第k个皇后的位置越界，说明没有合适的位置，回溯。

  {   

   k--;

  }

 }

}

void main()

{

 int n;

 printf("输入皇后个数:");

 scanf("%d",&n);

 Queens(n);

}