鱼C论坛

 找回密码
 立即注册
查看: 4433|回复: 19

[技术交流] 鱼C论坛Python精英挑战赛(第二季03期)

[复制链接]
发表于 2017-8-14 09:42:49 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 jerryxjr1220 于 2017-8-18 00:06 编辑

鱼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

评分

参与人数 1荣誉 +5 鱼币 +5 贡献 +5 收起 理由
冬雪雪冬 + 5 + 5 + 5 支持楼主!

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-8-14 14:45:04 | 显示全部楼层
本帖最后由 小火木 于 2017-8-14 19:44 编辑
  1. from itertools import permutations

  2. def slash(matrix):
  3.     X=set()
  4.     Y=set()
  5.     for line in matrix:
  6.         x=line +matrix.index(line)
  7.         y=line - matrix.index(line)-1
  8.         if x in X or y in Y:
  9.             return False
  10.         else:           
  11.             X.add(x)
  12.             Y.add(y)

  13.     return True



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

  21.   
复制代码

评分

参与人数 1贡献 +1 收起 理由
jerryxjr1220 + 1 答题奖励,Time=13.21s

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-14 15:17:38 | 显示全部楼层
本帖最后由 Cathaysian 于 2017-8-14 15:21 编辑
  1. from itertools import *
  2. #现在才发现看错题目了,以为八皇后呢
复制代码



第一次回帖有点小激动
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-14 19:23:39 | 显示全部楼层



  1. def confict(list1 , weizhi , n):
  2.     '''判断是否冲突'''
  3.     row_num = weizhi[0]
  4.     column_num = weizhi[1]
  5.     #判断行
  6.     for column in list1[row_num] :
  7.         if column :
  8.             return True
  9.     #判断列
  10.     for row in list1 :
  11.         if row[column_num] :
  12.             return True
  13.     #判断左斜线
  14.     while row_num >= 0 and column_num >= 0 :
  15.         if list1[row_num][column_num]:
  16.             return True
  17.         row_num -= 1
  18.         column_num -= 1
  19.     #判断右斜线
  20.     while weizhi[0] >= 0 and weizhi[1] < n :
  21.         if list1[weizhi[0]][weizhi[1]]:
  22.             return True
  23.         weizhi[0] -= 1
  24.         weizhi[1] += 1

  25.     return False


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

  33.    

  34. sumresult = 0
  35. for n in range(1,11):
  36.     #生成 n * n 的列表
  37.     list1 = [[0 for i in range(n)] for j in range(n)]
  38.     i , result = 0 , 0
  39.     jilu = []
  40.     try :
  41.         while len(jilu) >= 0:
  42.             count = 0
  43.             j = 0
  44.             while j <= n - 1:
  45.                 if not confict(list1 , [i,j] ,n):
  46.                     list1[i][j] = 1
  47.                     jilu.append([i,j])
  48.                     #如果到了最后一行
  49.                     if i == n-1:
  50.                         result += 1
  51.                         list1[i][j] = 0
  52.                         jilu.pop()
  53.                         list1 , jilu ,i, j = huisu(list1 , jilu)
  54.                         # 如果回溯的结果已经在最后一列,需要继续回溯
  55.                         if j == n-1:
  56.                             list1 , jilu ,i, j = huisu(list1 , jilu)
  57.                         j += 1
  58.                         count = j
  59.                         continue
  60.                     else:
  61.                         i += 1
  62.                         break
  63.                 else:
  64.                     count += 1
  65.                     #如果这一行都不可以放皇后
  66.                     if count == n :
  67.                         list1 , jilu ,i, j = huisu(list1 , jilu)
  68.                         # 如果回溯的结果已经在最后一列,需要继续回溯
  69.                         if j == n-1:
  70.                             list1 , jilu ,i, j = huisu(list1 , jilu)
  71.                         j += 1
  72.                         count = j
  73.                         continue
  74.                 j += 1

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

评分

参与人数 1贡献 +1 收起 理由
jerryxjr1220 + 1 答题奖励,Time=0.774s

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-15 13:12:07 | 显示全部楼层
  1. #!/usr/bin/env python3
  2. #coding:utf-8


  3. def conflict(state, col):
  4.     row = len(state)
  5.     for i in range(row):
  6.         if abs(state[i] - col) in (0, row - i):
  7.             return True
  8.     return False


  9. def queens(num=8, state=()):
  10.     for pos in range(num):
  11.         if not conflict(state, pos):
  12.             if len(state) == num - 1:
  13.                 yield (pos,)
  14.             else:
  15.                 for result in queens(num, state + (pos,)):
  16.                     yield (pos,) + result

  17. total = 0
  18. for x in range(1,11):
  19.     total += len(list(queens(x)))
  20. print('一皇后至10皇后总共有' + str(total)+'组解')
