python - Python 中的八皇后问题

Question

Python 中的 8 皇后问题。

嗨!我才开始教 Python，所以有人可以解释下面编写的代码(在 Internet 上找到的)吗？有些代码对我来说很复杂。请解释一下。谢谢。问题就在代码附近。

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

您的代码有误(剪切和粘贴错误？)，但要点如下:

您需要一份可能的解决方案列表。每个解决方案都是皇后列表。每个皇后都是一个元组——一行(整数)和一列(整数)。例如，BOARD_SIZE=1 的解决方案是 [[(1,1)]] - 单个解决方案 - [(1,1)] 包含一个皇后 - (1,1) 放在第 1 行和第 1 列。

对于 BOARD_SIZE=8 和 n=1 有 8 个 smaller_solutions - [[(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(因为它知道现有皇后的行位置将不断倒计时)，跟踪左右对角线。