注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

阿飘的博客

十里平湖霜满天 寸寸青丝愁华年

 
 
 

日志

 
 

八皇后问题  

2011-03-08 15:59:27|  分类: shell&c |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
皇后问题,是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。计算机发明后,有多种方法可以解决此问题。
IOCCC的一个实现(极简版)
#include
#define q(o) a[j]o[j+i+7]o[j-i+31]
int a[39];
void main(int i,int j){
    for(j=9;--j;i>8?printf("%10d ",a[j]):q(|a)||(q(=a)=i,main(i+1,j),q(=a)=0));
}
C语言另一个例子(效率较高):
#include "stdio.h"
#include "windows.h"
#define N 8 /* 定义棋盘大小 */
int place(int k); /* 确定某一位置皇后放置与否,放置则返回1,反之返回0 */
void backtrack(int i);/* 主递归函数,搜索解空间中第i层子树 */
void chessboard(); /* 每找到一个解,打印当前棋盘状态 */
static int sum, /* 当前已找到解的个数 */
x[N]; /* 记录皇后的位置,x[i]表示皇后i放在棋盘的第i行的第x[i]列 */
int main(void) {
    backtrack(0);
    system("pause");
    return 0;
}
int place(int k)
{
/* 测试皇后k在第k行第x[k]列时是否与前面已放置好的皇后相攻击。 x[j] == */
/* x[k] 时,两皇后在同一列上;abs(k - j) == abs(x[j] - x[k]) 时,两皇 */
/* 后在同一斜线上。两种情况两皇后都可相互攻击,故返回0表示不符合条件。*/
    for (int j = 0; j < k; j ++)
    if (abs(k - j) == abs(x[j] - x[k]) || (x[j] == x[k])) return 0;
    return 1;
}
void backtrack(int t)
{
    /* t == N 时,算法搜索至叶结点,得到一个新的N皇后互不攻击的放置方案 */
    if (t == N) chessboard();
    else
    for (int i = 0; i < N; i ++) {
        x[t] = i;
        if (place(t)) backtrack(t + 1);
    }
}
void chessboard()
{
    printf("第%d种解法:\n", ++ sum);
    for (int i = 0; i < N; i ++) {
        for (int j = 0; j < N; j ++)
            if (j == x[i]) printf("@ ");
            else printf("* ");
            printf("\n");
        }
    printf("\n");
}
  评论这张
 
阅读(494)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017