Комментарии 40
Небольшой коммент, почему формула работает. Достаточно убедиться, что любой ход не меняет четность N. Следовательно, играя по правилам, нельзя перевести «четную» позицию в «нечетную». У правильной позиции (где все костяшки идут строго по номерам) N будет четным, а у непавильной (где, например, 14 и 15 переставлены) — нечетной.
У себя я решил это иначе. Формула — математически корректное решение. Но лично я перед игрой перетасовываю все пятнашки на глазах у пользователя. Имхо, в этом дополнительный плюс — пользователь заранее знает, что комбинация — точно решаемая.
Всё хорошо, но данный алгоритм является обычной имитацией среднестатистического игрока. И поэтому достаточно примитивен.
Просто вариант превращения позиции не представляет никакого интереса. Алгоритм решения за минимальное количество ходов более ценен для подобных задач.
Просто вариант превращения позиции не представляет никакого интереса. Алгоритм решения за минимальное количество ходов более ценен для подобных задач.
Алгоритм достаточно прост, решается обычным перебором.
И сколько же по времени будет работать перебор решения на 40 ходов? O(4^40)?
Навскидку трудно сказать, но если делать перебор в ширину с запоминанием позиции, которые уже были, алгоритм выглядит достаточно простым и быстрым. Только может возникнуть проблема с памятью.
когда-то реализовывал поиск решения используя алгоритм А*(эвристика — к-во не правильно расположенных пятнашек).
для 15 ходов ищет 0.035 сек.
для 39 ходов ищет 31 сек.
для 15 ходов ищет 0.035 сек.
для 39 ходов ищет 31 сек.
Думаю, альфа-бета отсечения спасут мир. Надо будет попробовать как-нибудь)
Принцип: «хороший дизайн и вы продадите любую тривиальность!» — в действии.
tiler
простите, что похоже на рекламу, но принцип, описанный egormerkushev работает уже третий год :)
простите, что похоже на рекламу, но принцип, описанный egormerkushev работает уже третий год :)
Принцип чертовски эффективен, потому что я купил после одного взгляда на скриншот.
Помню на втором курсе института написал пятнашки на прологе. Там был выбор размер поля и автоматическое прохождение, правда алгоритм был довольно примитивным.
Писал на 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-разработчик, вполне может превратиться в инди-разработчика. Старт хороший.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Игра 15