python - 如果我将女王的攻击范围限制为 5 个方格，我如何检测女王是否安全？

Question

我需要在 MxM 板上放置 N 个皇后棋子，这样两个皇后就不会互相攻击。与原始问题的不同之处在于，皇后最多只能从其位置攻击 5 个方格，而不是原始问题中的整个行、列或对角线。

我脑海中的一个想法是将第一个皇后放在棋盘上的 board[i][j] 上，然后将它放在它的 5 个相邻方格中，如下图所示。

以下是原始 N-Queens 问题中的 isSafe 函数。

寻找有关如何检查女王放置是否安全的指导。

def isSafe(board, row, col): 

# Check this row on left side 
for i in range(col): 
    if board[row][i] == 1: 
        return False

# Check upper diagonal on left side 
for i,j in zip(range(row,-1,-1), range(col,-1,-1)): 
    if board[i][j] == 1: 
        return False

# Check lower diagonal on left side 
for i,j in zip(range(row,N,1), range(col,-1,-1)): 
    if board[i][j] == 1: 
        return False

return True

总之，如果我将皇后的范围限制为 5 个方格，我如何检测皇后是否安全？

标签： pythonalgorithmn-queens

Answer 1

这是解决问题的另一种方法。它基于这样一个事实，即两个皇后只有在它们共享相同的行或列或对角线时才会发生冲突，所以如果这个条件为 False，那么它对皇后来说是一个安全的地方。这是一个实现：

def share_diagonal(x0, y0, x1, y1):
    """ Check if two coordinates share diagonal or not ? """
    dx = abs(x0 - x1)
    dy = abs(y0 - y1)

    return dy == dx


def col_clashes(bs, c):
    """ Return True if the queen at column c clashes
         with any queen to its left.
    """
    for i in range(c):     # Look at all columns to the left of c
        if share_diagonal(i, bs[i], c, bs[c]):
            return True

    return False


def has_clashes(the_board):
    """ Determine whether we have any queens clashing on the diagonals.
        We're assuming here that the_board is a permutation of column
        numbers, so we're not explicitly checking row or column clashes.
    """
    for col in range(1, len(the_board)):
        if col_clashes(the_board, col):
            return True
    return False


def main():
    import random
    rng = random.Random()   # Instantiate a generator

    bd = list(range(8))     # Generate the initial permutation
    num_found = 0
    tries = 0
    result = []
    while num_found < 10:
        rng.shuffle(bd)
        tries += 1

        if not has_clashes(bd) and bd not in result:
            print("Found solution {0} in {1} tries.".format(bd, tries))
            tries = 0
            num_found += 1
            result.append(list(bd))
    print(result)


main()