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

网络浪子

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

• foreachpossibilityatlevel1:
  
• foreachpossibilityatlevel2:
  
• foreachpossibilityatleveln:
  
• ...
  
• isitviable
  

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

• defconflict(state,nextX):
  
• nextY=len(state)
  
• ifnextY==0:print0
  
• foriinrange(nextY):
  
• ifabs(nextX-state)in(0,nextY-i):
  
• returnTrue
  
• returnFalse
  
• 
  
• defqueen(num,state=()):
  
• printstate
  
• forposinrange(num):
  
• ifnotconflict(state,pos):
  
• iflen(state)==num-1:
  
• yield(pos,)
  
• else:
  
• forresultinqueen(num,state+(pos,)):
  
• yield(pos,)+result
  
• 
  
• defprettyprint(solution):
  
• defline(pos,length=len(solution)):
  
• return'.'*pos+'X'+'.'*(length-pos-1)
  
• forposinsolution:
  
• printline(pos)
  
• 
  
• if__name__=='__main__':
  
• importrandom
  
• prettyprint(random.choice(list(queen(4))))
  

其中

• forresultinqueen(num,state+(pos,)):
  
• yield(pos,)+result
  

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

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

• /*
  
• *=====================================================================================
  
• *
  
• *Filename:eightqueen.cpp
  
• *
  
• *Description:8皇后问题，c＋＋实现
  
• *
  
• *Version:1.0
  
• *Created:2008年12月30日19时46分52秒
  
• *Revision:none
  
• *Compiler:gcc
  
• *
  
• *Author:LiWeiJian(mn),lwj1396@163.com
  
• *Company:hunanuniversity
  
• *
  
• *=====================================================================================
  
• */
  
• 
  
• #include<vector>
  
• #include<iostream>
  
• #include<cmath>
  
• usingnamespacestd;
  
• 
  
• boolconflict(constvector<int>&state,intnextX)
  
• {
  
• intnextY=state.size();
  
• for(inti=0;i<nextY;i++)
  
• {
  
• if(abs(nextX-state)==0||abs(nextX-state)==(nextY-i))
  
• returntrue;
  
• }
  
• returnfalse;
  
• }
  
• 
  
• voidqueen(intnum,vector<int>&state)
  
• {
  
• for(inti=0;i<num;i++)
  
• {
  
• state.clear();
  
• state.push_back(i);
  
• intpos=0;
  
• while(state.size()!=num)
  
• {
  
• if(conflict(state,pos))//冲突了
  
• {
  
• if(pos==num-1)//已经是最后一个位置
  
• {
  
• state.pop_back();
  
• break;
  
• }
  
• pos++;//尝试下一个pos
  
• continue;
  
• }
  
• else//没有冲突
  
• {
  
• state.push_back(pos);
  
• pos=0;
  
• }
  
• }
  
• if(state.size()==num)
  
• return;
  
• }
  
• }
  
• 
  
• voidprint(intnum,constvector<int>result)
  
• {
  
• for(inti=0;i<result.size();i++)
  
• {
  
• for(intj=0;j<result;j++)
  
• cout<<".";
  
• cout<<"X";
  
• for(intj=0;j<num-result-1;j++)
  
• cout<<".";
  
• cout<<endl;
  
• }
  
• }
  
• 
  
• intmain()
  
• {
  
• vector<int>state;
  
• queen(16,state);
  
• print(16,state);
  
• }
  
• 
  

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

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