设为首页 加入收藏

TOP

C语言实现N皇后问题非递归求解(一)
2018-03-02 06:57:25 】 浏览:265
Tags:语言 实现 皇后 问题 求解

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);&nbs
编程开发网

首页 上一页 1 2 3 下一页 尾页 1/3/3
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇C语言重解经典回溯算法案例-迷宫.. 下一篇Python读取大文件的实现方法

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

最新文章

热门文章

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }