递归方法解决八皇后

garyneville

                  我暂时只能看明白全排列的递归实现，效率已经比我那个愚蠢的方法快了两个数量级。
               
               
                #!/usr/bin/python
import time
def display (x):
    i = 0
    while i8:
        print x
        i+=1
def display_method (method):
    x = [[0 for i in range(8)] for j in range(8)]
    for i in range(8):
        x[method[0]][method[1]]=1
    display(x)
def perm(s,k,m):
    if k==m:
        if(True==test(s[0],s[1],s[2],s[3],s[4],s[5],s[6],s[7])):
        print s
    else:
        for i in range(m-k+1):
            s[k],s[i+k]=s[i+k],s[k]
            perm(s,k+1,m)
            s[k],s[i+k]=s[i+k],s[k]
index = 1
def test(pos1 ,pos2 ,pos3,pos4,pos5,pos6,pos7,pos8) :
    global index
    method =([0,pos1],[1,pos2],[2,pos3],[3,pos4],[4,pos5],[5,pos6],[6,pos7],[7,pos8])
    for i in range(8):
        for j in range(i+1,8):
            if attack(method,method[j])==True:
                return False
    print "**************************"
    display_method(method)
    print "This is " + str(index) + "method"
    index+=1
    return True
def attack(x,y):
    if x[1] == y[1]:
        return True
    if ((x[0]-y[0])**2) == ((x[1]-y[1])**2):
        return True
    return False
x = [i for i in range(8)]
cur_time1=time.time()
print "Start time "+time.strftime( "%Y-%m-%d %X", time.localtime() )
perm(x,0,7)
cur_time2=time.time()
print "End time "+time.strftime( "%Y-%m-%d %X", time.localtime() )
print "Waste time "+str(cur_time2-cur_time1)+" seconds"
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/72023/showart_1979214.html