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

jerryxjr1220 · 发表于 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

小火木 · 发表于 2017-8-14 14:45:04

本帖最后由小火木于 2017-8-14 19:44 编辑

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 · 发表于 2017-8-14 15:17:38

本帖最后由 Cathaysian 于 2017-8-14 15:21 编辑

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

复制代码

第一次回帖有点小激动

小锟 · 发表于 2017-8-14 19:23:39

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))

复制代码

撒法空间 · 发表于 2017-8-15 13:12:07

#!/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 · 发表于 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)

qwc3000 · 发表于 2017-8-15 22:58:16

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

小剑剑 · 发表于 2017-8-16 10:18:01

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 · 发表于 2017-8-16 14:08:27

不会下象棋

michaelol · 发表于 2017-8-16 15:23:05

哇，人比较笨，写了好久。主要难点在斜线检测和递归调用。答案：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 · 发表于 2017-8-16 17:27:05

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

小風 · 发表于 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

小Q学Python · 发表于 2017-8-16 18:35:16

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

影乖 · 发表于 2017-8-16 20:16:02

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

bozhen · 发表于 2017-8-16 21:53:38

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 · 发表于 2017-8-16 22:54:01

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 · 发表于 2017-8-17 11:18:06

本帖最后由 gunjang 于 2017-8-17 11:19 编辑

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

'''
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 · 发表于 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))

流星蝴蝶剑 · 发表于 2017-8-17 16:48:34

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

账号		自动登录	找回密码
密码			立即注册

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

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

评分

本帖被以下淘专辑推荐:

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

点评