N-Queen的递归实现

Question

N-皇后问题是计算机科学分支在学习递归章节时首先教授的问题之一。这个问题在数学和计算机科学中得到了很好的研究。

我以深度优先搜索的方式编码了这个问题，并希望得到一个位置列表，我可以在 N × N 棋盘上放置 N 个皇后

import copy

# At some point, I thought recursion limit was the problem, but I don't think so.
# import sys
# sys.setrecursionlimit(1_000_000_000)
board_shape = 9
queen_moves = list()


def check_collision(var_current, var_others):
    if len(var_others) > 0:
        for queens in var_others:
            if var_current[0] == queens[0]:
                return True
            elif var_current[1] == queens[1]:
                return True
            elif abs(var_current[0] - queens[0]) == abs(var_current[1] -
                queens[1]) :
                return True

    return False


def n_queen(pos_X, pos_Y, queens_t, total_queens):
    if pos_X > -1 and pos_X < board_shape:
        if pos_Y > -1 and pos_Y < board_shape and queens_t < board_shape:

            current_queen = [pos_X, pos_Y, queens_t + 1]
            copy_of_moves = copy.deepcopy(total_queens)

            if check_collision(current_queen, copy_of_moves) is False:
                copy_of_moves.append(current_queen)
                print(copy_of_moves, "\t", len(copy_of_moves))
            else:
                return

            if len(copy_of_moves) == board_shape :
                print("There is a route")
                print(copy_of_moves)
                return

            n_queen(pos_X=pos_X + 2, pos_Y=pos_Y + 1, queens_t=queens_t+1, total_queens=copy_of_moves)
            n_queen(pos_X=pos_X + 2, pos_Y=pos_Y - 1, queens_t=queens_t+1, total_queens=copy_of_moves)
            n_queen(pos_X=pos_X - 2, pos_Y=pos_Y + 1, queens_t=queens_t+1, total_queens=copy_of_moves)
            n_queen(pos_X=pos_X - 2, pos_Y=pos_Y - 1, queens_t=queens_t+1, total_queens=copy_of_moves)

            n_queen(pos_X=pos_X + 1, pos_Y=pos_Y + 2, queens_t=queens_t+1, total_queens=copy_of_moves)
            n_queen(pos_X=pos_X + 1, pos_Y=pos_Y - 2, queens_t=queens_t+1, total_queens=copy_of_moves)
            n_queen(pos_X=pos_X - 1, pos_Y=pos_Y + 2, queens_t=queens_t+1, total_queens=copy_of_moves)
            n_queen(pos_X=pos_X - 1, pos_Y=pos_Y - 2, queens_t=queens_t+1, total_queens=copy_of_moves)

if __name__ == "__main__":
    moves = list()
    # Thought I would get at least one result if I go through all the rows or columns but no luck.
    for i in range(board_shape):
        n_queen(i, 0, 0, moves)

我试图使用递归来解决 N-Queen 问题。该算法适用于

board_shape

最大 5 的值。当我输入大于 5 的值时，它只会达到 5 的深度，并且不会执行任何其他操作。

如果可能，请突出显示导致问题的代码，并放置更正的代码。

Answer 1

您的代码不会探索棋盘上所有可能的位置。

n_queen

函数中的递归调用是针对

pos_X

和

pos_Y

值以 1 或 2 的固定增量或减量进行的。这种方法并没有探索棋盘上所有可能的位置。例如，对于尺寸为 9 的棋盘，该函数永远不会尝试 (3, 4)、(4, 5) 等位置。而且我没有看到递归的正确终止条件。

试试这个：

board_shape = 9
results = []

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

    # Check upper diagonal on the 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 the left side
    for i, j in zip(range(row, board_shape, 1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False

    return True

def solve_n_queen(board, col):
    # Base case: If all queens are placed, add the solution to the results list
    if col == board_shape:
        result = []
        for i in range(board_shape):
            for j in range(board_shape):
                if board[i][j] == 1:
                    result.append([i, j])
        results.append(result)
        return

    # Recursive case: Try to place the queen in all rows of the current column
    for i in range(board_shape):
        if is_safe(board, i, col):
            board[i][col] = 1

            # Recur to place rest of the queens
            solve_n_queen(board, col + 1)

            # If placing queen in board[i][col] doesn't lead to a solution,
            # remove the queen from board[i][col]
            board[i][col] = 0

def n_queens():
    board = [[0 for _ in range(board_shape)] for _ in range(board_shape)]
    solve_n_queen(board, 0)
    return results

if __name__ == "__main__":
    solutions = n_queens()
    for solution in solutions:
        print(solution)