В этой статье блога мы окунемся в увлекательный мир проблемы N-ферзей — классической головоломки, которая заставляет программистов найти все возможные способы разместить N ферзей на шахматной доске размера N x N так, чтобы два ферзя не угрожали друг другу.. Мы рассмотрим несколько методов решения этой проблемы, используя разговорный язык и попутно предоставляя примеры кода.

Метод 1: подход грубой силы
Подход грубой силы включает в себя создание всех возможных комбинаций размещения ферзей и проверку каждой комбинации на достоверность. Несмотря на свою простоту, этот метод становится неэффективным для больших значений N из-за его экспоненциальной временной сложности. Вот упрощенный фрагмент кода на Python:

def is_valid(board, row, col):
    # Check for any queens in the same row or diagonal
    for i in range(row):
        if board[i] == col or board[i] - col == i - row or board[i] - col == row - i:
            return False
    return True
def solve_n_queen(n):
    solutions = []
    board = [-1] * n  # Initialize an empty board

    def backtrack(row):
        if row == n:
            solutions.append(board[:])  # Found a valid solution
        else:
            for col in range(n):
                if is_valid(board, row, col):
                    board[row] = col
                    backtrack(row + 1)

    backtrack(0)
    return solutions
n = 4  # Change this value to try different board sizes
solutions = solve_n_queen(n)
print(solutions)

Метод 2: оптимизированный обратный поиск
Чтобы повысить эффективность метода грубой силы, мы можем использовать обратный поиск в сочетании с методами сокращения. Одна из оптимизаций заключается в том, чтобы избежать ненужной проверки уже занятых строк и столбцов. Вот оптимизированная версия кода:

def solve_n_queen(n):
    solutions = []
    board = [-1] * n  # Initialize an empty board

    def backtrack(row, cols, diag1, diag2):
        if row == n:
            solutions.append(board[:])  # Found a valid solution
        else:
            for col in range(n):
                if col not in cols and row + col not in diag1 and row - col not in diag2:
                    board[row] = col
                    backtrack(row + 1, cols | {col}, diag1 | {row + col}, diag2 | {row - col})

    backtrack(0, set(), set(), set())
    return solutions
n = 4  # Change this value to try different board sizes
solutions = solve_n_queen(n)
print(solutions)

Метод 3: Битовая маска
Более продвинутый метод предполагает использование битовых масок для представления занятых позиций на шахматной доске. Этот метод значительно снижает использование памяти и улучшает время выполнения. Вот пример реализации на Python:

def solve_n_queen(n):
    solutions = []

    def backtrack(row, cols, diag1, diag2):
        if row == n:
            solutions.append(bin(cols)[2:].zfill(n))  # Found a valid solution
        else:
            available_positions = ((1 << n) - 1) & (~(cols | diag1 | diag2))
            while available_positions:
                position = available_positions & -available_positions
                col = bin(position - 1).count('1')
                backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1)
                available_positions &= ~position

    backtrack(0, 0, 0, 0)
    return solutions
n = 4  # Change this value to try different board sizes
solutions = solve_n_queen(n)
print(solutions)

В этой статье мы рассмотрели три различных метода решения проблемы N-Queen: метод грубой силы, оптимизированный возврат и битовую маску. Каждый метод имеет свои преимущества и компромиссы с точки зрения временной и пространственной сложности. Понимая эти подходы, вы сможете эффективно решить проблему N-Queen и получить представление о фундаментальных методах решения проблем.