鱼C论坛Python精英挑战赛（第二季03期）

jerryxjr1220

鱼C论坛Python精英挑战赛第二季又开始啦！

本季挑战赛依旧会有精彩的题目供大家挑战，大量鱼币奖励等你赢取！

                               
登录/注册后可看大图

本期题目：N皇后问题

背景知识：
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。

拓展：
一皇后只有唯一解。
二皇后和三皇后，是无解的。
四皇后问题：在4x4的棋盘上，只有2个解。即：

	x
			x
x
		x

和

		x
x
			x
	x

同样的，五皇后问题：在5x5的棋盘上，共有10个解。
六皇后问题：在6x6的棋盘上，共有4个解。

求一皇后到十皇后的所有问题中，总共有多少组解？

请仔细审题，题目要求的是返回所有一到十皇后问题中，一共有多少组解，不需要每种情况单独列出，只要总数即可，回帖时请务必附带上答案！

比赛规则：
本题为纯算法题，要求输出结果正确，运行时间最短的鱼油即为优胜者。比赛截止日期：8月17日24时。

优胜者奖励100鱼币，由@小甲鱼 老师倾情赞助！

@冬雪雪冬 @～风介～ @SixPy

小火木

from itertools import permutations

def slash(matrix):
    X=set()
    Y=set()
    for line in matrix:
        x=line +matrix.index(line)
        y=line - matrix.index(line)-1
        if x in X or y in Y:
            return False
        else:           
            X.add(x)
            Y.add(y)

    return True



if __name__=="__main__":
    for i in range(1,11):
        count=0
        data=permutations([i for i in range(1,i+1)],i)
        for matrix in data:
            if slash(matrix):count+=1
        print("在%d皇后问题中，总共有%d组解"%(i,count))

  

Cathaysian

from itertools import *
#现在才发现看错题目了，以为八皇后呢

第一次回帖有点小激动

小锟

def confict(list1 , weizhi , n):
    '''判断是否冲突'''
    row_num = weizhi[0] 
    column_num = weizhi[1] 
    #判断行
    for column in list1[row_num] :
        if column :
            return True
    #判断列
    for row in list1 :
        if row[column_num] :
            return True
    #判断左斜线
    while row_num >= 0 and column_num >= 0 :
        if list1[row_num][column_num]:
            return True
        row_num -= 1
        column_num -= 1
    #判断右斜线
    while weizhi[0] >= 0 and weizhi[1] < n :
        if list1[weizhi[0]][weizhi[1]]:
            return True
        weizhi[0] -= 1
        weizhi[1] += 1

    return False


def huisu(list1 , jilu):
    '''进行回溯的函数，返回上一次的位置'''
    last = jilu.pop()
    i = last[0]
    j = last[1]
    list1[i][j] = 0
    return list1 , jilu , i ,j 

    

sumresult = 0
for n in range(1,11):
    #生成 n * n 的列表
    list1 = [[0 for i in range(n)] for j in range(n)]
    i , result = 0 , 0
    jilu = []
    try :
        while len(jilu) >= 0:
            count = 0
            j = 0
            while j <= n - 1:
                if not confict(list1 , [i,j] ,n):
                    list1[i][j] = 1
                    jilu.append([i,j])
                    #如果到了最后一行
                    if i == n-1:
                        result += 1
                        list1[i][j] = 0
                        jilu.pop()
                        list1 , jilu ,i, j = huisu(list1 , jilu)
                        # 如果回溯的结果已经在最后一列，需要继续回溯
                        if j == n-1:
                            list1 , jilu ,i, j = huisu(list1 , jilu)
                        j += 1
                        count = j
                        continue
                    else:
                        i += 1
                        break
                else:
                    count += 1
                    #如果这一行都不可以放皇后
                    if count == n :
                        list1 , jilu ,i, j = huisu(list1 , jilu)
                        # 如果回溯的结果已经在最后一列，需要继续回溯
                        if j == n-1:
                            list1 , jilu ,i, j = huisu(list1 , jilu)
                        j += 1
                        count = j
                        continue
                j += 1

    except  IndexError:
        #因为所有方案都出来后，jilu列表将会空，无法弹出，用异常处理
        #print('%s皇后有%s个方案' % (n,result))
        sumresult += result
        print('一共有%s种方案' % (sumresult))

