Comments 40
Небольшой коммент, почему формула работает. Достаточно убедиться, что любой ход не меняет четность N. Следовательно, играя по правилам, нельзя перевести «четную» позицию в «нечетную». У правильной позиции (где все костяшки идут строго по номерам) N будет четным, а у непавильной (где, например, 14 и 15 переставлены) — нечетной.
У себя я решил это иначе. Формула — математически корректное решение. Но лично я перед игрой перетасовываю все пятнашки на глазах у пользователя. Имхо, в этом дополнительный плюс — пользователь заранее знает, что комбинация — точно решаемая.
Всё хорошо, но данный алгоритм является обычной имитацией среднестатистического игрока. И поэтому достаточно примитивен.
Просто вариант превращения позиции не представляет никакого интереса. Алгоритм решения за минимальное количество ходов более ценен для подобных задач.
Просто вариант превращения позиции не представляет никакого интереса. Алгоритм решения за минимальное количество ходов более ценен для подобных задач.
Алгоритм достаточно прост, решается обычным перебором.
И сколько же по времени будет работать перебор решения на 40 ходов? O(4^40)?
Навскидку трудно сказать, но если делать перебор в ширину с запоминанием позиции, которые уже были, алгоритм выглядит достаточно простым и быстрым. Только может возникнуть проблема с памятью.
Насчёт быстроты — зависит от реализации, ну а использование ресурсов — та самая причина, почему данная трактовка на несколько порядков сложнее наивного алгоритма без ограничений.
когда-то реализовывал поиск решения используя алгоритм А*(эвристика — к-во не правильно расположенных пятнашек).
для 15 ходов ищет 0.035 сек.
для 39 ходов ищет 31 сек.
для 15 ходов ищет 0.035 сек.
для 39 ходов ищет 31 сек.
Думаю, альфа-бета отсечения спасут мир. Надо будет попробовать как-нибудь)
Принцип: «хороший дизайн и вы продадите любую тривиальность!» — в действии.
Помню на втором курсе института написал пятнашки на прологе. Там был выбор размер поля и автоматическое прохождение, правда алгоритм был довольно примитивным.
Писал на 3ем курсе тоже (12 лет назад), только задание было по теме «сетевые технологии» или как-то так… Добавил в свободном поле видимость как играет удаленный пользователь. Можно на скорость с другом играть например. Вот, может идея вашему Максиму пригодится :)
Вот за что я люблю скриптовые и не люблю компилируемые языки…
from itertools import chain
from operator import gt
def is_valid(field):
permutation = chain(*field)
return len(filter(None, [gt(permutation[i], a) for i in xrange(len(permutation)) for a in permutation[i+1:]])) % 2 == 0
Для многих из нас стало неожиданностью, что ровна половина из всех возможных (1 307 674 368 000) комбинаций, не имеет решений.
Студенты-математики смотрят на вас с недоумением. Это чистый матан. Теория групп, циклы и все такое. Проходили курсе на втором или третьем.
Не всеж математики. Есть еще физики и прочие…
Студенты-математики смотрят на Ваш комментарий с недоумением. Когда это теория групп и циклы успели попасть в курс матана? Алгебра это, алгебра!
И в самом деле, непонятно. Из статьи можно сделать вывод, что авторы перебрали пару триллионов комбинаций, и каждую проверили (пусть даже проверка велась аналитически, а не поиском решения). Сколько же это заняло времени?
А если результат про нерешаемые перестановки был получен из общих соображений, то в чем неожиданность? Или неожиданностью было увидеть в Вики или где-нибудь еще сам факт, что есть нерешаемые перестановки?
А если результат про нерешаемые перестановки был получен из общих соображений, то в чем неожиданность? Или неожиданностью было увидеть в Вики или где-нибудь еще сам факт, что есть нерешаемые перестановки?
Не так все просто. Чему учат на алгебре? Что у перестановки есть четность и что она меняется при транспозиции.
Если мы возьмем позицию, как перестановку из 16 элементов, то каждый ход будет транспозицией, и четность будет меняться. «Ну и что?». Так что надо еще догадаться, что при каждом ходе меняется еще и четность суммы координат пустой клетки, и что в сочетании они дают инвариант. А поиску таких инвариантов (особенно без предварительных знаний/подозрений об его существовании) в общем курсе не учат. Вообще, найти число элементов подгруппы с данными образующими — очень нетривиальная задача. Спросите любого, кто собирал много различных многогранников Рубика (и самостоятельно искал алгоритмы).
Если мы возьмем позицию, как перестановку из 16 элементов, то каждый ход будет транспозицией, и четность будет меняться. «Ну и что?». Так что надо еще догадаться, что при каждом ходе меняется еще и четность суммы координат пустой клетки, и что в сочетании они дают инвариант. А поиску таких инвариантов (особенно без предварительных знаний/подозрений об его существовании) в общем курсе не учат. Вообще, найти число элементов подгруппы с данными образующими — очень нетривиальная задача. Спросите любого, кто собирал много различных многогранников Рубика (и самостоятельно искал алгоритмы).
Эта игра… Гори в аду!
Мне кажется, вам надо с кем-то поговорить об этом…
И за что человека заминусовали?
Многие игры настолько хороши, что отбирают чрезмерное количество свободного времени. И многие игроки не в силах совладать со стремлением поиграть подольше. Очевидно же.
Многие игры настолько хороши, что отбирают чрезмерное количество свободного времени. И многие игроки не в силах совладать со стремлением поиграть подольше. Очевидно же.
Скачал ее пару дней назад, отличная реализация! Только немного отвлекает таймер, слишком он яркий. Вот если бы был режим на весь экран, было бы совсем круто :)
Максим, опытный JavaScript-разработчик, вполне может превратиться в инди-разработчика. Старт хороший.
Sign up to leave a comment.
Игра 15