tgoop.com/the_algorithms/4665
Last Update:
Задача о ходе коня
Головоломка, в которой требуется найти маршрут хода коня на шахматной доске, проходящий через все клетки только один раз.
Алгоритм:
1. Создаем шахматную доску n x n, где n - размерность доски.
2. Инициализируем текущую позицию коня на доске.
3. Помечаем текущую позицию как посещенную.
4. Проверяем, есть ли еще непосещенные клетки на доске:
- Если все клетки посещены, то задача решена, и мы можем вернуть найденный маршрут.
- Если не все клетки посещены, переходим к следующему шагу.
5. Находим все возможные ходы коня из текущей позиции:
- Проверяем, что следующий ход находится в пределах доски и не был посещен.
6. Для каждого возможного хода коня:
- Передвигаем коня на следующий ход.
- Рекурсивно вызываем алгоритм для новой позиции коня.
- Если рекурсивный вызов вернул true (маршрут найден), то возвращаем true.
- Если рекурсивный вызов вернул false, отменяем текущий ход и ищем другие возможные ходы.
Сложность: O(8^n), где n - размерность доски.
BY Алгоритмы и структуры данных
Share with your friend now:
tgoop.com/the_algorithms/4665