理解N皇后问题，附带示例

在计算机科学的发展以来，n皇后问题是一个经典的谜题，它已经存在很长时间，但是自从计算机科学的发展以来，它受到了更多的关注。许多算法已经被开发出来，以尽可能高效地解决这个问题，它仍然是许多计算机科学家的一个吸引点。在本文的其余部分中，了解如何设置该问题以及解决该问题的常见方法。

什么是n皇后问题？

简而言之，n皇后问题是一个国际象棋问题。目标是找到将n个皇后放置在一个n×n的国际象棋棋盘上的所有可能解，以便任何两个皇后都不能互相攻击（或“冲突”）。因为皇后可以在所有可能的方向上移动，即对角线和正交方向，所以这是一个相当复杂且有趣的问题。

这个被广泛研究的问题的起源存在争议，但类似的谜题早在8世纪就有详细记录。然而，我们现在所知的这个问题在19世纪后期变得流行起来。自从70年代计算机科学的出现以来，这个问题得到了发展，许多算法都被设计出来，试图最优地解决这个问题。

如何解决n皇后问题？

多年来，已经设计出了许多解决这个问题的方法。最简单但效率最低的方法是蛮力法。这就是简单地遍历棋盘上的所有可能的配置，直到找到所有的解。毫不奇怪，这在特别大的n值时非常不实用。更受欢迎的技术有回溯法、最小冲突法、遗传算法、约束满足和对称减少。接下来我们将介绍这些方法。

回溯法

使用简单的回溯法，算法通过将第一个皇后放置在第一行和第一列，并递归地探索其他行和列来寻找有效的解决方案。如果放置了一个皇后并违反了问题的约束条件，那么算法会回溯到上一步并尝试另一个位置。这将一直继续下去，直到尝试了所有可能的配置并找到有效的解决方案。

以一个4×4的国际象棋棋盘为例，我们希望放置4个皇后。我们可以从在第一行和第一列放置一个皇后开始，这是相当常规的。如图所示，这给出了关于放置第二个皇后的约束条件。q代表一个皇后，x代表我们不能放置皇后的空间，即违反会发生的地方。

放置第一个皇后。

©jingzhengli.com

接下来，我们需要放置第二个皇后。首先，我们可以将它放置在我们可用的第一个方格中，如下所示：

放置了第二个皇后，但我们无法继续。

©jingzhengli.com

这给出了进一步的约束条件。我们可以看到无法放置第三个皇后。因此，我们必须回溯到上一步。

我们可以选择为第二个皇后选择下一个位置，但是没有办法放置其他的皇后而不引起违反。所以，我们必须再次回溯，这次回溯到第一次放置。

值得注意的是，我们还了解到没有一个解决方案会涉及到将皇后放在一个角落。尽管我们只尝试了一个角落，但由于棋盘是正方形的，所有角落都是等价的。

寻找解决方案

在第二次尝试中，让我们尝试将第一个皇后向下移动一个方格。这给了我们第二个皇后的唯一可能性，如下所示：

第一个和第二个皇后的可替代放置方式。

©jingzhengli.com

同样，我们只有一个可能的位置来放置第三个皇后。放置它会得到以下的棋盘：

在我们的第二次尝试中放置第三个皇后。

©jingzhengli.com

再次地，我们只有一个选择来放置第四个皇后，这将给我们我们最终的棋盘，如下所示。

我们已经找到了第一个解决方案。

©jingzhengli.com

幸运的是，我们成功了。我们已经放置了所有的皇后而没有违规。因此，我们可以将这视为问题的一个有效解决方案，并将其存储在解决方案列表中。

实现

该示例说明了回溯的基本思想。现在，是时候看看我们如何使用代码来实现这种方法了。考虑下面这个简单的4 x 4棋盘的python代码：

def solve_n_queens(n):
    def backtrack(row, queens):
        if row == n:
            solutions.append(queens)
        else:
            for col in range(n):
                if all(col != queens[j] and
                       col - queens[j] != row - j and
                       col - queens[j] != j - row
                       for j in range(row)):
                    backtrack(row + 1, queens + [col])

    solutions = []
    backtrack(0, [])
    return solutions


n = 4
solutions = solve_n_queens(n)
for solution in solutions:
    print(solution)

代码解释

首先，我们定义了”solve_n_queens”函数，它以”n”为输入。第二个定义的是”backtrack”函数，它以”row”和”queens”为参数。queens列表存储了放置的皇后的位置。一个dfs算法被用来探索棋盘上的空间。我们在这里还使用了一个if语句，来检查当前行是否等于行号。如果是这样，那么所有的皇后都已经放置好了，解决方案会被添加到”solutions”列表中。

否则，正如else语句所示，我们需要探索更多的解决方案。通过一个for循环来遍历每一列，检查放置的位置。如果发生冲突，则进行回溯，并在下一行放置一个皇后。

最后，代码创建一个解决方案列表，将4赋值给n，然后调用函数来解决问题。每个解决方案都会被打印出来，如图所示。结果以数组的形式给出，其中每个值表示每一行的索引，从0开始。

解决n皇后问题的回溯方法。

