用python求解N皇后问题

算法1：

N=4
count=0
a=[0,0,0,0,0,0,0,0]

#count=0
def backtrack(t):
    if t==N:
        global count           #此语句不可少，否则下面对count进行修改时
        count += 1             #count会当做是局部变量而报错
        for i in range(N):
            for j in range(N):
                if a[i]==j: print ,
                else: print '*' ,
            print ''
        print ''
    else:
        for i in range(N):
            a[t]=i;
            flag = 1
            for j in range(t):
                if (abs(a[t]-a[j])==abs(t-j) or a[t]==a[j]) :
                    flag=0
                    break
            if flag:backtrack(t+1)

backtrack(0)
print '解的个数为',count

 

***********************************************************

***********************************************************

***********************************************************

算法2：

N=4
count=0
a=[]

#count=0
def backtrack(t):
    if t==N:
        global count
        count += 1
        for i in range(N):
            for j in range(N):
                if a[i]==j: print ,
                else: print '*' ,
            print ''
        print ''
    else:
        for i in range(N):
            a.append(i);
            flag = 1
            for j in range(t):
                if (abs(a[t]-a[j])==abs(t-j) or a[t]==a[j]) :
                    flag=0
                    break
            if flag:backtrack(t+1)
            a.pop()

backtrack(0)
print '解的个数为',count

 

*********************************************************

*********************************************************

*********************************************************

算法3：

N=4
count=0

def backtrack(t,a):    # t为下标,a为列表
    if t==N:
        global count
        count += 1
        for i in range(N):
            for j in range(N):
                if a[i]==j: print ,
                else: print '*' ,
            print ''
        print ''
    else:
        for i in range(N):
            a.append(i);
            flag = 1
            for j in range(t):
                if (abs(a[t]-a[j])==abs(t-j) or a[t]==a[j]) :
                    flag=0
                    break
            if flag:backtrack((t+1),a)
            a.pop()

a=[]
backtrack(0,a)
print '解的个数为',count

 

******************************************************

******************************************************

算法4：------生成迭代器

def conflict(state,y):
    x_num=len(state)
    for i in range(x_num) :
        if abs(state[i]-y) in (0,x_num - i) :
            return True
    return False

 

def queens(num=8,state=()):
    for pos in range(num):
        if not conflict(state,pos):
            if len(state) == num-1:
                yield (pos,)
            else:
                for result in queens(num,state+(pos,)):
                    yield (pos,)+result

 

def Queens(n):
    for result in list(queens(n)):
        for i in range(n):
            for j in range(n):
                if result[i] == j:
                    print ,
                else:
                    print '*',
            print ''
        print result,'\n'

 

 

####### test
Queens(4)

 

****************************************************

****************************************************

算法5：（由算法2修改而成）------生成迭代器

N=4
count=0
a=[]
#count=0
def backtrack(t):
    if t==N:
        global count
        count += 1
        for i in range(N):
            for j in range(N):
                if a[i]==j: print ,
                else: print '*' ,
            print ''
        print ''
        yield ()
    else:
        for i in range(N):
            a.append(i);
            flag = 1
            for j in range(t):
                if (abs(a[t]-a[j])==abs(t-j) or a[t]==a[j]) :
                    flag=0
                    break
            if flag:
                for result in backtrack(t+1):
                    yield (a[t],)+result
            a.pop()

a=list(backtrack(0))
print '解的个数为',count
print a