Вот код 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-ферзей:
- Алгоритм возврата
- Рекурсивный подход
- Проблема удовлетворения ограничений
- Поиск в глубину (DFS)
- Битовые манипуляции