Решение проблемы N-ферзей в Python: возврат и рекурсивный подход

Вот код Python для решения задачи N-Queens, где N установлено равным 8:

def is_safe(board, row, col):
    # Check if there is a queen in the same column
    for i in range(row):
        if board[i][col] == 1:
            return False
    # Check upper diagonal on the left side
    i = row - 1
    j = col - 1
    while i >= 0 and j >= 0:
        if board[i][j] == 1:
            return False
        i -= 1
        j -= 1
    # Check upper diagonal on the right side
    i = row - 1
    j = col + 1
    while i >= 0 and j < N:
        if board[i][j] == 1:
            return False
        i -= 1
        j += 1
    return True

def solve_n_queens(board, row):
    if row >= N:
        return True
    for col in range(N):
        if is_safe(board, row, col):
            board[row][col] = 1
            if solve_n_queens(board, row + 1):
                return True
            board[row][col] = 0
    return False

def print_solution(board):
    for i in range(N):
        for j in range(N):
            print(board[i][j], end=" ")
        print()
N = 8
board = [[0] * N for _ in range(N)]
if solve_n_queens(board, 0):
    print_solution(board)
else:
    print("No solution exists.")

Этот код использует алгоритм обратного поиска для поиска решения проблемы N-ферзей. Он проверяет каждую комбинацию строк и столбцов, чтобы разместить ферзя, и при этом гарантирует, что никакие два ферзя не угрожают друг другу.

Вот несколько способов решения проблемы N-ферзей:

  1. Алгоритм возврата
  2. Рекурсивный подход
  3. Проблема удовлетворения ограничений
  4. Поиск в глубину (DFS)
  5. Битовые манипуляции