如何简化求解八皇后八妃问题的代码？

虽然速度不算慢，但是for太多了，而且通用性不好，能否动态的生成for呢，或者改成等价的递归？ def queen8(): for x1 in xrange(1,9): for x2 in set(xrange(1,9)) - {x1-1,x1,x1+1}: for x3 in set(xrange(1,9)) - {x2-1,x2,x2+1,x1-2,x1,x1+2}: for x4 in set(xrange(1,9)) - {x3-1,x3,x3+1,x2-2,x2,x2+2,x1-3,x1,x1+3}: for x5 in set(xrange(1,9)) - {x4-1,x4,x4+1,x3-2,x3,x3+2,x2-3,x2,x2+3,x1-4,x1,x1+4}: for x6 i…
关注者
178
被浏览
32,472

18 个回答

谢邀。
前面所有回答都跑题了，我来终结此问题。
先说结论：
1. 能动态地生成for
2. 不能改成等价的递归 （我理解的等价是"速度严格变快或持平"）
下面展开说：
1. 能动态地生成for
题主所贴代码可称为“枚举剪枝算法”（后面会再提到），思路是：按行号顺序摆放皇后(Queen，下简称Q)，为第j行的Q选择列数时，根据前j-1行中摆放Q的位置进行筛选，筛选原则是：第x行(前j-1行中的某一行)已放列不选，第x行已放列向前数第j-x列不选，第x行已放列向后数第j-x列不选（之所以这个原则有效，是因为这些列是前j-1行的Q在第j行的可攻击位置，画一下图就明白了）
思路理解之后，求Q代码 和 打印求Q代码的代码 都可以写出来了。
打印求Q代码的代码（代码A）：
n = 11 
print 'def queen%d():'%n
print ' s=set(xrange(1,%d))'%(n+1)
print ' for x1 in s:'
for i in xrange(2,n+1):
    buf = ' '*(i)
    buf += 'for x%d in s - {'%i
    list = []
    for j in xrange(1,i):
        list.append(j)
    for j in list:
        buf += 'x%d+%d,'%(i-abs(j), 0)
    for j in xrange(1,i):
        list.append(-j)
    for j in list:
        buf += 'x%d+%d,'%(i-abs(j), j)
    buf = buf[:-1]
    buf += '}:'
    print buf
buf = ' '*(n+1)+'yield '
for j in xrange(1, n+1):
    buf += 'x%d,'%j
buf = buf[:-1]
print buf
print 'for i in queen%d():'%n
print ' print i'
代码A会打印出代码B (即求Q代码，即题主所贴queen11的等效代码)：
def queen11():
 s=set(xrange(1,12))
 for x1 in s:
  for x2 in s - {x1+0,x1+1,x1+-1}:
   for x3 in s - {x2+0,x1+0,x2+1,x1+2,x2+-1,x1+-2}:
    for x4 in s - {x3+0,x2+0,x1+0,x3+1,x2+2,x1+3,x3+-1,x2+-2,x1+-3}:
     for x5 in s - {x4+0,x3+0,x2+0,x1+0,x4+1,x3+2,x2+3,x1+4,x4+-1,x3+-2,x2+-3,x1+-4}:
      for x6 in s - {x5+0,x4+0,x3+0,x2+0,x1+0,x5+1,x4+2,x3+3,x2+4,x1+5,x5+-1,x4+-2,x3+-3,x2+-4,x1+-5}:
       for x7 in s - {x6+0,x5+0,x4+0,x3+0,x2+0,x1+0,x6+1,x5+2,x4+3,x3+4,x2+5,x1+6,x6+-1,x5+-2,x4+-3,x3+-4,x2+-5,x1+-6}:
        for x8 in s - {x7+0,x6+0,x5+0,x4+0,x3+0,x2+0,x1+0,x7+1,x6+2,x5+3,x4+4,x3+5,x2+6,x1+7,x7+-1,x6+-2,x5+-3,x4+-4,x3+-5,x2+-6,x1+-7}:
         for x9 in s - {x8+0,x7+0,x6+0,x5+0,x4+0,x3+0,x2+0,x1+0,x8+1,x7+2,x6+3,x5+4,x4+5,x3+6,x2+7,x1+8,x8+-1,x7+-2,x6+-3,x5+-4,x4+-5,x3+-6,x2+-7,x1+-8}:
          for x10 in s - {x9+0,x8+0,x7+0,x6+0,x5+0,x4+0,x3+0,x2+0,x1+0,x9+1,x8+2,x7+3,x6+4,x5+5,x4+6,x3+7,x2+8,x1+9,x9+-1,x8+-2,x7+-3,x6+-4,x5+-5,x4+-6,x3+-7,x2+-8,x1+-9}:
           for x11 in s - {x10+0,x9+0,x8+0,x7+0,x6+0,x5+0,x4+0,x3+0,x2+0,x1+0,x10+1,x9+2,x8+3,x7+4,x6+5,x5+6,x4+7,x3+8,x2+9,x1+10,x10+-1,x9+-2,x8+-3,x7+-4,x6+-5,x5+-6,x4+-7,x3+-8,x2+-9,x1+-10}:
            yield x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11