©jingzhengli.com

最小冲突

最小冲突法是一种局部搜索技术的例子，因为它依靠改变局部变量来改进解决方案。其基本思想是首先随机将皇后放置在各列中，然后选择具有最大冲突或违规数量的皇后。然后，将该皇后移动到最小化这些冲突的位置。重复这个过程，对每个皇后进行冲突最小化，直到找到解决方案。

实现

继续使用n = 4的示例，我们可以使用python实现最小冲突算法如下：

import random

def initialize_board(n):
    board = list(range(n))
    random.shuffle(board)
    return board

def count_conflicts(board, row, col):
    conflicts = 0
    for i in range(row):
        if board[i] == col or board[i] - col == i - row or board[i] - col == row - i:
            conflicts += 1
    return conflicts

def min_conflicts(board, n, max_iter):
    for _ in range(max_iter):
        conflicts = [count_conflicts(board, row, col) for row, col in enumerate(board)]
        if sum(conflicts) == 0:
            return board
        row = random.choice([i for i, c in enumerate(conflicts) if c > 0])
        min_conflicts = float('inf')
        min_col = -1
        for col in range(n):
            if col != board[row]:
                conflicts = count_conflicts(board, row, col)
                if conflicts < min_conflicts:
                    min_conflicts = conflicts
                    min_col = col
        board[row] = min_col
    return none

def print_solution(board):
    n = len(board)
    for i in range(n):
        row = ['.'] * n
        row[board[i]] = 'q'
        print(' '.join(row))

n = 4
max_iter = 1000

board = initialize_board(n)
solution = min_conflicts(board, n, max_iter)
if solution:
    print_solution(solution)
else:
    print("no solution found.")

代码解释

由于我们需要随机生成初始位置，因此必须导入”random”模块。然后，我们初始化棋盘，随机洗牌位置，并接收配置。

接下来，我们定义”count_conflicts()”函数，该函数接受”board”、”row”和”col”作为参数。通过迭代棋盘并检查皇后是否违反当前位置，计算出每个位置的冲突。每次发现冲突时，计数增加1。

然后，我们定义”min_conflicts()”函数来实现算法。除了配置之外，它还接受大小”n”和最大迭代次数”max_iter”作为输入。如果没有找到冲突，将配置作为解决方案返回。否则，我们随机选择一行，遍历每一列，计算冲突以找到最小值。然后，更新配置以反映此更改，并重复此过程，直到达到解决方案或执行了最大迭代次数。

最后，定义了”print()”函数，以网格格式打印结果，其中”.”表示空格，”q”表示皇后的位置。然后声明了n和max_iter，接着是初始化棋盘和打印解决方案的指令。我们可以在图像中看到达到的解决方案。

4皇后问题的最小冲突算法。

©jingzhengli.com

值得一提的是，尽管对于大棋盘尺寸来说，最小冲突法是高效的，但它可能无法找到最优解，甚至可能无法找到所有可能的解。根据搜索路径和初始放置的不同，它可能会错过一些解。这也可能是由于解对称性造成的，在n = 4的情况下是真实的。虽然我们使用回溯法获得了两个解，但使用最小冲突法只获得一个解，因为它们是对称的。

遗传算法

解决这个问题的一种相当新颖的方法是使用遗传算法，模拟自然选择的过程。我们从所有可能的配置开始，其中皇后处于不同的位置。我们根据每个配置的“适应度”评估它们，即它们的冲突数量。选择适应度较高的配置，就像进行自然选择一样。之后，通常使用两种方法：交叉和突变。在遗传学中，这些方法涉及将父母的遗传物质组合在一起或引入随机突变。对于n皇后问题，交叉是指将两个配置组合在一起，从而产生新的组合，每个皇后的放置方式都像染色体一样从一个父母那里继承。突变则是引入随机放置，这对于探索空间是有用的。

实现

通过考虑以下python中的遗传方法，我们可以更好地理解这是如何工作的。

import random

def initialize_population(population_size, n):
population = [] for _ in range(population_size):
board = list(range(n))
random.shuffle(board)
population.append(board)
return population

def count_conflicts(board):
n = len(board)
conflicts = 0
for i in range(n):
for j in range(i + 1, n):
if board[i] == board[j] or abs(board[i] – board[j]) == abs(i – j):
conflicts += 1
return conflicts

def selection(population, fitness):
selected = random.choices(population, weights=fitness, k=2)
return selected[0], selected[1]

def crossover(parent1, parent2):
n = len(parent1)
crossover_point = random.randint(1, n – 1)
child1 = parent1[:crossover_point] + parent2[crossover_point:] child2 = parent2[:crossover_point] + parent1[crossover_point:] return child1, child2

def mutation(individual):
n = len(individual)
index = random.randint(0, n – 1)
new_position = random.randint(0, n – 1)
individual[index] = new_position
return individual

def genetic_algorithm(population_size, n, max_generations):
population = initialize_population(population_size, n)

for generation in range(max_generations):
fitness = [1 / (count_conflicts(board) + 1) for board in population]

if 1 in fitness:
index = fitness.index(1)
return population[index]

