Python 实现八皇后问题

初学 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[i][pos]=1
    
    if check(i,pos):
        i=i+1
        pos=0
    else:
        chess[i][pos]=0
        while pos<7 and not check(i,pos):
            pos=pos+1
        
        if pos<=7 and check(i,pos): 
            chess[i][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