Комментарии 17
Только это не волновой алгоритм(который является частным случаем алгоритма Дейкстры для регулярной сетки), а обычный поиск в глубину/ширину. Да и как по мне реализованный довольно вырвиглазно. (но это субъективно)
Вобщем-то где-то как-то так и есть. Главное что оно позволило мне пройти в игрухе уровень, чего бы я ручками стопудово не сделал :)))
Так там ж пропустить пятнашки можно!
Ну пятнашки и есть. В самом начале об этом пишу. Только доска 3x3, а не 4x4 как в классических. Так что даже проще. Однако решение занимает 20 ходов. Причем это КРАТЧАЙШЕЕ решение ! Вы уверены, что сами способны найти его ручками ??? Я мучился часа полтора если не два, прежде чем перейти к радикальным методам.
Там что, ещё где-то пятнашки есть ??? Или Вы про эти ??? Я вобщем-то только начал играть. Дошел до пока обувного магазина. Так что не особо знаю, что там можно пропустить, что нельзя. Вообще игра очень понравилась.
Да не, я к тому, что их скипнуть можно прямо в игре. А так — алгоритм достаточно простой, если понять, какая плиточка отсутствует. Если нижняя правая (как в игре), то надо сперва верхний ряд собрать, потом средний. После этого спокойно дособирается и нижний.
Да ладно. Простейшая же задача. Вы в настоящие пятнашки играли? По сравнению с ними (которые сами по себе — элементарщина) это — ерудна, точно так же собирается первый слой, левый столбец, остаток крутится
Первым делом сделаем скриншот игры с головоломкой
Ощущение, что как минимум одного абзаца нет. Что за игра? Почему нужно делать с неё скриншот, да ещё и первым делом? Вот настоящая загадка, а не этот волновой фронт
Спасибо, поправил. Тут редактор поменялся. Раньше был тег cut, а теперь вместо него текст статей фактически разбивается на две части - заголовок для ленты и основной текст. Я немного подзабыл об этом. Теперь надеюсь стало понятно ?
Да, один абзац как-будто куда-то пропал, судя по логлайнам этой статьи в ВК. Ето Кужлевка.
Пятнашки же вроде рекурсивно решаются вполне успешно.
Есть у нас, например, поле n*n. Собираем сначала верхний и левый ряд, получаем поле (n-1)*(n-1). Ну и повторяем Собираем новый верхний и левый ряд, получаем поле (n-2)*(n-2). Собираем...
А сами пятнашки в игре же вроде можно пропустить?
Спасибо за инфу. Не слыхал о таком. Нужно будет глянуть как это работает. Хотя сходу кажется что это действительно так. Интересно ещё как у рекурсивной сборки с оптимальностью. Алгоритм о котором я пишу, по построению дает кратчайший (точнее один из кратчайших, их может быть несколько) путь к решению. Ибо ищет решение по последовательно увеличивающимся кругам (узлам, лежащим от начального на равных расстояниях).
Кратчайший - да. Только этот алгоритм рассмотрит экспоненциально много промежуточных состояний, кол-во ходов до которых меньше, чем до финального.
Ну вобщем-то конечно это так, задача является NP-полной со всеми вытекающими. Но в данном конкретном случае просмотрено 51079 узлов. Во фронте волны 10877 узлов. На моём ноутбуке считается мгновенно. Глаз во всяком случае никакой задержки не замечает. Т.е. заведомо быстрее трети секунды. Всего состояний доски 9!=362880. Насколько я помню, достижимых из них ровно половина, т.е. 181440. Так что в этой конкретной задаче просматривается примерно треть всех достижимых состояний за треть секунды. Значит даже в наихудшем случае считать будет около секунды. Так что вполне ещё по-божески. Писал я тут на хабре и про куда более жуткие задачки https://habr.com/ru/articles/485786/ :)))
Не суметь "ручками" решить "пятнашку" 3х3 за полтора часа?! Я был лучшего мнения о хабровчанах...
Есть там молот, есть там серп…