八皇后,回溯与递归(Python实现)

八皇后问题是十九世纪著名的数学家高斯1850年提出 。以下为python语言的八皇后代码,摘自《Python基础教程》,代码相对于其他语言,来得短小且一次性可以打印出92种结果。同时可以扩展为九皇后,十皇后问题。

问题:在一个8*8棋盘上,每一行放置一个皇后旗子,且它们不冲突。冲突定义:同一列不能有两个皇后,每一个对角线也不能有两个皇后。当然,三个皇后也是不行的,四个也是不行的,凭你的智商应该可以理解吧。

解决方案:回溯与递归。

介绍:

1.回溯法

回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。参见百度百科

2.递归法

阶乘 n! = 1 x 2 x 3 x ... x n

用函数fact(n)表示,可以看出:

fact(1) = 1

fact(n) = n!

           = 1 x 2 x 3 x ... x (n-1) x n

           = (n-1)! x n

           = fact(n-1) x n

于是,fact(n)用递归的方式写出来就是:

def fact(n):
  if n==1:
    return 1
  return n * fact(n - 1)

如果计算fact(5),结果如下:

===> fact(5)
===> 5 * fact(4)
===> 5 * (4 * fact(3))
===> 5 * (4 * (3 * fact(2)))
===> 5 * (4 * (3 * (2 * fact(1))))
===> 5 * (4 * (3 * (2 * 1)))
===> 5 * (4 * (3 * 2))
===> 5 * (4 * 6)
===> 5 * 24
===> 120

使用递归函数需要注意防止栈溢出。在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。由于栈的大小不是无限的,所以,递归调用的次数过多,会导致栈溢出。可以试试fact(1000):

>>> fact(1000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in fact
  ...
  File "<stdin>", line 4, in fact
RuntimeError: maximum recursion depth exceeded

解决递归调用栈溢出的方法是通过尾递归优化。

尾递归是指,在函数返回的时候,调用自身本身,并且,return语句不能包含表达式。这样,编译器或者解释器就可以把尾递归做优化,使递归本身无论调用多少次,都只占用一个栈帧,不会出现栈溢出的情况。如:

def factorial(n, acc=1):
  if n == 0:
    return acc
  return factorial(n-1, n*acc)

函数返回时只调用了它本身factorial(n-1, n*acc)

问题是Python标准的解释器没有针对尾递归做优化,任何递归函数都存在栈溢出的问题。

python源码:

# -*- coding: utf-8 -*-
#python默认为ascii编码,中文编码可以用utf-8
import random
#随机模块

def conflict(state,col):
    #冲突函数,row为行,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(solution):
    #打印函数
    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())))

结果:

