8皇后问题的c＋＋与python实现对比

详细请点击：http://www.verydemo.com/demo_c92_i2205.html

c＋＋经典书多，但貌似不太新，而python则新书很多，能体现一些新思路新概念。看python的书，写python代码，再用c＋＋实现一遍，这样互补的学习方式貌似也蛮适合自己的。
在《Beginning Python From Novice to Professional》一书的八皇后问题上，python果然精妙而优雅。
在对待

1. foreachpossibilityatlevel1:
2. foreachpossibilityatlevel2:
3. foreachpossibilityatleveln:
4. ...
5. isitviable

形式的循环下，它有yield， generator递归。短短20来行代码就搞定了八皇后，如下：

1. defconflict(state,nextX):
2. nextY=len(state)
3. ifnextY==0:print0
4. foriinrange(nextY):
5. ifabs(nextX-state[i])in(0,nextY-i):
6. returnTrue
7. returnFalse
9. defqueen(num,state=()):
10. printstate
11. forposinrange(num):
12. ifnotconflict(state,pos):
13. iflen(state)==num-1:
14. yield(pos,)
15. else:
16. forresultinqueen(num,state+(pos,)):
17. yield(pos,)+result
19. defprettyprint(solution):
20. defline(pos,length=len(solution)):
21. return'.'*pos+'X'+'.'*(length-pos-1)
22. forposinsolution:
23. printline(pos)
25. if__name__=='__main__':
26. importrandom
27. prettyprint(random.choice(list(queen(4))))

其中

1. forresultinqueen(num,state+(pos,)):
2. yield(pos,)+result

2句由为精妙，自己苦思很久，没有能完全理解yield的精髓。。。。。

在用c＋＋实现的时候，一直想模仿实现这句话的功能，却被这句话困扰了2个多小时，看书看久了不休息果然效率奇差。
今天早上醒来，才恍然大悟，其实不就是个栈么。

1. /*
2. *=====================================================================================
3. *
4. *Filename:eightqueen.cpp
5. *
6. *Description:8皇后问题，c＋＋实现
7. *
8. *Version:1.0
9. *Created:2008年12月30日19时46分52秒
10. *Revision:none
11. *Compiler:gcc
12. *
13. *Author:LiWeiJian(mn),[email protected]
14. *Company:hunanuniversity
15. *
16. *=====================================================================================
17. */
19. #include<vector>
20. #include<iostream>
21. #include<cmath>
22. usingnamespacestd;
24. boolconflict(constvector<int>&state,intnextX)
25. {
26. intnextY=state.size();
27. for(inti=0;i<nextY;i++)
28. {
29. if(abs(nextX-state[i])==0||abs(nextX-state[i])==(nextY-i))
30. returntrue;
31. }
32. returnfalse;
33. }
35. voidqueen(intnum,vector<int>&state)
36. {
37. for(inti=0;i<num;i++)
38. {
39. state.clear();
40. state.push_back(i);
41. intpos=0;
42. while(state.size()!=num)
43. {
44. if(conflict(state,pos))//冲突了
45. {
46. if(pos==num-1)//已经是最后一个位置
47. {
48. state.pop_back();
49. break;
50. }
51. pos++;//尝试下一个pos
52. continue;
53. }
54. else//没有冲突
55. {
56. state.push_back(pos);
57. pos=0;
58. }
59. }
60. if(state.size()==num)
61. return;
62. }
63. }
65. voidprint(intnum,constvector<int>result)
66. {
67. for(inti=0;i<result.size();i++)
68. {
69. for(intj=0;j<result[i];j++)
70. cout<<".";
71. cout<<"X";
72. for(intj=0;j<num-result[i]-1;j++)
73. cout<<".";
74. cout<<endl;
75. }
76. }
78. intmain()
79. {
80. vector<int>state;
81. queen(16,state);
82. print(16,state);
83. }

在实现之后，对比了一下，效率的差距果然满大，python跑14皇后，等了几分钟没搞定，而c＋＋跑16皇后，都是刷的一下出来了，不过可能c＋＋没有用递归也是一个原因。

最后再总结2句：
1 一本书，无论薄厚，都不能欺负它，不要想1，2天就看完
2 c＋＋虽然经典，但书籍过老了，要拿一门有活力的语言为它开路，其实boost的c＋＋已经很python了。