CodePanada

panada 不是熊猫 胜似熊猫
posts(7) comments(3) trackbacks(0)
  • C++博客
  • 联系
  • RSS 2.0 Feed 聚合
  • 管理

常用链接

  • 我的随笔
  • 我的评论
  • 我参与的随笔

留言簿

  • 给我留言
  • 查看公开留言
  • 查看私人留言

随笔分类

  •  C/C++(1)
  •  读研那些事(1)
  •  设计模式(2)
  •  算法(2)
  •  心情(1)

随笔档案

  • 2011年6月 (1)
  • 2011年5月 (6)

常去的地方

  •  C++标准库
  •  陈硕的Blog

搜索

  •  

最新评论

  • 1. re: 用位操作实现的n皇后问题
  • 主要是位操作在线性上的二进制优化。
  • --。。。
  • 2. re: 用位操作实现的n皇后问题
  • 因为一直在做理论研究,所以程序几乎很多都看不懂了。。。谢谢你的推荐~ ps:我是C/C++的坚定粉丝。。呵呵@SonicMisora
  • --熊猫呵呵
  • 3. re: 用位操作实现的n皇后问题[未登录]
  • 八皇后的位运算写法是很基本的……然后要看精彩程序的话建议看下有个用下划线写成的PI计算程序,以及某个开根程序。
    当今世界上用C的程序员有95%都没有真正学会C,当然我也是其中一个。
  • --SonicMisora

阅读排行榜

评论排行榜

View Post

用位操作实现的n皇后问题

      C语言是我大一时期专业课所学习的第一门语言,离现在差不多也有将近5年的时间。最近想重拾起来,买了一本Plauger大牛的<<The standard C library>>,简单翻了一下,觉得自己如井底之蛙一样。。。以前对C的理解只是皮毛,孰不知这门极其优秀的跨平台可移植的编译语言还有如此精彩的实现。
      前几天整理文档,发现了这段用C bit实现的N皇后算法,花了半天时间才把它搞明白。。大家都知道,n皇后的一般解法是回溯,要用一个二维数组表示棋盘,按逐行(列)进行解搜索,对于每个当前解都要进行判断,如成功则继续;失败则回溯。
      这段用bit实现的代码极其简明。只不过它只是用了一个一维的数组,按行搜索,将列上的、对象线上的限制归一。
      感兴趣的朋友可以看下:http://jsomers.com/nqueen_demo/nqueens.html 作者的方法跟下面的方法大同小异。
 1 #include <stdio.h> 
 2 #include <stdlib.h> 
 3 #include <time.h> 
 4 
 5 long int sum = 0, upperlim = 1; 
 6 
 7 void test(long  row, long  ld, long  rd) 
 8 {
 9     //printf("%ld\t%ld\t%ld\n",row,ld,rd);
10     //printf("%ld\t",row); 
11     //printf("\n%ld\n",upperlim); 
12     if(row != upperlim) 
13     {
14         long pos = upperlim & ~(row|ld|rd); 
15         //printf("%ld\n",pos);
16         while(pos!= 0) 
17         { 
18           //    printf("%ld\n",pos);
19               long p = pos & -pos; 
20               pos = pos - p; //取得可以放皇后的最右边的列
21               test(row + p,(ld + p)<<1, (rd + p)>>1);
22           }   
23       return; 
24      }
25       else 
26     {
27         sum++; 
28         return; 
29     }
30 } 
31 
32 int main(int  argc, char  *argv[]) 
33 { 
34       time_t tm; 
35       int n = 16; 
36       if(argc  !=   1) n = atoi(argv[1]); 
37       tm = time(0); 
38       if((n < 1)||(n > 32)) 
39       { 
40         printf("只能计算1-32之间的皇后问题\n "); 
41         exit(-1); 
42       } 
43       printf( "%d皇后\n ",n); 
44        printf("%ld\t",upperlim); 
45       upperlim = (upperlim << n) - 1;      //所有位都是1 
46          printf("%ld\t",upperlim); 
47       test(0,0,0); 
48       printf( "共有%ld种排列,计算时间%d秒\n",sum,(int)(time(0)-tm)); 
49       system("pause");
50       return 0;
51 } 


posted on 2011-06-08 00:16 熊猫呵呵 阅读(2254) 评论(3)  编辑 收藏 引用 所属分类: C/C++

View Comments

# re: 用位操作实现的n皇后问题[未登录]  回复  更多评论   
八皇后的位运算写法是很基本的……然后要看精彩程序的话建议看下有个用下划线写成的PI计算程序,以及某个开根程序。
当今世界上用C的程序员有95%都没有真正学会C,当然我也是其中一个。
2011-06-08 22:01 | SonicMisora
# re: 用位操作实现的n皇后问题  回复  更多评论   
因为一直在做理论研究,所以程序几乎很多都看不懂了。。。谢谢你的推荐~ ps:我是C/C++的坚定粉丝。。呵呵@SonicMisora
2011-06-09 18:07 | 熊猫呵呵
# re: 用位操作实现的n皇后问题  回复  更多评论   
主要是位操作在线性上的二进制优化。
2015-12-01 21:28 | 。。。
刷新评论列表

只有注册用户登录后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


 
Powered by:
C++博客
Copyright © 熊猫呵呵