了解知识

python基础教程(第二版)第九章,有一个例子是8皇后问题,据说是一个经典的计算机问题。
可以抽象成N皇后问题:
在一个N*N的国际象棋棋盘中,放入N个皇后,要求它们中任意两个都不能攻击到对方。
这个问题本身作为计算机编程问题算是递归算法的经典,难度似乎不算太大。我按以往的旧方案(也就是java之类的语言)的那一套也写了个解法,比较冗长。后来看了书里的python解法,不禁惊呼python真的太神奇了!过了几个小时,我凭记忆重新写了一次类似书中的解法,写得与书略有不同,不过也问题不大,只是多了两行而已。
不妨先记录一下我的解法:

==================================================================================
#num个皇后问题的解,假使已经给定条件前几个状态是state
def queens(num,state):
#在前面的皇后状态已经给定为state1的时候,下一个皇后的位置可不可以是nextX
def conflict(state1,nextX):
for i in range(len(state1)):
if abs(state1[i]-nextX) in (0,abs(i-len(state1))):
return True #有冲突,不能是nextX
return False #没有冲突,可以是nextX
#如果只差最后一位那么把可行的全部加上
if len(state)==num-1:
for i in range(num):
if not conflict(state,i):
yield state+(i,)

#如果不只差一位,那么把所有增加一位后可行的状态利用递归算出结果表
else:
for i in range(num):
if not conflict(state,i):
for result in queens(num,state+(i,)):
yield result
return
if __name__=='__main__':
solution=list(queens(8,()))
print(len(solution))
===================================================================================

现在我们可以来谈谈python的生成器有多么强大了……
说python之前,还要先说说递归。queens()方法有两个参数,这个设定很很重要。在递归当中,方法的参数设定是很重要的,设定得好,可以通过改变参数进行递归。
递归的语句是:for result in queens(num,state+(i,)): yield result
这一句就体现了生成器的恐怖之处。如果不用生成器,要遍历并记录下一层的所有结果,然后再记录所有成立的最终结果,可能要几十行代码。用了生成器,递归的结果不再是一个函数值,而是一个表,遍历就很方便了。再用一个for,世界从此清静。 

标签: python
扩展知识