Рекурсивная реализация N-Queen
Задача 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 и больше ничего не делает.
Если возможно, выделите код, вызывающий проблему, а также укажите исправленный код.
@anatolyg, «ценности» означают board_shape
Для чего нужен queen_moves?
@Barmar queen_moves был создан для хранения всех возможных позиций ферзей, когда они достигают board_shape. Но мне не удалось достать board_shape с ферзями, поэтому я удалил его из функции.
Ответы 1
Ваш код не исследует все возможные позиции на шахматной доске. Рекурсивные вызовы функции n_queen выполняются с фиксированным увеличением или уменьшением на 1 или 2 для значений pos_X и pos_Y. Этот подход не исследует все возможные позиции на шахматной доске. Например, для шахматной доски размером 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)
Ух ты! Прочитав ваш ответ и час ломая голову, я понял, что эти N-ферзи не обязательно находятся на расстоянии (2,1) или (1,2) друг от друга. Интернет это подтвердил. Спасибо
На моей машине работает нормально? Смотрите здесь