n皇后问题的优化解法代码,Python代码库,德仔网

代码语言

代码分类

【Python】 n皇后问题的优化解法

作者:刘地 / 发布于2012/11/19/ 711

num=8

class 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 s

def 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 False

def 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]-=1

def 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]+=1

def 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:break

def 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:break
	
if __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)

试试其它关键字

　n皇后　

同语言下

可能有用的

刘地贡献的其它代码(3)