Python中的N皇后

Question

我偶尔使用Python，今天我解决了Python中的n个皇后只是为了好玩。我确信在Python中有更好的方法来完成某些事情，并且不能等待改进的建议！

#!/usr/bin/python3


def print_board(board):
    for row in board:
        for field in row:
            print('Q ', end='') if field else print('X ', end='')
        print()
    print()


def can_place_queen(board, row, col):
    for field in board[row]:
        if field: return False
    for i in range(len(board[0])):
        if board[i][col]: return False
    i, j = row, col
    l = len(board)
    while i < l and j < l:
        if board[i][j]: return False
        i, j = i + 1, j + 1
    i, j = row, col
    while i < l and j >= 0:
        if board[i][j]: return False
        i, j = i + 1, j - 1
    i, j = row, col
    while i >= 0 and j < l:
        if board[i][j]: return False
        i, j = i - 1, j + 1
    i, j = row, col
    while i >= 0 and j >= 0:
        if board[i][j]: return False
        i, j = i - 1, j - 1
    return True

def place_queens(board, row=0):
    global nSolutions
    if row >= len(board):
        print_board(board)
        nSolutions += 1
        return
    for col, field in enumerate(board):
        if can_place_queen(board, row, col):
            board[row][col] = True
            place_queens(board, row + 1)
            board[row][col] = False


nSolutions = 0
# Note that [[False]*8]*8 does not work since * will just copy the address
# of the row!
board = [[False] * 8 for i in range(8)]
place_queens(board)
print("Found %s solutions!" % nSolutions)

Answer 1

一个可能有助于加快速度的选择是在您的董事会中包含一些冗余的元数据。不只是表示一个8*8的布尔数组，它代表的是一个女王是否在一个给定的单元格上发挥作用，您还可以使用8个布尔数组来指示女王是否在给定的行、列或对角线上的任何位置发挥作用。这将使实际演奏这首曲子稍微复杂一些，但要检查一次搬迁是否合法要容易得多。

特别是如果您希望有一个更复杂的董事会状态表示，那么将其封装到一个类中可能是值得的。

第二个值得思考的领域是利用对称性。如果您找到了一个解决方案，则该布局垂直反射、水平反射或以这种方式旋转，或者也将是有效的解决方案。要确认这是一个独特的解决方案需要一点谨慎，但避免甚至检查董事会的大多数职位，因为你已经检查过反思或轮转，这是一个巨大的胜利。

Python提供的许多优雅的技巧之一是列表理解，用于一次操作整个列表。例如，要将布尔人的list row转换为"Q“和"X”的列表，您可以使用它。

["Q" if i else "X" for i in row]

这意味着可以编写print_board中的内环。

print("".join(["Q" if i else "X" for i in row]))

避免显式循环的另一个方便的技巧是any和all缩减函数。它们获取布尔值的集合(或可以转换为布尔值的内容)，并返回True (如果有或全部为True )。

例如，(忽略我的第一个建议) can_place_queen中的第一个检查可以从

for field in board[row]:
    if field: return False

至

if any(board[row]): return False

然而，将其他检查写得非常简洁，也不起作用。

最后，编写独立运行的脚本的传统方法是

def main():
    nSolutions = 0
    # Note that [[False]*8]*8 does not work since * will just copy the address
    # of the row!
    board = [[False] * 8 for i in range(8)]
    place_queens(board)
    print("Found %s solutions!" % nSolutions)

if __name__ == "__main__": main()

这样做的主要目的是，如果有人将python文件作为模块导入，他们就不会获得运行脚本的结果。

Answer 2

我建议要么注释每个检查循环，解释它们正在做的检查(“检查对角到右下角的皇后”)，要么将每个子检查放在自己的函数中。

您也有可能在一个循环中同时完成右下角和左上角的大步，甚至可以将所有搜索抽象为一个跨步的函数，因为那里有大量的代码重复：

def diagonal_search(row, col, board, x_stride, y_stride):
   i, j = row, col
   l = len(board)
   while i < l and i >= 0 and j < l and j >= 0:
      if board[i][j]: return False
      i, j = i + x_stride, j + y_stride
   return True

并将其用作：

# Search the row
if not diagonal_search(row, col, board, 1, 0):
   return False
# Search the column
if not diagonal_search(row, col, board, 0, 1):
   return False
# Search the right-down diagonal
if not diagonal_search(row, col, board, 1, 1):
   return False

等等。