C语言实现N皇后问题非递归求解

C语言实现N皇后问题非递归求解

N皇后问题是一个老掉牙的问题了，随便翻一本算法书籍都能看到对它的介绍，其实N皇后问题可以用非递归方法解决，有效避免N过大时的递归工作栈溢出，且占用的存储空间较小，运行速度也较快，达到运行速度和空间合理利用的两全,代码很简单，并不复杂，有时简单也是一种美，意味着可靠和高效。追求程序的复杂和难以理解的编程者不会认同这一点，但对用简单的设计就可以解决的问题用复杂的数据表示加以描述是没有必要的。

代码如下(C语言):

#include <stdio.h>
#include <malloc.h>
#include <math.h>
int place(int i, int k, int *p);  //检查k+1行i列能否放置皇后,能返回1，否则返回0
int find(int n, int *p, int k);  //在k+1行搜索可以放置皇后的位置，找到位置后返回列标，否则返回0
void output(int n, int *p);  //输出n皇后问题的一个解

void main()
{
    int k, n;
    int m;
    int *p;

    printf("you want to solve n queens problem\n");
    printf("n=");
    scanf("%d", &n);                  //输入问题规模

    p=(int *) malloc(n*sizeof(int));  //p[k]表示k+1行皇后所在列
    for (k=0; k<n; k++)
    {
        p[k]=0;                    //初始化数组p                     
    }

    k=0;      //初始化为第一行
    m=0;      //记录解的个数变量初始化
loop: if (k==0)  //进入或回溯至第一行
      {
          p[k]=p[k]+1;  //试探下一列

          if (p[k]>n)    //第一行所有列试探完毕，回溯结束
          {
              goto exit;
          }

          k++;    //试探下一行
          goto loop;
      }
      else
      {
          if (find(n, p, k)==0)    //k+1行没有找到可放置皇后的位置
          {
              p[k]=0;            //必要的清理
              k--;                //回溯
              goto loop;
          }
          else
          {
              p[k]=find(n, p, k);    //在k+1行找到的位置赋予p[k]
              if (k!=(n-1))    //皇后没有全部放置完毕
              {
                  k++;          //试探下一行
                  goto loop;
              }
              else        //皇后全部放置成功，找到解
              {
                  m++;   
                  printf("The %dnd solution\n", m);
                  output(n, p);    //输出解

                  goto loop;  //回溯
              }
          }
      }

exit: ;
      printf ("There are %d solutions in total\n", m);  //输出解的个数
}

int place(int i, int k, int *p)
{
    int m;

    for (m=0; m<k; m++)
    {
        if ((p[m]==i)||(abs(m-k)==abs(p[m]-i)))  //k+1行i列不是合法位置
            return (0);
    }

    return (1);  //k+1行i列是合法位置   
}

int find(int n, int *p, int k)
{
    int i;
    i=p[k];

    for (i++; i<=n; i++)
    {
        if (place(i, k, p)==1)  //在k+1行找到可放置皇后的列
            return (i);    //返回该列
    }
    return (0);  //在k+1行没有找到可放置皇后的列
}

void output(int n, int *p)
{
    int i, j;

    for (i=0; i<n; i++)
    {
        for (j=1; j<=n; j++)
        {
            if (j==p[i])
                printf("1 ");
            else
                printf("0 ");
        }
        printf("\n");
    }
    printf("\n");
}

附n皇后问题的递归代码：

该程序段为自己的创作(教科书上现成的代码没必要复制粘贴)，意义不是很大，因为比较繁琐，当n<=8时能输出正确结果,n>8时直接STACKOVERFLOW，所以大家看看就好，并不实用

#include <stdio.h>
#include <math.h>
#include <malloc.h>
#include <stdlib.h>
void print(int n);
void put(int k, int n, int *q, int *p);
void output(int n, int *p);
int law(int k ,int i, int *p);

void main ()
{
    int n;
    printf ("you want to solve the problem of n queens the n=?\n");
    scanf ("%d", &n);
    print(n);
}

void print(int n)
{
    int number, i;
    int *p;
    number=0;
    p=(int *)malloc(n*sizeof(int));
    for (i=0; i<n; i++)
        *(p+i)=0;

    put(1, n, &number, p);

    printf("There are %d solutions in total\n", number);
    free(p);
}
void put(int k, int n, int *q, int *p)
{
    int i;
    if (k==1)
    {
        (*p)++;
        if ((*p)>n)
            return;
        put(k+1, n, q, p);
    }
    else
    {
        i=*(p+k-1);
        i++;
        while (i<=n)
        {
            if (law(k, i, p))
            {
                *(p+k-1)=i;
                if (k==n)
                {
                    (*q)++;
                    printf ("The %dnd solution\n", *q);
                    output(n, p);
                    put(k, n, q, p);
                }
                else
                {
                    put(k+1, n, q, p);
                }
                break;
            }
            i++;
        }
        if (i>n)
        {
            *(p+k-1)=0;
            put(k-1, n, q, p);
        }
    }
}

void output(int n, int *p)
{
    int j, c;
    for (j=1; j<=n; j++)
    {
        for (c=1; c<=n; c++)
        {
            if (c==*(p+j-1))
                printf ("%d", 1);
            else
                printf ("%d", 0);
        }
        printf ("\n");
    }
    printf ("\n");
}

int law(int k ,int i, int *p)
{
    int m;
    for (m=1; m<k; m++)
    {
        if ((*(p+m-1)==i)||(abs(m-k)==abs(*(p+m-1)-i)))
            return(0);
    }
    return(1);
}