撒法空间

#!/usr/bin/env python3
#coding:utf-8


def conflict(state, col):
    row = len(state)
    for i in range(row):
        if abs(state[i] - col) in (0, row - 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

total = 0
for x in range(1,11):
    total += len(list(queens(x)))
print('一皇后至10皇后总共有' + str(total)+'组解')

所有一到十皇后问题中，一共有1225组解！

qwc3000

lists = []
temp_list1 = []
temp_list2 = []
for i in range(1, 9):
    for j in range(1, 9):
        lists.append([i, j])
temp_list2=lists.copy()
for a1 in lists:
    temp_list2.remove(a1)
    for a2 in temp_list2:
        if a2[0] != a1[0] and a2[1] != a1[1]:
            if abs(a2[0]-a1[0]) != abs(a2[1]-a1[1]):
                temp_list1.append([a1, a2])
# print(len(temp_list1))
# print(temp_list1)
#   三层
temp_out=[]
temp_in=temp_list1.copy()
temp_sort=[]
temp_logo=0
temp=[]
for a1 in lists:
    for a2 in temp_in:
        for i in range(0, 2):
            if a2[i][0] != a1[0] and a2[i][1] != a1[1]:
                if abs(a2[i][0] - a1[0]) != abs(a2[i][1] - a1[1]):
                    temp_logo =temp_logo+1
        if temp_logo==2:
            temp_logo=0
            temp=[a2[0], a2[1], a1]
            temp.sort()
            temp_out.append(temp)
        temp_logo=0
temp_sort.clear()
for i in temp_out:
    if i not in temp_sort:
        temp_sort.append(i)
temp_out=temp_sort.copy()
temp_list3=temp_out.copy()

def fun_find(temp_list3, num):
    temp_out = []
    temp_in = temp_list3.copy()
    temp_sort = []
    temp = []
    temp_logo = 0
    num=num-1
    for a1 in lists:
        for a2 in temp_in:
            for i in range(0, num):
                if a2[i][0] != a1[0] and a2[i][1] != a1[1]:
                    if abs(a2[i][0] - a1[0]) != abs(a2[i][1] - a1[1]):
                        temp_logo = temp_logo + 1
            if temp_logo == num:
                temp_logo = 0
                temp = a2.copy()
                temp.append(a1)
                temp.sort()
                temp_out.append(temp)
            temp_logo = 0
    temp_sort.clear()
    for i in temp_out:
        if i not in temp_sort:
            temp_sort.append(i)
    temp_out = temp_sort.copy()
    temp= temp_out.copy()
    return temp

temp_list3=fun_find(temp_list3,4)
temp_list3=fun_find(temp_list3,5)
temp_list3=fun_find(temp_list3,6)
temp_list3=fun_find(temp_list3,7)
temp_list3=fun_find(temp_list3,8)
print(len(temp_list3))
print(temp_list3)

qwc3000

我只是参与下   我的运行感觉好慢啊

小剑剑

def n_queens(queen):
    save=[]
    col=0
    row=[i for i in range(queen)]
    queens=[]
    save.append((queens,col,row))
    result=0
    while save:
        temp=save.pop()
        col=temp[1]
        if  col ==queen:
            result+=1
            continue
        row=temp[2]
        queens=temp[0]
        i=col
        for j in row:
            judge=True
            for q in queens:
                c=abs(q[0]-i)
                r=abs(q[1]-j)
                if c==r:
                    judge=False
                    break
            if judge:
                t1 = queens[:]
                t1.append((i, j))
                t2 = col+1
                t3 = row[:]
                t3.remove(j)
                save.append((t1, t2, t3))
    return result

print(sum(map(n_queens,[i for i in range(1,11)])))

1225

huyu

不会下象棋

michaelol

哇，人比较笨 ，写了好久。主要难点在斜线检测和递归调用。答案：1225个  代码如下 result[]中存放了所有结果：

import copy

#直线的检查方法：
def row_check(coor,i,j,n):      #行检测
    for each in range(n):
        if coor[i][each]==1:
            return 0
    else:
        return 1

def column_check(coor,i,j,n):  #列检测
    for each in range(n):
        if coor[each][j]==1:
                return 0
    else:
        return 1
def slash_check(coor,i,j,n):  #斜线检测
    if i>j:
        for delta in range(n-i+j):
            if coor[i-j+delta][delta]==1:
                return 0
    elif i==j:
        
        for delta in range(n):
            if coor[delta][delta]==1:
                return 0
        if 2*i-n+1>=0:
            for delta in range(2*n-2*i-1):
                if coor[n-delta-1][2*i-n+1+delta]==1:
                    return 0
        else:
            for delta in range(2*i+1):
                if coor[2*i-delta][delta]==1:
                    return 0
    else:
        for delta in range(n-j+i):
            if coor[delta][j-i+delta]==1:
                return 0
    if i+j>=n-1:
        
        for delta in range(2*n-i-j-2+1):
            if coor[n-1-delta][i+j+1-n+delta]==1:
                return 0
    else:
        
        for delta in range(i+j+1):
            if coor[i+j-delta][delta]==1:
                return 0

    return 1
def check(coor,i,j,n):    #检测是否可以放置皇后  可以返回1 否则返回0
    a=row_check(coor,i,j,n)
    b=column_check(coor,i,j,n)
    c=slash_check(coor,i,j,n)
    if a and b and c:
        return 1
    else:
        return 0


def backtracking(coor,i,n):
    if i==n-1:
       
        for j in range(n):
            if check(coor,i,j,n):
                coor[i][j]=1
                global result
                result.append(copy.deepcopy(coor))
                coor[i][j]=0              
                return result
            
    for j in range(n):
       
        if check(coor,i,j,n):
            coor[i][j]=1
            i+=1
            backtracking(coor,i,n)
            i-=1
            coor[i][j]=0
    return result

def queen(n):

    checkerboard=[[0 for i in range(n)]for i in range(n)]
    return backtracking(checkerboard,0,n)
   


result=[]
for n in range(1,11):    
    queen(n)
print(len(result))

gunjang

import time
def canput(x, y): #[0..n)
        if (x >= n) or (y >= n):
                return False
        #column
        for i in range(y):
                if queen[i] == x:
                        return False
        #Left Top 45 degree
        for i in range(x):
                if queen[y-i-1]-(y-i-1) == x - y:
                        return False
        #Right Top 135 degree
        for i in range(n-1-x):
                if (x+y) == (queen[y-i-1]+(y-i-1)):
                        return False
        return True

st = time.time()
count = 1
maxn = 10
for n in range(2, maxn+1):
        queen = [-1 for i in range(n)]
        y = 0
        halfcnt = 0
        while True:
                x = queen[y]+1
                while not canput(x, y):
                        x += 1
                        if x >= n:
                                break
                if (y==0) and (x >= (n+1)//2): #symmetrical 
                        #print(n, halfcnt, midcnt)
                        break
                if canput(x, y):
                        #put queen
                        queen[y] = x
                        if y == n-1:
                                #print(queen) #
                                if (n%2==1) and (queen[0] == n//2) and (queen[1] > n//2): #symmetrical 
                                        break
                                else:
                                        halfcnt += 1
                                queen[y] = -1 #reset
                                y -= 1
                                continue
                                #break #return one solve
                        else:
                                y += 1
                else:
                        queen[y] = -1 #reset
                        y -= 1
                        if y == -1:
                                break

        count += 2*halfcnt

cost = time.time()-st
print(count) #1225
print(cost) #1.84375 => 1.71875 => 0.828125

答案：1225

小風

def conflict(state, nextx):  
    nexty = len(state)  
    for i in range(nexty):  
        if abs(state[i]-nextx) in (0, nexty-i):  
            return True  
    return False  
  
  
def queens(num=1, 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  
  
  
if __name__ == "__main__":
    print len(list(queens(10)))

724

小Q学Python

def nQ(m):
    a = [None]*m
    def nQueen(n):
        global counts
        if n == m:
            counts+=1
        for i in set(range(m))-set(a[:n]):
            if n!=0 and abs(i-a[n-1])==1:
                continue
            flag = 0
            for x,y in enumerate(a[:n]):
                if n-i == x-y or n+i == x+y :
                    flag = 1
                    break
            if flag==0:
                a[n]=i
                nQueen(n+1)
    
    nQueen(0)

counts = 0
for i in range(1,11):
    nQ(i)
print(counts)

%time %run untitled0.py
1225
Wall time: 401 ms

影乖

我不会，我只是来顶贴的……

bozhen

from itertools import permutations

def getcount(x):
    count = 0
    for vec in permutations(range(x)):
        if (x == len(set(vec[i]+i for i in range(x)))== len(set(vec[i]-i for i in range(x)))):
            count += 1
    return count

counts = 0
for i in range(1,11):
    counts += getcount(i)

print(counts)

gunjang

import time

st = time.time()
count = 1
maxn = 10
for n in range(2, maxn+1):
        queen = [-1 for i in range(n)]
        column = [False for i in range(n)]
        LB45 = [False for i in range(2*n-2+1)] # leftbottom, sum of x and y
        RB135 = [False for i in range(2*n-2+1)] # x-y in [1-n..n-1] ,so index=x-y+n-1
        y = 0
        halfcnt = 0
        while True:
                x = queen[y]+1
                #while (x < n) and not canput(x, y):
                while  (x < n) and (column[x] or LB45[x+y] or RB135[x-y+n-1]):
                        x += 1

                if (y==0) and (x >= (n+1)//2): #symmetrical 
                        break
                if x < n:#if canput(x, y):
                        #put queen
                        queen[y] = x
                        
                        if y == n-1:
                                #print(queen) #symmetrical is [n-x for x in queen]
                                if (n%2==1) and (queen[0] == n//2) and (queen[1] > n//2): #symmetrical 
                                        break
                                else:
                                        halfcnt += 1
                                queen[y] = -1 #reset
                                y -= 1
                                column[queen[y]] = False
                                LB45[queen[y]+y] = False
                                RB135[queen[y]-y+n-1] = False
                                continue        # or break #return one solve
                        else:
                                column[x] = True
                                LB45[x+y] = True
                                RB135[x-y+n-1] = True
                                y += 1
                else:
                        queen[y] = -1 #reset
                        y -= 1
                        if y == -1:
                                break
                        column[queen[y]] = False
                        LB45[queen[y]+y] = False
                        RB135[queen[y]-y+n-1] = False

        count += 2*halfcnt

cost = time.time()-st
print(count) #1225
print(cost) #1.84375 => 1.71875 => 0.828125 => 0.28124403953552246

答案1225，v2版速度更快

gunjang

应版主要求，加了注释版，当然小细节调整

'''
http://bbs.fishc.com/thread-94433-1-1.html
'''
import time

st = time.time()
count = 1
maxn = 10
for n in range(2, maxn+1):
        queen = [-1 for i in range(n)]
        column = [False for i in range(n)]
        LB45 = [False for i in range(2*n-2+1)] # leftbottom, sum of x and y
        RB135 = [False for i in range(2*n-2+1)] # x-y in [1-n..n-1] ,so index=x-y+n-1
        y = 0
        halfcnt = 0
        while True:
                x = queen[y]+1
                #while (x < n) and not canput(x, y):
                while  (x < n) and (column[x] or LB45[x+y] or RB135[x-y+n-1]):
                        x += 1

                if (y==0) and (x >= (n+1)//2): #symmetrical 
                        break
                if (y==1) and (n%2==1) and (queen[0] == n//2) and (x > n//2): #symmetrical 
                        break

                if x < n:#if canput(x, y):
                        #put queen
                        queen[y] = x
                        
                        if y == n-1:
                                #print(queen) 
                                #symmetrical is [n-x for x in queen]
                                halfcnt += 1
                                queen[y] = -1 #reset
                                y -= 1
                                column[queen[y]] = False
                                LB45[queen[y]+y] = False
                                RB135[queen[y]-y+n-1] = False
                                continue        # or break #return one solve
                        else:
                                column[x] = True
                                LB45[x+y] = True
                                RB135[x-y+n-1] = True
                                y += 1
                else:
                        queen[y] = -1 #reset
                        y -= 1
                        if y == -1: #all solve
                                break
                        column[queen[y]] = False
                        LB45[queen[y]+y] = False
                        RB135[queen[y]-y+n-1] = False

        count += 2*halfcnt

cost = time.time()-st
print(count) #1225
print(cost) #1.84375 => 1.71875 => 0.828125 => 0.171875

'''
算法： 采用回溯法，非递归方式（python的递归效率不高，而且龟叔对优化递归没啥兴趣)
while 循环 (16-55行)
        试着在当前行放入queen（x,y) （17-20行）
        可以的话  保存位置，下一行y+1
        否则就回溯， y-1

    需要注意的是状态的保存
    这里用三个变量表示 碰撞判断（原来是一个函数canput)
def canput(x, y): #[0..n)
        if (x >= n) or (y >= n):
                return False
        #column
        for i in range(y):
                if x == queen[i]:
                        return False
        #Left Top
        for i in range(x):
                if queen[y-i-1]-(y-i-1) == x - y:
                        return False
        #Right Top
        for i in range(n-1-x):
                if (x+y) == (queen[y-i-1]+(y-i-1)):
                        return False
        return True
        直接用三个状态判断（列 左斜线 右斜线）快速判断    
    column[x] 表示 x列已经有皇后了
    LB45是左下角45度 已经 有皇后了， 所有这个角度的x+y的和是相同的
    RB135则是右下角135度， 所有这个角度的x-y是相同的，因为list的index最小是0，所以取值的时候index要加上n-1

    当保存的时候， column等三个变量设置True（42-44行）
    当回溯的时候，column要恢复为False （37-39 51-53）
    40行continue改成break时，就相当于只求一个解

上面这些就是典型的非递归回溯算法实现八皇后问题
理论上一个点在n*n中有8个镜像（上下、左右、斜45度、135度对称和旋转90 180 270度），当然有些解的镜像中是重复的（怎么持续优化是另一个问题了）
本程序特色就是利用其中的左右对称原理进行改进
大家可以看下4皇后的解 1,3,0,2和2,0,3,1
每一行的皇后位置都是竖直中线对称的
所以只要求出中线左边的解，对称的解就出来了(对称解为[n-x for x in queen]）
因为采用回溯法，所以只要判断第一行的x不超过中线就好了
见22行
注意判断的是当n是偶数的时候，对称界限是第一行时 x > x//2-1
当n是奇数时，对称界限是 (x//2, 0)
结果*2就是实际全部解的数量(55行)

看问题规模（n=10)，回溯和暴力法估计都可以选（这个13皇后约20几秒，解释语言和编译语言毕竟存在差别）
python的语言相对高级，位运算等优化我还不知道怎么实现，更多关注算法的改进
如果n的规模比较大，目测可以采用高爷爷dance link x
那个实现起来太麻烦了---python还没试过实现
'''

答案1225
算是v2.1吧

pingws928

def place(x, k):
    for i in range(1, k):
        if x[i] == x[k] or abs(x[i] - x[k]) == abs(i - k):
            return False
    return True

def n_queens(n):
    k = 1
    list=[]
    x = [0 for row in range(n + 1)]
    x[1]=0
    while k > 0:
        x[k] = x[k] + 1
        while (x[k] <= n) and (not place(x, k)):
            x[k] = x[k] + 1
        if x[k] <= n:
            if k == n:
                list.append(x[1:])
                continue
            else:
                k = k + 1
                x[k] = 0
        else:
            x[k] = 0
            k = k - 1
    return list

Totle_queens_10=[]
for i in range(1,11):
    Totle_queens_10 += n_queens(i)

print(len(Totle_queens_10))

流星蝴蝶剑

一到十皇后问题中，一共有1225组解！