В этой статье я расскажу о том как генерировать рандомные лабиринты, используя рекурсивный алгоритм с возвратом. Этот алгоритм также может использоваться для решения других задач, которые связанны с неявными графами: судоку, комбинаторика и другие головоломки (например, задача о n ферзях).
Описание алгоритма в общих чертах:
Алгоритм Recursive backtracker - это метод систематического перебора всех возможных вариантов решения задачи, основанный на поиске в глубину (DFS).
Поэтапно, что делает алгоритм на примере графа:
-
Выбираем начальную вершину и делаем ее текущей.