О лабиринтах - от древних лабиринтов до сгенерированных головоломок
Люди рисуют и строят лабиринты тысячи лет, от лабиринта из греческого мифа до лабиринтов из живой изгороди в садах. Сегодня компьютер создаёт новый лабиринт за долю секунды, и его методы хорошо показывают, как простые правила создают сложные формы.
Однопутные и разветвлённые лабиринты
Классический однопутный лабиринт имеет одну извилистую тропу без выбора. В разветвлённом лабиринте есть развилки и тупики, поэтому нужно решать, куда идти. Лабиринты из живой изгороди стали популярны в европейских садах с XVI века, а лабиринты на бумаге с тех пор остаются классикой.
Идеальные лабиринты
В идеальном лабиринте нет петель и замкнутых участков: между любыми двумя клетками ровно один путь. В математических терминах его проходы образуют остовное дерево сетки, поэтому в лабиринте из n клеток ровно n - 1 проходов между клетками.
Как компьютер строит лабиринт
Рекурсивный поиск с возвратом случайно бродит по сетке, ломает стены в ещё не посещённые клетки и отступает назад, когда заходит в тупик. Получаются длинные коридоры с немногими ответвлениями. Алгоритм Прима, наоборот, растит лабиринт от одной клетки наружу, каждый раз присоединяя случайную соседнюю клетку, и даёт много коротких тупиков.
Советы по прохождению
В идеальном лабиринте вы всегда дойдёте до выхода, если держитесь одной рукой за стену и идёте вдоль неё. Это не кратчайший путь, но он всегда работает. Помогает и взгляд от выхода назад к старту, а след не даст дважды зайти в один и тот же тупик.
Часто задаваемые вопросы
Чем разветвлённый лабиринт отличается от однопутного?
В однопутном лабиринте одна тропа без выбора; в разветвлённом есть развилки и тупики. В обычной речи оба называют просто лабиринтом.
Всегда ли работает правило руки на стене?
В идеальном лабиринте да, потому что все стены связаны. В лабиринтах с петлями можно бесконечно ходить вокруг острова.
Насколько большим может быть лабиринт?
Здесь до 100 x 100 клеток, то есть 10 000 клеток с единственным путём между стартом и выходом.
Сопутствующие инструменты
Лабиринт
Играйте в лабиринт бесплатно в браузере. Найдите путь от зелёного старта к красному выходу в лабиринтах от 5 x 5 до 100 x 100, на время или в тумане.
Yahtzee
Играйте в Yahtzee бесплатно в браузере. Бросайте пять кубиков до трёх раз, оставляйте нужные и заполните 13 клеток. Одному, до 4 игроков или против компьютера.
Ханойская башня
Перенесите в браузере башню из дисков между тремя стержнями. По одному диску, никогда больший на меньший. Кратчайшее решение — 2ⁿ − 1 ходов.
О Yahtzee - игра в кости об удаче и выборе
Как устроен Yahtzee: пять кубиков и три броска, 13 клеток, верхний бонус, бонусы Yahtzee, правила джокера и советы, как набрать больше очков.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Играть в лабиринт