【剑指offer】八皇后问题

转载请注明出处:http://blog.csdn.net/ns_code/article/details/26614999

    剑指offer上解决八皇后问题,没有用传统的递归或非递归回溯法,而是用了很巧妙的全排列法。

    先说下八皇后问题:在8 X 8的国际象棋上摆放八个皇后,使其不能相互攻击,即任意两个皇后不得处于同一行,同一列或者同意对角线上,求出所有符合条件的摆法。

    全排列解决八皇后问题的思路如下:

    由于8个皇后不能处在同一行,那么肯定每个皇后占据一行,这样可以定义一个数组A[8],数组中第i个数字,即A[i]表示位于第i行的皇后的列号。先把数组A[8]分别用0-7初始化,接下来对该数组做全排列,由于我们用0-7这7个不同的数字初始化数组,因此任意两个皇后肯定也不同列,那么我们只需要判断每个排列对应的8个皇后中是否有任意两个在同一对角线上即可,即对于数组的两个下标i和j,如果i-j==A[i]-A[j]或i-j==A[j]-A[i],则认为有两个元素位于了同一个对角线上,则该排列不符合条件。

    代码如下:

[cpp] view plaincopy

  1. #include<stdio.h>
  2. void swap(int *a,int *b)  
  3. {  
  4. int temp = *a;  
  5.     *a = *b;  
  6.     *b = temp;  
  7. }  
  8. /*
  9. 如果有符合条件的摆法,打印出所有的摆法,否则,什么也不打印
  10. */
  11. void CubVertex(int *A,int len,int begin)  
  12. {  
  13. if(A==NULL || len!=8)  
  14. return;  
  15. if(begin == len-1)  
  16.     {  
  17. int i,j;  
  18. bool can = true;    //是否又符合条件的摆法
  19. for(i=0;i<len;i++)  
  20. for(j=i+1;j<len;j++)  
  21. if(i-j==A[i]-A[j] || i-j==A[j]-A[i])  
  22.                 {  
  23. //如果任意两个在一条对角线上,则不符合
  24.                     can = false;  
  25. break;  
  26.                 }  
  27. //有符合的摆法,就打印出来
  28. if(can)  
  29.         {  
  30. for(i=0;i<len;i++)  
  31.                 printf("%d ",A[i]);  
  32.             printf("\n");  
  33.         }  
  34.     }  
  35. else
  36.     {  
  37. int i;  
  38. for(i=begin;i<len;i++)  
  39.         {  
  40.             swap(&A[begin],&A[i]);  
  41.             CubVertex(A,len,begin+1);  
  42.             swap(&A[begin],&A[i]);  
  43.         }  
  44.     }  
  45. }  
  46. int main()  
  47. {  
  48. int A[8] = {0,1,2,3,4,5,6,7};  
  49.     CubVertex(A,8,0);  
  50. return 0;  
  51. }  

    测试结果:

    四皇后:

    四皇后总共有2中摆法。

    1、3、0、2的意思是指:第0行上的皇后摆放在第1个位置(从0开始),第1行上的皇后摆放在第3个位置,第3行上的皇后摆放在第0个位置,第4行上的皇后摆放在第2个位置。

    八皇后:

    八皇后总共有92种摆法。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏儿童编程

天干地支五行八卦的对应关系

19790
来自专栏儿童编程

一张图理清《梅花易数》梗概

学《易经》的目的不一定是为了卜卦,但是了解卜卦绝对能够让你更好地了解易学。今天用一张思维导图对《梅花易数》的主要内容进行概括,希望能够给学友们提供帮助。

32440
来自专栏儿童编程

我不是算命先生,却对占卜有了疑惑——如何论证“占卜前提”的正确与否

事出有因,我对《周易》感兴趣了很多年。只是觉得特别有趣,断断续续学习了一些皮毛。这几天又偶然接触到了《梅花易数》,觉得很是精彩,将五行八卦天干地支都串联了起来。...

15610
来自专栏儿童编程

儿童创造力教育与编程教育的碰撞——MIT雷斯尼克教授最新理论梗概

儿童编程教育已经在我国各一线二线城市疯狂出现,颇有“烂大街”的趋势。我们不禁要问很多很多问题:

22670
来自专栏儿童编程

一张思维导图看懂《周易》基础要点——参考《易经杂说》

本图对《易经》的基础部分做了归纳总结。主要参考南怀瑾先生的《易经杂说》及不同版本《周易》。

83440
来自专栏儿童编程

声音功能让儿童编程更有创造性

导读:Scratch中声音功能非常强大,除了常规的音效,你甚至可以模拟各种乐器的各个发音、设置节拍、休止……如果你愿意,甚至可以用它创作一个交响乐。我们可以引导...

13940
来自专栏儿童编程

儿童编程Scratch之“画笔”基础功能学习总结

Scratch中“画笔”功能能够让使用者模拟画笔在舞台上创作,合理运用能够给作品带来极大的趣味性。

65220
来自专栏儿童编程

《动物魔法学校》儿童学编程Scratch之“外观”部分

导读:本文通过一个案例《动物魔法学校》来学习Scratch语言的“外观”部分。之后通过一系列其他功能的综合运用对作品功能进行了扩展。

19340
来自专栏儿童编程

什么样的人生才是有意义的人生——没有标准的标准答案

【导读】其实我们可以跳出这个小圈圈去更加科客观地看一下这个世界。在夜晚的时候我们仰望天空,浩瀚的宇宙中整个地球只是一粒浮尘,何况地球上一个小小的人类?在漫长的历...

1.8K50
来自专栏儿童编程

一张导图梳理欧洲简史梗概

3.1K30

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励