八皇后问题，回溯和递归

$ # -*- coding:utf-8 -*-
$ #python默认为ascii编码，中文编码可以用utf-8
$
$ import random
$ def conflict(state,col):
$     row=len(state)
$     for i in range(row):
$          if abs(state[i]-col) in (0,row-i):
$              return True
$     return    False
$
$ def queens(num=8,state=()):
$     for pos in range(num):
$          if not conflict(state,pos):
$              if len(state)==num-1:
$                   yield(pos,)
$             else:
$                 for result in queens(num,state+(pos,)):
$                       yield (pos,)+result
$
$ def queenprint(soultion):   
$     def line(pos,length=len(solution)):
$          return '. '*(pos)+'X'+'. '*(length-pos-1)
$     for pos in solution:
$          print line(pos)
$        
$ for solution in list(queens(8)):
$     print solution
$
$ print ' total number is '+str(len(list(queens())))'
$ print ' one of the range is:\n'
$ 
$ queenprint(random.choice(list(queens())))

源码解析

主要利用冲突函数检测冲突，如果冲突则回溯，递归用到python的yield语句，该语句涉及python的生成器

冲突函数

$ def  conflict(state,col):
$     #冲突函数，row为行，col为列(不论行和列都是从0开始的)
$    row=len(state)
$     for i in range(row):
$          if abs(state[i]-col) in (0,row-i):
$             return True
$    return False
$注释:state为已知的皇后的状态，类型是一个元组，例如(7,3,0,2,5,1,6,4),元组是不可变对象，一经创建不能修改，元组是创建生成器的一种方法(第一行的皇后在第七列，第二行的皇后在第三列，等等)

假设第一行到第三行的皇后都没冲突，这个时候要检测第四行皇后是否冲突。如第一行皇后在第五列，第二行皇后在第八列，第三行皇后在第四列，检验第四行皇后放在哪一列不会冲突。

$ * * * * X * * *
$ * * * * * * * X
$ * * * X * * * *
$ 这时state=(4,7,3),col=?

1 得出目前没冲突的行数row

$ row = len(state)

2 从1~row行依次检测已知的皇后是否与row+1行皇后有冲突

$ for i in range(row):

3 如果row+1行皇后所在的列col与其它行皇后的列相同或处于对角线，则冲突

$ if abs(state[i]-col) in (0,row-i):#判断是否冲突
$    return True

以上语句翻译为(其它已知的皇后所在的列-要求检测的皇后所在的列)等于0或者等于(row-i)则冲突

傻瓜式教学：第一行与第四行冲突，要么在同一列，要么在对角线，当对角线列数相差3，因为第一行与第二行对角线相差1，第二行与第三行对角线相差1，则第一行与第三行对角线相差2，以此类推，第一行与第四行冲突，则相差3

当第四行所在列col=4,这时abs(state[0]-4) in (0,3-0)为真，因为4-4=0，如图：

$ * * * * X * * *
$ * * * * * * * X
$ * * * X * * * *
$ * * * * X * * *     同列冲突

当第四行所在列col=2,这时abs(state[2]-2) in (0,3-2)为真，因为abs(3-2)=1，如：

$ * * * * X * * *
$ * * * * * * * X
$ * * * X * * * *
$ * * X * * * * *     对角线冲突

生成器函数：

$ def queen(num=8,state=()):
$     #生成器函数
$     for pos in range(num):
$         if not conflict(state,pos):
$            if len(state)==num-1:
$                yield(pos,)
$            else:
$                for result in queens(num,state+(pos,)):
$                    yield (pos,)+result

生成器:通过列表生成式，我们可以直接创建一个列表，但是，受到内存限制，列表容量肯定是有限的，而且，创建一个包含100万个元素的列表，不仅占用很到的存储空间，如果我们仅仅需要访问前面几个元素，那后面绝大多数元素占用的空间都白白浪费了，所以，如果列表元素可以按照某种算法推算出来，那我们是否可以在循环过程中不断推算出后续的元素呢？这样就不必创建完整的list，从而节省大量的空间，python中，这种一遍循环一边计算的机制，称为生成器

步骤

1 下面该语句为构建所有皇后摆放情况打下基础，可以尝试所有情况

$ for pos in range(num):

2 如果不冲突，则递归构造棋盘

$ if not conflict(state,pos):

3 如果棋盘状态state已经等于num-1,即到达倒数第二行，而这时最后一行皇后又没冲突，直接yield，打出其位置(pos,),python在显示只有1个元素的元组时，也会加上一个逗号，以免你误解成数学计算意义上的括号，否则递归，打印(pos,)+result

$ if len(state)==num-1:
$     yield(pos,)
$ else:
$    for result in queens(num,state+(pos,)):
$        yield (pos,)+result

傻瓜式教学:例如pos=0，第0行放在第0列，这时不会冲突，但是不会进入if，因为还没到达倒数第二行，进入else后，再调用queens(num,state+(pos,)),这时进入第二行，再次递归展开则是queens(num,state+(pos,)+(pos,)),到达最后一行时返回(pos,),再返回倒数第二行，再返回倒数第三行，最后到达最开始那层(pos,)+result, pos为第0行皇后所在列，result包含第一行皇后和另一个result

打印所有结果

$ for solution in queens(8):
$     print solution

queens(8)因为生成器函数的for循环，每一次循环都会yield一个元组出来，所以有很多种情况，可以把它全部打印出来
也可以用list包装列表在统计一下多少种数目

$ print 'total number is '+str(len(list(queens())))

随机优美打印一个棋盘情况

$ print ' one of the range is:\n'
$ queenprint(random.choice(list(quees())))