for i in queen11():
 print i
2. 不能改成等价的递归
考虑到问题中的代码功能是输出N皇后的所有的解
此问题的递归解法，再牛也绕不过剪枝
而剪枝，再牛也比不过“枚举剪枝算法”中的剪枝（只需调用系统的集合减操作）
用“枚举剪枝算法”中的剪枝的话，可以写成如下样子(以4皇后的递归写法为例，感兴趣的同学可尝试把打印该代码的代码写出来)，
但需要 额外递归开销+数组变量访问，远不如原算法中的 无额外开销+整型变量访问 高效。
n = 0
def queen4(x, r):
    global n
    s = set(xrange(1,n+1))
    if x == 1:
        for x1 in s:
            r[1] = x1 
            queen4(x+1, r)
    elif x == 2:
        for x2 in s-{r[1]+0,r[1]+1,r[1]-1}:
            r[2] = x2
            queen4(x+1, r)
    elif x == 3:
        for x3 in s-{r[2]+0,r[1]+0,r[2]+1,r[1]+2,r[2]-1,r[1]-2}:
            r[3] = x3
            queen4(x+1, r)
    elif x == 4:
        for x4 in s-{r[3]+0,r[2]+0,r[1]+0,r[3]+1,r[2]+2,r[1]+3,r[3]-1,r[2]-2,r[1]-3}:
            r[4] = x4
            print r
n = 4
r = [0 for i in xrange(0, n+1)]
queen4(1, r)
-
不信结论2的同学可以看下能否跑过我写的两版递归代码：
版本1 (2.842秒)：
def check(x, y, n, a):
    for i in xrange(x):
        if a[i][y]:
            return False
    i = x-1
    j = y-1
    while i>=0 and j>=0:
        if a[i][j]:
            return False
        i -= 1
        j -= 1
    i = x-1
    j = y+1
    while i>=0 and j<n:
        if a[i][j]:
            return False
        i -= 1
        j += 1
    return True
def put(x, n, a, r, c):
    if x == n:
        c[0] += 1
#        print r
        return
    for i in xrange(n):
        if check(x, i, n, a):
            a[x][i] = True
            r[x] = i
            put(x+1, n, a, r, c)
            a[x][i] = False
def queen(n):
    a = [[False for j in xrange(n)] for i in xrange(n)]
    r = [0 for i in xrange(n)]
    c = [0]
    put(0, n, a, r, c)
    print c[0]
queen(11)
版本2 (3.075秒)：
cnt = 0
def check(x, r, rx):
    for i in xrange(x):
        if rx==r[i] or abs(rx-r[i])==x-i:
            return False
    return True
