Comments 48
плюсы поставил, но я 15-ки не хотел играть уже лет в 6
Случайно перемещать пустую клетку не эффективно?
В статье про это написанно:
Проблема с этим методом в том, что на каждой итерации алгоритма (где мы перемещаем
0
в выбранную клетку) в среднем мы будем делать ~2.67 операций обмена в массиве состояния (всего ~400 за 150 итераций). И хотя это не будет заметно для современных компьютеров (и телефонов), есть вариант получше.
Вы про алгоритм со случайными ходами? Если да, то тогда возникает та же проблема, как и с перемешиванием всего массива - нужно соблюсти четность, поэтому придется проверять решаемость. А в таком случае непонятно, зачем только пустую клетку перемещать, когда можно уже весь массив перемешивать.
Набор случайных ходов, стартовавших с финальной позиции всегда решаем. Вот только не всегда интересен, там главная проблема оценки сложности задания (можно сделать 100 случайных ходов а для решения потребуется 2)
можно сделать 100 случайных ходов а для решения потребуется 2
Вот это очень интересный момент. Это сходу не совсем очевидно. Надо выяснить почему это может произойти.
Потому что случайные ходы могут быть и назад: как минимум 1 из 4х возможных ходов всегда -- отмена прошлого хода. Окей, мы можем избегать делать этот ход, но даже тогда мы можем вернуться в одну из прошлых позиций через несколько ходов. Отслеживать их?
Получается задача сложнее, чем сгенерировать случайную выборку и гарантировать её сходимость.
А не этот ли принцип положен в основу "Bird sort puzzle" на мобилках? Мне что-то игра так зашла, а на ПК я подобное не могу найти. Действительно, хоть сам пиши. Это все игры про сортировку птичек, переливание жидкостей и такое вот)
Поменяв местами два самых больших числа (
14
и15
для 4x4), мы поменяем четность инверсий
Но ведь можно просто поменять местами любые две соседних ячейки (главное чтобы среди них пустой не было)
Можно немного поменять правила решения - нужно расставить первые 13 фишек по порядку, а 14 и 15 в любом порядке. Тогда все начальные комбинации будут решаемые.
Для классических пятнашек есть алгоритм проще: Берём любые две ячейки и меняем местами. Решение есть только для чётного количества перестановок.
Если мы генерируем позицию, в которой пустая клетка в последней строке - да. Если мы будем размещать пустую клетку случайно, то нужная четность перестановок будет варьироваться в зависимости от строки, т. к. в классической версии ход по вертикали всегда меняет четность на противоположную.
Обмен должен быть "по горизонтали" - то есть меняем не любые две, а две соседние в одной горизонтали (причём ни одна из них - не ноль).
Для классических любые две.
Причём и пустую тоже. Вот совсем непринципиально. В случайном порядке.
Вопрос только в четности. Причём кажется даже размер поля не влияет.
Давно было, писали как лабу, ещё на паскале. И тоже был вопрос в решаемости. Тогда ещё интернета толком не было. Тупо методом проб нашли решение.
Вот с пустой кажись погорячился. Трогать её нельзя по этому алгоритму.
Она вносит сумятицу.
А вот размерность может быть любая, и желаемое расположение тоже произвольное, хоть зигзагом )
Просто четность перестановок.
Это исходит из самой сути игры.
Просто проверьте )))
И не надо вообще никакой огород городить. Простите что сломал вам всю математику )
Нет там вертикали или горизонтали. Есть только четность. Забудь что написано на костяшках это не принципиально. Восстановить можно только пройдя путь в обратную сторону. Отсюда и четность. Один раз идёшь вперёд, другой раз назад.
2n перестановок.
И доказывается ведь элементарно )))
Если мы переставляем любые две фишки то решения нет, а если сделать это ещё раз то решение есть.
Это как с 14 и 15. Представьте что именно их вы переставляли в обоих случаях.
Первый раз слышу, что у пятнашек бывают не сходящиеся расклады. Я столько раз в них играл в детстве и ни разу не было такого, чтоб не сошлось.
Для того чтобы наткнуться на это нужны пятнашки, из которых "квадратики" можно выбросить, перемешать, а затем обратно засунуть в случайном порядке.
Не нужны. Нерешаемость позиции означает, что эту позицию невозможно получить из финальной - ведь любой ход обратим. И это известная нерешаемая задачка - предложение поменять местами любые две соседние плитки (или обычно говорят о плитках 14 и 15 в стандартном конечном расположении), оставив все остальные плитки на своих местах.
Именно такие у меня и были. Я прямо сильно удивился, узнав из статьи о несудимости половины позиций.
Если мы будем хранить
16! / 2
позиций в виде массива из 16 32-битных чисел, нам потребуется примерно 608 Т
не слишком круто тратить 32 бита на кодирование?
Чтобы число от 0 до 16 закодировать достаточно 5 бит.
Массив 4x4 = 16 элементов 16x5 = 80 бит = 10 байт на позицию.
Берем расскладку 1-15 (собранная),
1,2,3,4
5,6,7,8
9,10,11,12
13,14,15, 0
если ее повернуть на 90 градусов влево, получим
13,9,5,1
14,10,6,2,
15,11,7,3,
0, 12,8,4
т.е. существуют 4 вирианта отображения позиции,
кодируем еще 3-мя битами.
таким обазом у нас уходит 11 байт на все про все, плюс 7 бит на дополнительные флаги.
(20922789888000/4) * 11 (байт на позицию)/(1024*1024*1024*1024) = ~52 TB
Поскольку нам нужны только решаемые позиции, то их будет половина, т.е. надо 26 TB.
Начальная оценка автора была 608 TB, мы уложились в 26 TB, что в 26 раз меньше первоначальной оценки.
Из курса физики мы знаем, что значением в формуле можно пренебречь, если оно в 10 и более раз меньше остальных згачений, т.е. размером хранимых данных можно пренебречь и хранить все позиции в памяти :)
Допустим что игрок собирает пятнашки за 1 секунду,
считаем что он непрерывно играет 24x7*100 лет подряд, тогда нам надо сгенерировать
60*24 * 365 *100 = 52560000 позиций,
исходя из 11 байт на позицию получаем всего лишь 551 Mb. :)
что по современным меркам вообще не размер.
Дерзайте!
P.S. для тех кто решит все 52560000 позиций, предложите бесплатную подписку на следующую версии игра с новыми 52560000 позициями :)
А еще можно дополнительно отбрасывать зеркальные позиции, позиции с числами в обратном порядке (может еще какие-нибудь конфигурации найдутся) - примерно еще раз в 8 объем сократим.
Но этот вопрос уже за рамками моей статьи :)
Да я вообще не понимаю смысла этого кодирования, если просто номер позиции однозначно определяет расположение всех костей, и наоборот. А потому вполне достаточно хранить битовую карту. Не, 1,3 Тбайт - тоже не сахар, но это гораздо более вменяемый объём.
плюс 7 бит на дополнительные флаги
Дополнительные флаги, думаю, не нужны - если мы оптимизируем, исключая повороты, отзеркаливания и т.д., то можно хранить только набор уникальных позиций, и при создании новой игры случайным образом поворачивать пазл, отзеркаливать и т. д.
Допустим что игрок собирает пятнашки за 1 секунду,
Если мы не ищем оптимальные решения (а нам нужно найти хоть какое-то решение), то компьютер будет решать намного быстрее.
На Ryzen 9 7900X у меня уходит около 5мс на позицию, т. е. `16!` позиций можно проверить за ~1200 тысяч дней. Если написать алгоритм решения на Rust (мой написан на Java), взять более мощный процессор, решать в несколько потоков (и/или распараллелить на несколько машин), то вполне можно уложиться в несколько лет.
Вопрос что делать если позиция оказалась не решаемой? За сколько времени компьютер придёт к выводу что она не решаемая?
Можно установить какой-нибудь лимит: по времени или глубине поиска (например, используя A* и ε-admissible эвристики). Так как 100% позиций требуют для оптимального решения 80 ходов или меньше, мы можем выбрать какую-нибудь верхнюю границу и просто останавливать поиск решения при ее достижении.
Чтобы число от 0 до 16 закодировать достаточно 5 бит.
Там числа от 0 до 15, достаточно 4 бит.
Допустим что игрок собирает пятнашки за 1 секунду,
считаем что он непрерывно играет 24x7*100 лет подряд, тогда нам надо сгенерировать
60*24 * 365 *100 = 52560000 позиций,
Надо умножить ещё на 60 (60 секунд в минуте и 60 минут в часе)
3 153 600 000 позиций и
исходя из 11 байт на позицию получаем
~32Gb
Существует и другой, как мне кажется более простой, способ проверять решаемость головоломки. Заключается он в том, чтобы вычислить некую характеристику для start и для goal и сравнить ее: если характеристика совпала, то существует "путь" от позиции start к позиции goal.
Теперь непосредственно про вычисление характеристики.
1. Необходимо обойти головоломку "змейкой", то есть обойти в следующем порядке:
1 2 3 4
8 7 6 5
9 10 11 12
16 15 14 13
Данный обход можно обощить на любой размер доски: обходим доску строчку за строчкой, четные (предполагается нумерация с 0) обходим слева направо, нечетные справа налево.
2. Выписать встретившиеся значения фишек, то есть выписать только ненулевые значения ячеек. Полученная набор чисел является перестановкой множества чисел от 1 до 15.
Для приведенного автором статьи примера
12 13 11 2
4 5 3 14
1 9 15 6
8 7 0 10
числа будут выписаны в следующем порядке: 12, 13, 11, 2, 14, 3, 5, 4, 1, 9, 15, 6, 10, 7, 8.
3. Характеристикой является четность описанной в прошлом пункте перестановки. Как посчитать четность? Отсортировать массив, подсчитав количество swap'ов. Четностью перестановки будет четность количества swap'ов.
Какова сложность данного алгоритма?
По памяти: .
По времени: .
P.S. Может возникнуть вопрос почему сложность по времени , а не . Ошибки здесь нету. Все дело в том, что в данной задаче массив имеет специфичный вид и за счет этого его можно отсортировать за линейное время. Кому интересно предлагаю самостоятельно разобраться почему это так, я же просто оставлю код сортировки массива, являющегося перестановкой множества :
for (int i = 0; i < perm.length; i++) {
while (perm[i] != i) {
// swap(a, i, j) меняет местами a[i] и a[j]
swap(perm, i, perm[i]);
}
}
Отмечу, что в отсортированном массиве perm[i] == i для всех i от 0 до perm.length и что именно это свойство является ключевым.
Не понял, и чем же это проще?
Выбранный автором способ обхода для построения перестановки привел к необходимости учитывать множество факторов таких как четность ширины доски, четность номера столбца с нулем. В таком обилии условий легко запутаться.
Про сложность говорить смысла особо нету, так как размер доски небольшой и оба алгоритма отработают мгновенно.
Что-то я накосячил с оформлением формул в пост скриптуме. Я хотел написать ".. O(mn), а не O(mn log(mn))".
У меня тоже андроид пятнашки выложены в андроид стор. Но с самого начала решил не связываться с математикой, и перемешивать пятнашки из исходного состояния случайными тыками. Подобрал число раундов, 1 раунд - смещение тыком на случайную позицию той же вертикали или горизонтали где пустое место. 200 раундов хватает для неплохого перемешивания, если под неплохим понимать то что старшие пятнашки обычно уносит в первую половину доски а младшие в конец. 400 точно хорошо перемешают
Не знаю, мне Sonnet за 5 шотов сделал фото-пятнашки, вся семья играет уже три дня не можем оторваться https://allchat.online/chat/66b686e821636646fdb551aa
Про решаемость пятнашек