(0, 4, 7, 5, 2, 6, 1, 3)
(0, 5, 7, 2, 6, 3, 1, 4)
(0, 6, 3, 5, 7, 1, 4, 2)
(0, 6, 4, 7, 1, 3, 5, 2)
(1, 3, 5, 7, 2, 0, 6, 4)
(1, 4, 6, 0, 2, 7, 5, 3)
(1, 4, 6, 3, 0, 7, 5, 2)
(1, 5, 0, 6, 3, 7, 2, 4)
(1, 5, 7, 2, 0, 3, 6, 4)
(1, 6, 2, 5, 7, 4, 0, 3)
(1, 6, 4, 7, 0, 3, 5, 2)
(1, 7, 5, 0, 2, 4, 6, 3)
(2, 0, 6, 4, 7, 1, 3, 5)
(2, 4, 1, 7, 0, 6, 3, 5)
(2, 4, 1, 7, 5, 3, 6, 0)
(2, 4, 6, 0, 3, 1, 7, 5)
(2, 4, 7, 3, 0, 6, 1, 5)
(2, 5, 1, 4, 7, 0, 6, 3)
(2, 5, 1, 6, 0, 3, 7, 4)
(2, 5, 1, 6, 4, 0, 7, 3)
(2, 5, 3, 0, 7, 4, 6, 1)
(2, 5, 3, 1, 7, 4, 6, 0)
(2, 5, 7, 0, 3, 6, 4, 1)
(2, 5, 7, 0, 4, 6, 1, 3)
(2, 5, 7, 1, 3, 0, 6, 4)
(2, 6, 1, 7, 4, 0, 3, 5)
(2, 6, 1, 7, 5, 3, 0, 4)
(2, 7, 3, 6, 0, 5, 1, 4)
(3, 0, 4, 7, 1, 6, 2, 5)
(3, 0, 4, 7, 5, 2, 6, 1)
(3, 1, 4, 7, 5, 0, 2, 6)
(3, 1, 6, 2, 5, 7, 0, 4)
(3, 1, 6, 2, 5, 7, 4, 0)
(3, 1, 6, 4, 0, 7, 5, 2)
(3, 1, 7, 4, 6, 0, 2, 5)
(3, 1, 7, 5, 0, 2, 4, 6)
(3, 5, 0, 4, 1, 7, 2, 6)
(3, 5, 7, 1, 6, 0, 2, 4)
(3, 5, 7, 2, 0, 6, 4, 1)
(3, 6, 0, 7, 4, 1, 5, 2)
(3, 6, 2, 7, 1, 4, 0, 5)
(3, 6, 4, 1, 5, 0, 2, 7)
(3, 6, 4, 2, 0, 5, 7, 1)
(3, 7, 0, 2, 5, 1, 6, 4)
(3, 7, 0, 4, 6, 1, 5, 2)
(3, 7, 4, 2, 0, 6, 1, 5)
(4, 0, 3, 5, 7, 1, 6, 2)
(4, 0, 7, 3, 1, 6, 2, 5)
(4, 0, 7, 5, 2, 6, 1, 3)
(4, 1, 3, 5, 7, 2, 0, 6)
(4, 1, 3, 6, 2, 7, 5, 0)
(4, 1, 5, 0, 6, 3, 7, 2)
(4, 1, 7, 0, 3, 6, 2, 5)
(4, 2, 0, 5, 7, 1, 3, 6)
(4, 2, 0, 6, 1, 7, 5, 3)
(4, 2, 7, 3, 6, 0, 5, 1)
(4, 6, 0, 2, 7, 5, 3, 1)
(4, 6, 0, 3, 1, 7, 5, 2)
(4, 6, 1, 3, 7, 0, 2, 5)
(4, 6, 1, 5, 2, 0, 3, 7)
(4, 6, 1, 5, 2, 0, 7, 3)
(4, 6, 3, 0, 2, 7, 5, 1)
(4, 7, 3, 0, 2, 5, 1, 6)
(4, 7, 3, 0, 6, 1, 5, 2)
(5, 0, 4, 1, 7, 2, 6, 3)
(5, 1, 6, 0, 2, 4, 7, 3)
(5, 1, 6, 0, 3, 7, 4, 2)
(5, 2, 0, 6, 4, 7, 1, 3)
(5, 2, 0, 7, 3, 1, 6, 4)
(5, 2, 0, 7, 4, 1, 3, 6)
(5, 2, 4, 6, 0, 3, 1, 7)
(5, 2, 4, 7, 0, 3, 1, 6)
(5, 2, 6, 1, 3, 7, 0, 4)
(5, 2, 6, 1, 7, 4, 0, 3)
(5, 2, 6, 3, 0, 7, 1, 4)
(5, 3, 0, 4, 7, 1, 6, 2)
(5, 3, 1, 7, 4, 6, 0, 2)
(5, 3, 6, 0, 2, 4, 1, 7)
(5, 3, 6, 0, 7, 1, 4, 2)
(5, 7, 1, 3, 0, 6, 4, 2)
(6, 0, 2, 7, 5, 3, 1, 4)
(6, 1, 3, 0, 7, 4, 2, 5)
(6, 1, 5, 2, 0, 3, 7, 4)
(6, 2, 0, 5, 7, 4, 1, 3)
(6, 2, 7, 1, 4, 0, 5, 3)
(6, 3, 1, 4, 7, 0, 2, 5)
(6, 3, 1, 7, 5, 0, 2, 4)
(6, 4, 2, 0, 5, 7, 1, 3)
(7, 1, 3, 0, 6, 4, 2, 5)
(7, 1, 4, 2, 0, 6, 3, 5)
(7, 2, 0, 5, 1, 4, 6, 3)
(7, 3, 0, 2, 5, 1, 6, 4)
  total number is 92
  one of the range is:

X . . . . . . . 
. . . . . . X . 
. . . X . . . . 
. . . . . X . . 
. . . . . . . X 
. X . . . . . . 
. . . . X . . . 
. . X . . . . . 

源码解析:

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

冲突函数:

def conflict(state,col):
  #冲突函数,row为行,col为列
  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=7,这时abs ( state[0]-7 ) in (0 , 3-0)为真,因为abs (4-7)=3,如:

. . . . X . . . 
. . . . . . . X 
. . . X . . . .

. . . . . . . X 对角线冲突

你们这么聪明,该重要语句应该懂吧。

生成器函数:

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

生成器:

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

参考:生成器

步骤:

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,第一行放在第一列,这时不会冲突,但是不会进入if,因为还没到达倒数第二行,进入else后,再调用queens(num, state+(pos,),这时进入第二行,再次递归展开则是queens(num,state+(pos, )+(pos, ) ),到达最后一行时返回(pos, ),再返回倒数第二行,再返回倒数第三行,最后到达最开始那层(pos, )+result, pos为第一行皇后所在列,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(queens())))