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);

}