最新消息:点击查看大S的省钱秘笈

八皇后问题 回溯递归 C语言版

编程相关 Slyar 10735浏览 13评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

今天听陈星火老师(火爷)的讲座提到了八皇后问题,正好今天没写的,于是晚上上完课回来就写了一段回溯递归解决八皇后问题的代码,当然也可以解决N皇后问题。运行后得到解为92组。

/* Code by Slyar */ 
#include 
#include 

#define max 8


int queen[max], sum=0; /* max为棋盘最大坐标 */

void show() /* 输出所有皇后的坐标 */
{
    int i;
    for(i = 0; i < max; i++)
    {
         printf("(%d,%d) ", i, queen[i]);
    }
    printf("\n");
    sum++;
}

int check(int n) /* 检查当前列能否放置皇后 */
{
    int i;
    for(i = 0; i < n; i++) /* 检查横排和对角线上是否可以放置皇后 */
    {
        if(queen[i] == queen[n] || abs(queen[i] - queen[n]) == (n - i))
        {
            return 1;
        }
    }
    return 0;
}

void put(int n) /* 回溯尝试皇后位置,n为横坐标 */
{
    int i;
    for(i = 0; i < max; i++)
    {       
        queen[n] = i; /* 将皇后摆到当前循环到的位置 */
        if(!check(n))
        {           
            if(n == max - 1)
            {
                show(); /* 如果全部摆好,则输出所有皇后的坐标 */
            }         
            else
            {
                put(n + 1); /* 否则继续摆放下一个皇后 */
            }
        }
    }
}

int main()
{
    put(0); /* 从横坐标为0开始依次尝试 */
    printf("%d", sum);
    system("pause");
    return 0;
}

转载请注明:Slyar Home » 八皇后问题 回溯递归 C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (13)

  1. 为什么我觉得check函数里面第一个应该return 0呢。。
    sunshine5年前 (2015-06-12)回复
  2. c语言八皇后中的回溯是用哪行代码实现的呢?回溯就能回到上一行的下一列吗
    梦之缘6年前 (2014-06-24)回复
  3. 火爷的课不可信呀,你main函数要放在所有其他函数前面,在main函数前做定义,在它后面写其它函数,这是逻辑先后顺序问题
    9年前 (2012-04-05)回复
    • main函数不一定要放在最前面啊
      Cindy4年前 (2016-11-09)回复
  4. excellent
    匿名9年前 (2011-11-07)回复
  5. 好代码,简单明了。博主相当勤奋。
    Adward11年前 (2010-04-09)回复
  6. 可以装个代码插件~~~
    匿名12年前 (2008-12-15)回复
    • 我不喜欢代码插件
      Slyar12年前 (2008-12-15)回复
  7. 动作蛮快!可以奖励你一包糖!!
    火爷12年前 (2008-10-31)回复
  8. 来学习了
    自然堂12年前 (2008-10-30)回复
  9. 我还是对没有缩进的代码很有意见。
    felix02112年前 (2008-10-30)回复
  10. 不懂c语言
    雪深12年前 (2008-10-30)回复