复制代码


所有一到十皇后问题中,一共有1225组解!

评分

参与人数 1荣誉 +1 鱼币 +1 贡献 +1 收起 理由
jerryxjr1220 + 1 + 1 + 1 答题奖励,Time=0.927s

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-15 22:57:28 | 显示全部楼层
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)

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
jerryxjr1220 + 1 + 1 答题奖励

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-15 22:58:16 | 显示全部楼层
我只是参与下   我的运行感觉好慢啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-16 10:18:01 | 显示全部楼层
  1. def n_queens(queen):
  2.     save=[]
  3.     col=0
  4.     row=[i for i in range(queen)]
  5.     queens=[]
  6.     save.append((queens,col,row))
  7.     result=0
  8.     while save:
  9.         temp=save.pop()
  10.         col=temp[1]
  11.         if  col ==queen:
  12.             result+=1
  13.             continue
  14.         row=temp[2]
  15.         queens=temp[0]
  16.         i=col
  17.         for j in row:
  18.             judge=True
  19.             for q in queens:
  20.                 c=abs(q[0]-i)
  21.                 r=abs(q[1]-j)
  22.                 if c==r:
  23.                     judge=False
  24.                     break
  25.             if judge:
  26.                 t1 = queens[:]
  27.                 t1.append((i, j))
  28.                 t2 = col+1
  29.                 t3 = row[:]
  30.                 t3.remove(j)
  31.                 save.append((t1, t2, t3))
  32.     return result

  33. print(sum(map(n_queens,[i for i in range(1,11)])))
复制代码


1225

评分

参与人数 1荣誉 +1 鱼币 +1 贡献 +1 收起 理由
jerryxjr1220 + 1 + 1 + 1 答题奖励,Time=0.296s

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-16 14:08:27 | 显示全部楼层
不会下象棋
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-16 15:23:05 | 显示全部楼层
哇,人比较笨 ,写了好久。主要难点在斜线检测和递归调用。答案:1225个  代码如下 result[]中存放了所有结果:
  1. import copy

  2. #直线的检查方法:
  3. def row_check(coor,i,j,n):      #行检测
  4.     for each in range(n):
  5.         if coor[i][each]==1:
  6.             return 0
  7.     else:
  8.         return 1

  9. def column_check(coor,i,j,n):  #列检测
  10.     for each in range(n):
  11.         if coor[each][j]==1:
  12.                 return 0
  13.     else:
  14.         return 1
  15. def slash_check(coor,i,j,n):  #斜线检测
  16.     if i>j:
  17.         for delta in range(n-i+j):
  18.             if coor[i-j+delta][delta]==1:
  19.                 return 0
  20.     elif i==j:
  21.         
  22.         for delta in range(n):
  23.             if coor[delta][delta]==1:
  24.                 return 0
  25.         if 2*i-n+1>=0:
  26.             for delta in range(2*n-2*i-1):
  27.                 if coor[n-delta-1][2*i-n+1+delta]==1:
  28.                     return 0
  29.         else:
  30.             for delta in range(2*i+1):
  31.                 if coor[2*i-delta][delta]==1:
  32.                     return 0
  33.     else:
  34.         for delta in range(n-j+i):
  35.             if coor[delta][j-i+delta]==1:
  36.                 return 0
  37.     if i+j>=n-1:
  38.         
  39.         for delta in range(2*n-i-j-2+1):
  40.             if coor[n-1-delta][i+j+1-n+delta]==1:
  41.                 return 0
  42.     else:
  43.         
  44.         for delta in range(i+j+1):
  45.             if coor[i+j-delta][delta]==1:
  46.                 return 0

  47.     return 1
  48. def check(coor,i,j,n):    #检测是否可以放置皇后  可以返回1 否则返回0
  49.     a=row_check(coor,i,j,n)
  50.     b=column_check(coor,i,j,n)
  51.     c=slash_check(coor,i,j,n)
  52.     if a and b and c:
  53.         return 1
  54.     else:
  55.         return 0


  56. def backtracking(coor,i,n):
  57.     if i==n-1:
  58.       
  59.         for j in range(n):
  60.             if check(coor,i,j,n):
  61.                 coor[i][j]=1
  62.                 global result
  63.                 result.append(copy.deepcopy(coor))
  64.                 coor[i][j]=0              
  65.                 return result
  66.             
  67.     for j in range(n):
  68.       
  69.         if check(coor,i,j,n):
  70.             coor[i][j]=1
  71.             i+=1
  72.             backtracking(coor,i,n)
  73.             i-=1
  74.             coor[i][j]=0
  75.     return result

  76. def queen(n):

  77.     checkerboard=[[0 for i in range(n)]for i in range(n)]
  78.     return backtracking(checkerboard,0,n)
  79.    


  80. result=[]
  81. for n in range(1,11):   
  82.     queen(n)
  83. print(len(result))
