queen.py

用Python实现的八皇后问题

#八皇后问题递归解法
class EQueen:
    
    num=0             #保存解的个数
    data=range(0,8)   #保存解
    
    def isPlace(self,t):   #判断t是否可以放置
        for i in range(0,t):
            if EQueen.data[i]==EQueen.data[t]:
                return 0
            if abs(EQueen.data[i]-EQueen.data[t])==abs(i-t):
                return 0
        return 1

    def queen(self,t):  #对t进行操作
        if t==8:
            EQueen.num+=1
            print EQueen.data
        else:
            for i in range(0,8):
                EQueen.data[t]=i
                if self.isPlace(t):
                    self.queen(t+1)

#八皇后问题非递归解法
class EQueeny:
    
    num=0
    data=range(0,8)
    
    def isPlace(self,t):
        for i in xrange(0,t):
            if EQueeny.data[i]==EQueeny.data[t]:
                return 0
            if abs(EQueeny.data[i]-EQueeny.data[t])==abs(i-t):
                return 0
        return 1
    def queen(self):
        i=0
        EQueeny.data[i]=-1
        while i>=0:
            EQueeny.data[i]+=1
            while EQueeny.data[i]<8 and not self.isPlace(i):
                EQueeny.data[i]+=1
            if EQueeny.data[i]<8:
                if i==7:
                    print EQueeny.data
                    EQueeny.num+=1
                else:
                    i+=1
                    EQueeny.data[i]=-1
            else:
                i-=1
#非递归解法            
eqy=EQueeny()
eqy.queen()
print eqy.num

print '*****************'

#递归解法
eq=EQueen()
eq.queen(0)
print eq.num