new_population = [] for _ in range(population_size // 2):
parent1, parent2 = selection(population, fitness)
child1, child2 = crossover(parent1, parent2)
child1 = mutation(child1)
child2 = mutation(child2)
new_population.extend([child1, child2])

population = new_population

return none

def print_solution(board):
n = len(board)
for i in range(n):
row = [‘.'] * n
row[board[i]] = ‘q'
print(‘ ‘.join(row))

n = 4
population_size = 100
max_generations = 1000

solution = genetic_algorithm(population_size, n, max_generations)
if solution:
print_solution(solution)
else:
print(“no solution found.”)

代码解释

和之前一样，我们导入了“random”模块。然后我们定义了“initialize_population()”函数，接受“population_size”和“n”两个参数。这个函数返回可能配置的种群。

接下来，我们创建了一个列表“population”来存储这个种群，并开始一个for循环来创建这些配置，并将它们添加到列表中。然后，我们像之前一样定义了“count_conflicts()”函数，来计算冲突数量。

下一步是定义“selection()”函数，根据适应度选择父代。具有较高适应度的父代被选择的可能性更大。

在此之后，我们定义了“crossover()”函数，它接受两个父代作为输入，并执行交叉。通过从第一个父代中取出基因材料直到选择的交叉点，然后从另一个父代中取出剩余的材料来创建子代。

接下来定义了“mutation()”函数，它随机选择一个位置放置一个皇后。下一个要定义的函数是“genetic_algorithm()”函数，它计算每个配置的适应度。如果找到完美解答，则返回。

创建另一个列表“new_population”，用于存储遗传函数执行后的新人口。调用每个遗传函数，并将子代添加到新人口中。与之前类似，使用print函数将结果打印为棋盘配置。我们可以看到在图像中得到了相同的结果。

＜img_7＞

遗传方法解决四皇后问题的第一部分。

＜img_8＞

遗传方法解决四皇后问题的第二部分。

如何优化解决n皇后问题的方法？

有多种方法可以优化我们解决问题的技术。一些主要的技术包括对称约简和约束传播。我们将在下面介绍这些技术。

约束传播

这是一种旨在通过利用约束来减少可搜索空间的技术。由于我们知道不能让任何皇后彼此冲突，我们可以尽早消除潜在冲突。其中一个示例是前向检查，它通常与回溯一起使用。前向检查通过向前查看来检查放置是否允许有效的未来放置。如果不允许，该配置将尽早被删除以提高算法的效率。

实现

我们可以修改之前的示例来包含前向检查，如下所示：

def solve_n_queens(n):
    def backtrack(row, queens, domains):
        if row == n:
            solutions.append(queens)
        else:
            for col in range(n):
                if is_valid(row, col, queens, domains):
                    updated_domains = update_domains(row, col, queens, domains)
                    backtrack(row + 1, queens + [col], updated_domains)

    def is_valid(row, col, queens, domains):
        for i in range(row):
            if queens[i] == col or abs(queens[i] - col) == abs(i - row):
                return false
        return true

    def update_domains(row, col, queens, domains):
        updated_domains = domains.copy()
        for i in range(row + 1, n):
            updated_domains[i] = updated_domains[i] - {col, col - (i - row), col + (i - row)}
        return updated_domains

    solutions = []
    initial_domains = [set(range(n)) for _ in range(n)]
    backtrack(0, [], initial_domains)
    return solutions


n = 4
solutions = solve_n_queens(n)
for solution in solutions:
    print(solution)

代码解释

这里的主要区别是我们在回溯函数中包含了“domain”参数，它允许我们更新表示皇后放置的有效选项的域。使用“update_domains()”函数来删除冲突的配置。

＜img_9＞

前向检查用于优化回溯方法。

对称约简

对称约简可以用来使许多n皇后算法在解决问题时更加高效。基本原则是，通过考虑对称性，我们可以避免重复的解决方案，从而使过程更加高效。我们可以将对称行、列和对角线转化为单个表示，从而减少需要搜索的空间。

实现

我们可以通过添加以下代码将这种技术纳入我们的回溯示例中：

reduced_solutions = []
for solution in solutions:
    symmetrical_solutions = get_symmetrical_solutions(solution)
    is_unique = true
    for sym_solution in symmetrical_solutions:
        if sym_solution in reduced_solutions:
            is_unique = false
            break
    if is_unique:
        reduced_solutions.append(solution)

return reduced_solutions

def get_symmetrical_solutions(solution):
    n = len(solution)
    symmetrical_solutions = []

    symmetrical_solutions.append(tuple(solution))

    return symmetrical_solutions

代码解释

首先，我们创建一个空列表“reduced_solutions”，用于存储解决方案。for循环遍历每个解决方案，并调用“get_symmetrical_solutions()”函数返回当前解决方案的对称解决方案。然后我们检查此解决方案是否唯一，如果不是，则将其从列表中移除以减少解决方案的数量。最后，我们返回无对称的解决方案，并定义了之前描述的获取函数。我们可以看到在图片中，这次我们只收到了一个解决方案，这是正确的，因为两个可能的解决方案都是对称的。