n皇后问题的优化解法,n皇后解法,采用打乱安置次序的优化来
n皇后问题的优化解法,n皇后解法,采用打乱安置次序的优化来
采用打乱安置次序的优化来解决问题
num=8class Queen(object): def __init__(self,n): self.lct= n self.prs=-1 self.cdt=[1 for i in range(num)]def Count(q): s=0 for i in range(num): if q.cdt[i]>0:s+=1 return sdef FindIt(q): u=q.prs+1; while u<num and q.cdt[u]<=0:u+=1 if u<num: q.prs=u return True return Falsedef Settle(q,n): x=q[n].lct y=q[n].prs for i in range(n+1,num,1): p=q[i].cdt p[y]-=1 a=q[i].lct-x b=y-a if b>=0 and b<num:p[b]-=1 b=y+a if b>=0 and b<num:p[b]-=1def Pickup(q,n): x=q[n].lct y=q[n].prs for i in range(n+1,num,1): p=q[i].cdt p[y]+=1 a=q[i].lct-x b=y-a if b>=0 and b<num:p[b]+=1 b=y+a if b>=0 and b<num:p[b]+=1def Select(q,n): j,k=0,num+1 for i in range(n,num): t=Count(q[i]) if k>t:j,k=i,t if j!=n:q[n],q[j]=q[j],q[n]def ShowIt(q): for i in range(num): for j in range(num): if q[j].lct==i: for k in range(num): if q[j].prs==k: print '*', else: print '-', print '' print ''def Locate1(): q=[Queen(i) for i in range(num)] i=0 j=0 while 1: if q[i].prs<0: Select(q,i) else: Pickup(q,i) if FindIt(q[i]): if i<num-1: Settle(q,i) i+=1 else: j+=1 yield j #ShowIt(q) else: q[i].prs=-1 i-=1 if i<0:breakdef Locate2(): q=[Queen(i) for i in range(num)] i=0 j=0 while 1: if q[i].prs>=0:Pickup(q,i) if FindIt(q[i]): if i<num-1: Settle(q,i) i+=1 else: j+=1 yield j #ShowIt(q) else: q[i].prs=-1 i-=1 if i<0:breakif __name__=='__main__': q=[Queen(i) for i in range(num)] import time t=time.time() Locate1().next() print 'once cost %.6f'%(time.time()-t) print '-----------------' t=time.time() Locate2().next() print 'once cost %.6f'%(time.time()-t)#该片段来自于http://byrx.net
相关内容
- Python版国旗,python国旗,from matplot
- 创建并修改excel,创建修改excel,创建一个excel,并且
- Gimp的python-plugins,gimppython-plugins,在用户选择图片上需要
- 获取主要城市的及时气温,获取主要城市气温,#coding=
- 登录网站,,from urllib
- 多线程采集图片,多线程采集,#! /usr/bin/
- python果然适合演示算法,python演示算法,def calc(str
- 使用python的正则表达式做词法分析器,python词法,#!use
- 很好玩的一个面试题,很好玩一个面试题,给定一个一亿
- 简单的生成html,简单生成html,class Tag:
评论关闭