复制代码

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
jerryxjr1220 + 1 + 1 答题奖励,Time=2.42s

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-16 17:27:05 | 显示全部楼层
  1. import time
  2. def canput(x, y): #[0..n)
  3.         if (x >= n) or (y >= n):
  4.                 return False
  5.         #column
  6.         for i in range(y):
  7.                 if queen[i] == x:
  8.                         return False
  9.         #Left Top 45 degree
  10.         for i in range(x):
  11.                 if queen[y-i-1]-(y-i-1) == x - y:
  12.                         return False
  13.         #Right Top 135 degree
  14.         for i in range(n-1-x):
  15.                 if (x+y) == (queen[y-i-1]+(y-i-1)):
  16.                         return False
  17.         return True

  18. st = time.time()
  19. count = 1
  20. maxn = 10
  21. for n in range(2, maxn+1):
  22.         queen = [-1 for i in range(n)]
  23.         y = 0
  24.         halfcnt = 0
  25.         while True:
  26.                 x = queen[y]+1
  27.                 while not canput(x, y):
  28.                         x += 1
  29.                         if x >= n:
  30.                                 break
  31.                 if (y==0) and (x >= (n+1)//2): #symmetrical
  32.                         #print(n, halfcnt, midcnt)
  33.                         break
  34.                 if canput(x, y):
  35.                         #put queen
  36.                         queen[y] = x
  37.                         if y == n-1:
  38.                                 #print(queen) #
  39.                                 if (n%2==1) and (queen[0] == n//2) and (queen[1] > n//2): #symmetrical
  40.                                         break
  41.                                 else:
  42.                                         halfcnt += 1
  43.                                 queen[y] = -1 #reset
  44.                                 y -= 1
  45.                                 continue
  46.                                 #break #return one solve
  47.                         else:
  48.                                 y += 1
  49.                 else:
  50.                         queen[y] = -1 #reset
  51.                         y -= 1
  52.                         if y == -1:
  53.                                 break

  54.         count += 2*halfcnt

  55. cost = time.time()-st
  56. print(count) #1225
  57. print(cost) #1.84375 => 1.71875 => 0.828125
复制代码

答案:1225

评分

参与人数 1荣誉 +1 鱼币 +1 贡献 +1 收起 理由
jerryxjr1220 + 1 + 1 + 1 答题奖励,Time=0.459s

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-16 18:13:47 | 显示全部楼层
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

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
jerryxjr1220 + 1 + 1 答题奖励

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-16 18:35:16 | 显示全部楼层
  1. def nQ(m):
  2.     a = [None]*m
  3.     def nQueen(n):
  4.         global counts
  5.         if n == m:
  6.             counts+=1
  7.         for i in set(range(m))-set(a[:n]):
  8.             if n!=0 and abs(i-a[n-1])==1:
  9.                 continue
  10.             flag = 0
  11.             for x,y in enumerate(a[:n]):
  12.                 if n-i == x-y or n+i == x+y :
  13.                     flag = 1
  14.                     break
  15.             if flag==0:
  16.                 a[n]=i
  17.                 nQueen(n+1)
  18.    
  19.     nQueen(0)

  20. counts = 0
  21. for i in range(1,11):
  22.     nQ(i)
  23. print(counts)
复制代码


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

评分

参与人数 1荣誉 +1 鱼币 +1 贡献 +1 收起 理由
jerryxjr1220 + 1 + 1 + 1 答题奖励,Time=0.293s

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-16 20:16:02 | 显示全部楼层
我不会,我只是来顶贴的……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-16 21:53:38 | 显示全部楼层
  1. from itertools import permutations

  2. def getcount(x):
  3.     count = 0
  4.     for vec in permutations(range(x)):
  5.         if (x == len(set(vec[i]+i for i in range(x)))== len(set(vec[i]-i for i in range(x)))):
  6.             count += 1
  7.     return count

  8. counts = 0
  9. for i in range(1,11):
  10.     counts += getcount(i)

  11. print(counts)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-16 22:54:01 | 显示全部楼层
  1. import time

  2. st = time.time()
  3. count = 1
  4. maxn = 10
  5. for n in range(2, maxn+1):
  6.         queen = [-1 for i in range(n)]
  7.         column = [False for i in range(n)]
  8.         LB45 = [False for i in range(2*n-2+1)] # leftbottom, sum of x and y
  9.         RB135 = [False for i in range(2*n-2+1)] # x-y in [1-n..n-1] ,so index=x-y+n-1
  10.         y = 0
  11.         halfcnt = 0
  12.         while True:
  13.                 x = queen[y]+1
  14.                 #while (x < n) and not canput(x, y):
  15.                 while  (x < n) and (column[x] or LB45[x+y] or RB135[x-y+n-1]):
  16.                         x += 1

  17.                 if (y==0) and (x >= (n+1)//2): #symmetrical
  18.                         break
  19.                 if x < n:#if canput(x, y):
  20.                         #put queen
  21.                         queen[y] = x
  22.                        
  23.                         if y == n-1:
  24.                                 #print(queen) #symmetrical is [n-x for x in queen]
  25.                                 if (n%2==1) and (queen[0] == n//2) and (queen[1] > n//2): #symmetrical
  26.                                         break
  27.                                 else:
  28.                                         halfcnt += 1
  29.                                 queen[y] = -1 #reset
  30.                                 y -= 1
  31.                                 column[queen[y]] = False
  32.                                 LB45[queen[y]+y] = False
  33.                                 RB135[queen[y]-y+n-1] = False
  34.                                 continue        # or break #return one solve
  35.                         else:
  36.                                 column[x] = True
  37.                                 LB45[x+y] = True
  38.                                 RB135[x-y+n-1] = True
  39.                                 y += 1
  40.                 else:
  41.                         queen[y] = -1 #reset
  42.                         y -= 1
  43.                         if y == -1:
  44.                                 break
  45.                         column[queen[y]] = False
  46.                         LB45[queen[y]+y] = False
  47.                         RB135[queen[y]-y+n-1] = False

  48.         count += 2*halfcnt

  49. cost = time.time()-st
  50. print(count) #1225
  51. print(cost) #1.84375 => 1.71875 => 0.828125 => 0.28124403953552246
复制代码

答案1225,v2版速度更快

评分

参与人数 1贡献 +1 收起 理由
jerryxjr1220 + 1 Time=0.107s, 写一下注释呗,方便大家理解.

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-17 11:18:06 | 显示全部楼层
本帖最后由 gunjang 于 2017-8-17 11:19 编辑

应版主要求,加了注释版,当然小细节调整
  1. '''
  2. http://bbs.fishc.com/thread-94433-1-1.html
  3. '''
  4. import time

  5. st = time.time()
  6. count = 1
  7. maxn = 10
  8. for n in range(2, maxn+1):
  9.         queen = [-1 for i in range(n)]
  10.         column = [False for i in range(n)]
  11.         LB45 = [False for i in range(2*n-2+1)] # leftbottom, sum of x and y
  12.         RB135 = [False for i in range(2*n-2+1)] # x-y in [1-n..n-1] ,so index=x-y+n-1
  13.         y = 0
  14.         halfcnt = 0
  15.         while True:
  16.                 x = queen[y]+1
  17.                 #while (x < n) and not canput(x, y):
  18.                 while  (x < n) and (column[x] or LB45[x+y] or RB135[x-y+n-1]):
  19.                         x += 1

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

  24.                 if x < n:#if canput(x, y):
  25.                         #put queen
  26.                         queen[y] = x
  27.                        
  28.                         if y == n-1:
  29.                                 #print(queen)
  30.                                 #symmetrical is [n-x for x in queen]
  31.                                 halfcnt += 1
  32.                                 queen[y] = -1 #reset
  33.                                 y -= 1
  34.                                 column[queen[y]] = False
  35.                                 LB45[queen[y]+y] = False
  36.                                 RB135[queen[y]-y+n-1] = False
  37.                                 continue        # or break #return one solve
  38.                         else:
  39.                                 column[x] = True
  40.                                 LB45[x+y] = True
  41.                                 RB135[x-y+n-1] = True
  42.                                 y += 1
  43.                 else:
  44.                         queen[y] = -1 #reset
  45.                         y -= 1
  46.                         if y == -1: #all solve
  47.                                 break
  48.                         column[queen[y]] = False
  49.                         LB45[queen[y]+y] = False
  50.                         RB135[queen[y]-y+n-1] = False

  51.         count += 2*halfcnt

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

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

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

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

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

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

答案1225
算是v2.1吧

评分

参与人数 2荣誉 +3 鱼币 +3 贡献 +1 收起 理由
小剑剑 + 2 + 2 原来还有对称性
jerryxjr1220 + 1 + 1 + 1 解释很到位,加分!对称性我都没考虑到!

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-17 12:58:35 | 显示全部楼层
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))

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
jerryxjr1220 + 1 + 1 答题奖励,Time=0.844s

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-17 16:48:34 | 显示全部楼层
一到十皇后问题中,一共有1225组解!

点评

我很赞同!: 1.0
我很赞同!: 1
参与答题的话要附上源代码哟!  发表于 2017-8-17 18:33
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 21:39

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表