Python中的八皇后问题

Question

8皇后问题在Python中的实现。

你好！我刚开始学习Python，所以能不能有人帮我解释一下下面这段代码（在网上找到的）？代码中的某些部分对我来说有点复杂。请帮我解释一下。谢谢！问题就在代码旁边。

BOARD_SIZE = 8

def under_attack(col, queens): # (col, queens) What is their meaning? What do I need to write it this field? 
    left = right = col
    for r, c in reversed(queens): # What does reversed means in this loop? For what reson do we need r and c (their meaning is 0 by default?)?
        left, right = left-1, right+1
        if c in (left, col, right):
            return True
    return False

def solve(n):
    if n == 0: return [[]]
    smaller_solutions = solve(n-1) # For what reasons do we need to write smaller_solutions?
    return [solution+[(n,i+1)] # What is solution (is it a function or what?)? What is value of i? 
        for i in range(BOARD_SIZE)
            for solution in smaller_solutions
                if not under_attack(i+1, solution)]
for answer in solve(BOARD_SIZE): print answer

谢谢你！

Answer 1

这是一个源程序，运行这个代码后，输出结果会被生成到一个名为“queen.txt”的单独文件中。

import json
import sys

BOARD_SIZE = 8

def under_attack(col, queens):
    x = y = col

    for r, c in reversed(queens):
        x , y = x - 1, y + 1 #check for the prev queen location 

        if c in (x , col, y):
            return True
    return False

def solve(n): # n is the number of queens to be placed
    if n == 0:
        return [[]]

    smaller_solutions = solve(n - 1)

    return [solution+[(n,i+1)]
        for i in xrange(BOARD_SIZE)
            for solution in smaller_solutions
                if not under_attack(i+1, solution)] #call the function 

former, sys.stdout = sys.stdout, open('queen.txt','w')

for answer in solve(BOARD_SIZE):
    print answer

results, sys.stdout = sys.stdout, former #former is used for ip & op
print json.dumps(answer) #dumps is used to write in json file

输出文件的内容会像这样：[(1, 4), (2, 2), (3, 7), (4, 3), (5, 6), (6, 8), (7, 5), (8, 1)] [(1, 5), (2, 2), (3, 4), (4, 7), (5, 3), (6, 8), (7, 6), (8, 1)] [(1, 3), (2, 5), (3, 2), (4, 8), (5, 6), (6, 4), (7, 7), (8, 1)] . . . . [(1, 4), (2, 7), (3, 5), (4, 2), (5, 6), (6, 1), (7, 3), (8, 8)] [(1, 5), (2, 7), (3, 2), (4, 6), (5, 3), (6, 1), (7, 4), (8, 8)]

Answer 2

BOARD_SIZE = 8

def under_attack(col, queens): # You do not need to fill in these fields. This is a helper function for the solve function.
    left = right = col
    for r, c in reversed(queens): # Reversing queens causes them to be iterated over in reverse order.
        left, right = left-1, right+1
        if c in (left, col, right):
            return True
    return False

def solve(n):
    if n == 0: return [[]]
    smaller_solutions = solve(n-1) # It appears that in solving this board, it solves all boards smaller than it in a recursive manner.
    return [solution+[(n,i+1)] # This line appears to be in error. Have you run this code and verified that it runs correctly?
        for i in range(BOARD_SIZE)
            for solution in smaller_solutions
                if not under_attack(i+1, solution)]
for answer in solve(BOARD_SIZE): print answer

当然可以！请把你想要翻译的内容发给我，我会帮你用简单易懂的语言解释清楚。

Answer 3

你的代码有问题（可能是复制粘贴错误？），不过我来给你讲讲大概意思：

你需要一个可能的解决方案列表。每个解决方案都是一个皇后的位置列表。每个皇后用一个元组表示，包含行（整数）和列（整数）。比如说，当BOARD_SIZE=1时，解决方案是[[(1,1)]]，这表示只有一个解决方案[(1,1)]，里面有一个皇后(1,1)，它放在第一行第一列。

当BOARD_SIZE=8时，有8个smaller_solutions，而且n=1 - [[(1,1)],[(1,2)],[(1,3)],[(1,4)],[(1,5)],[(1,6)],[(1,7)],[(1,8)]] - 这表示在第一行的每一列都放了一个皇后。

你了解递归吗？如果不懂，赶紧去网上查一下。

简单来说，你从一个0皇后的0大小棋盘开始，这个棋盘有一个简单的解决方案，就是没有皇后。然后你找出在棋盘第一行放一个皇后的解决方案。接着你再找出在第二行放第二个皇后的解决方案，前提是这个位置不被攻击。然后依此类推。

def solve(n):
    if n == 0: return [[]] # No RECURSION if n=0. 
    smaller_solutions = solve(n-1) # RECURSION!!!!!!!!!!!!!!
    solutions = []
    for solution in smaller_solutions:# I moved this around, so it makes more sense
        for column in range(1,BOARD_SIZE+1): # I changed this, so it makes more sense
            # try adding a new queen to row = n, column = column 
            if not under_attack(column , solution): 
                solutions.append(solution + [(n,column)])
    return solutions

这解释了大致的策略，但没有讲到under_attack。

under_attack可以重新写一下，让它更容易理解（对我、你和你的学生来说）：

def under_attack(column, existing_queens):
    # ASSUMES that row = len(existing_queens) + 1
    row = len(existing_queens)+1
    for queen in existing_queens:
        r,c = queen
        if r == row: return True # Check row
        if c == column: return True # Check column
        if (column-c) == (row-r): return True # Check left diagonal
        if (column-c) == -(row-r): return True # Check right diagonal
    return False

我的方法稍微慢一点，但也没慢太多。

旧的under_attack基本上是一样的，不过它稍微加快了速度。它会反向查看existing_queens（因为它知道现有皇后的行位置会逐渐减少），同时跟踪左对角线和右对角线。