Python 实现八皇后问题

pqwsa

　　初学 Python ， 写了一个八皇后的小程序，虽然算法效率不高，但这次是第一个用python实现

chess=[[0 for col in range(8)] for row in range(8)]
pos =0
i=0
flag =0
def check(i,pos):  
if i==0:
return True
for counter in range(i):
if chess[counter][pos]==1:
return False
for x in range(min(i,pos)):
if chess[i-x-1][pos-x-1]==1:
return False
if pos<7:
for y in range(min(i,7-pos)):
if  chess[i-y-1][pos+y+1]==1:
return False
return True
while i<8:
chess[pos]=1
if check(i,pos):
i=i+1
pos=0
else:
chess[pos]=0
while pos<7 and not check(i,pos):
pos=pos+1
if pos<=7 and check(i,pos):
chess[pos]=1
i=i+1
pos=0
else:
if (chess[i-1].index(1))<7:
pos = chess[i-1].index(1)+1
chess[i-1][pos-1]=0
i=i-1
else:
if i>=2:
pos =chess[i-2].index(1)+1
chess[i-1][7]=0
chess[i-2][pos-1]=0
i=i-2
else:
break
if 1 in chess[7]:
flag=flag+1
##        print "%d:Found:"%(flag)
##        
##        for k in range(len(chess)):
##            print chess[k]
##        
##        print
##        print "*"*30
if (chess[7].index(1))<7:
pos = chess[7].index(1)+1
chess[7][pos-1]=0
i=7
else:
pos =chess[6].index(1)+1
chess[7][7]=0
chess[6][pos-1]=0
i=6
print "there are %d solutions" %flag



　　去掉程序中的注释，可以得到全部解：

******************************
90:Found:
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0]
******************************
91:Found:
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 0, 0, 0]
******************************
92:Found:
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 1, 0, 0, 0]
******************************
there are 92 solutions