Открыть список
Как стать автором
Обновить

Комментарии 40

Небольшой коммент, почему формула работает. Достаточно убедиться, что любой ход не меняет четность N. Следовательно, играя по правилам, нельзя перевести «четную» позицию в «нечетную». У правильной позиции (где все костяшки идут строго по номерам) N будет четным, а у непавильной (где, например, 14 и 15 переставлены) — нечетной.
У себя я решил это иначе. Формула — математически корректное решение. Но лично я перед игрой перетасовываю все пятнашки на глазах у пользователя. Имхо, в этом дополнительный плюс — пользователь заранее знает, что комбинация — точно решаемая.
В начале мы сделали так же, но для пользователя достаточно долго ожидать старта игры, поэтому мы отказались от такого решения. Фишки просто перелетают сразу на позиции.
Совершенно верно, ведь пользователь может запомнить решение!
100 ходов? Крутой. Думаю, он может получить за это вознаграждение!
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Там справа-сверху есть количество ходов до конца)
Спасибо, приятно)
Ну… Это всё-таки демонстрация фреймворка, мне надо было показать плавную анимацию, а не проработанную игру =)
Всё хорошо, но данный алгоритм является обычной имитацией среднестатистического игрока. И поэтому достаточно примитивен.
Просто вариант превращения позиции не представляет никакого интереса. Алгоритм решения за минимальное количество ходов более ценен для подобных задач.
Алгоритм достаточно прост, решается обычным перебором.
И сколько же по времени будет работать перебор решения на 40 ходов? O(4^40)?
Навскидку трудно сказать, но если делать перебор в ширину с запоминанием позиции, которые уже были, алгоритм выглядит достаточно простым и быстрым. Только может возникнуть проблема с памятью.
Насчёт быстроты — зависит от реализации, ну а использование ресурсов — та самая причина, почему данная трактовка на несколько порядков сложнее наивного алгоритма без ограничений.
Можно попробовать ввести в перебор ограничения, чтобы каждая следующая позиция вела к уменьшению количества беспорядков, а так же эта комбинация еще не посещалась.
когда-то реализовывал поиск решения используя алгоритм А*(эвристика — к-во не правильно расположенных пятнашек).
для 15 ходов ищет 0.035 сек.
для 39 ходов ищет 31 сек.

Думаю, альфа-бета отсечения спасут мир. Надо будет попробовать как-нибудь)
Принцип: «хороший дизайн и вы продадите любую тривиальность!» — в действии.
tiler
простите, что похоже на рекламу, но принцип, описанный 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) комбинаций, не имеет решений.

Студенты-математики смотрят на вас с недоумением. Это чистый матан. Теория групп, циклы и все такое. Проходили курсе на втором или третьем.
Не всеж математики. Есть еще физики и прочие…
На физфаке как раз в базовом курсе теория групп куда жестче, чем в базовом курсе мехмата:)
В МГУ — может быть, в ПетрГУ — нет.
У нас не было на физфаке теории групп. Вам повезло.
Или, возможно, меня дезинформировали. Теперь надо вспомнить, кто из физваковцев мне рассказывал про курс теории групп на 3 семестра)
На 3 семестра? Точно обманули. Не так уж глубоко на физфаке дают математику.
Студенты-математики смотрят на Ваш комментарий с недоумением. Когда это теория групп и циклы успели попасть в курс матана? Алгебра это, алгебра!
И в самом деле, непонятно. Из статьи можно сделать вывод, что авторы перебрали пару триллионов комбинаций, и каждую проверили (пусть даже проверка велась аналитически, а не поиском решения). Сколько же это заняло времени?
А если результат про нерешаемые перестановки был получен из общих соображений, то в чем неожиданность? Или неожиданностью было увидеть в Вики или где-нибудь еще сам факт, что есть нерешаемые перестановки?
Не так все просто. Чему учат на алгебре? Что у перестановки есть четность и что она меняется при транспозиции.
Если мы возьмем позицию, как перестановку из 16 элементов, то каждый ход будет транспозицией, и четность будет меняться. «Ну и что?». Так что надо еще догадаться, что при каждом ходе меняется еще и четность суммы координат пустой клетки, и что в сочетании они дают инвариант. А поиску таких инвариантов (особенно без предварительных знаний/подозрений об его существовании) в общем курсе не учат. Вообще, найти число элементов подгруппы с данными образующими — очень нетривиальная задача. Спросите любого, кто собирал много различных многогранников Рубика (и самостоятельно искал алгоритмы).
Эта игра… Гори в аду!
Мне кажется, вам надо с кем-то поговорить об этом…
И за что человека заминусовали?
Многие игры настолько хороши, что отбирают чрезмерное количество свободного времени. И многие игроки не в силах совладать со стремлением поиграть подольше. Очевидно же.
А вот и нет — я эту игру ненавижу именно за то, что ее просто обожают вставлять в полноценные игры в качестве миниквеста, например. А поскольку в эти игрульки играет девушка моя, то тут просто challenge accepted — пройди девушке игру, надейся на хорошее настроение вечером!
Скачал ее пару дней назад, отличная реализация! Только немного отвлекает таймер, слишком он яркий. Вот если бы был режим на весь экран, было бы совсем круто :)
Попробуем сделать в след апдейте
Максим, опытный JavaScript-разработчик, вполне может превратиться в инди-разработчика. Старт хороший.
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Информация

Дата основания
2010
Местоположение
Кипр
Сайт
crew.taucraft.com
Численность
31–50 человек
Дата регистрации

Блог на Хабре