def put(x, n, r, c):
    if x == n:
#        print r
        c[0] += 1
        return
    for i in xrange(n):
        r[x] = i
        if check(x, r, i):
            put(x+1, n, r, c)
def queen(n):
    r = [0 for i in xrange(n)]
    c = [0]
    put(0, n, r, c)
    print c[0]
queen(11)
这两版的代码都验证过无法超过“枚举剪枝算法”了：
枚举剪枝算法 (0.394秒)：
def queen11(c):
 s=set(xrange(1,12))
 for x1 in s:
  for x2 in s - {x1+0,x1+1,x1+-1}:
   for x3 in s - {x2+0,x1+0,x2+1,x1+2,x2+-1,x1+-2}:
    for x4 in s - {x3+0,x2+0,x1+0,x3+1,x2+2,x1+3,x3+-1,x2+-2,x1+-3}:
     for x5 in s - {x4+0,x3+0,x2+0,x1+0,x4+1,x3+2,x2+3,x1+4,x4+-1,x3+-2,x2+-3,x1+-4}:
      for x6 in s - {x5+0,x4+0,x3+0,x2+0,x1+0,x5+1,x4+2,x3+3,x2+4,x1+5,x5+-1,x4+-2,x3+-3,x2+-4,x1+-5}:
       for x7 in s - {x6+0,x5+0,x4+0,x3+0,x2+0,x1+0,x6+1,x5+2,x4+3,x3+4,x2+5,x1+6,x6+-1,x5+-2,x4+-3,x3+-4,x2+-5,x1+-6}:
        for x8 in s - {x7+0,x6+0,x5+0,x4+0,x3+0,x2+0,x1+0,x7+1,x6+2,x5+3,x4+4,x3+5,x2+6,x1+7,x7+-1,x6+-2,x5+-3,x4+-4,x3+-5,x2+-6,x1+-7}:
         for x9 in s - {x8+0,x7+0,x6+0,x5+0,x4+0,x3+0,x2+0,x1+0,x8+1,x7+2,x6+3,x5+4,x4+5,x3+6,x2+7,x1+8,x8+-1,x7+-2,x6+-3,x5+-4,x4+-5,x3+-6,x2+-7,x1+-8}:
          for x10 in s - {x9+0,x8+0,x7+0,x6+0,x5+0,x4+0,x3+0,x2+0,x1+0,x9+1,x8+2,x7+3,x6+4,x5+5,x4+6,x3+7,x2+8,x1+9,x9+-1,x8+-2,x7+-3,x6+-4,x5+-5,x4+-6,x3+-7,x2+-8,x1+-9}:
           for x11 in s - {x10+0,x9+0,x8+0,x7+0,x6+0,x5+0,x4+0,x3+0,x2+0,x1+0,x10+1,x9+2,x8+3,x7+4,x6+5,x5+6,x4+7,x3+8,x2+9,x1+10,x10+-1,x9+-2,x8+-3,x7+-4,x6+-5,x5+-6,x4+-7,x3+-8,x2+-9,x1+-10}:
#            yield x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11
            c[0] += 1
c = [0]
queen11(c)
print c[0]
哪里有那么麻烦呀？八皇后明明只需要 5行代码就搞定了，递归版，统计所有解的数量：
f = lambda A, x, y: y < 0 or (not (A[y] in (A[x], A[x] + (x - y), A[x] - (x - y))))
g = lambda A, x, y: (not x) or (f(A, x, y) and ((y < 0) or g(A, x, y - 1)))
h = lambda A, x: sum([ g(A, x, x - 1) and 1 or 0 for A[x] in range(len(A)) ])
q = lambda A, x: h(A, x) if (x is 7) else sum([ q(A, x + 1) for A[x] in range(8) if g(A, x, x - 1) ])

print q([ 0 for i in xrange(8) ], 0)