Про решаемость пятнашек

плюсы поставил, но я 15-ки не хотел играть уже лет в 6

Случайно перемещать пустую клетку не эффективно?

А не этот ли принцип положен в основу "Bird sort puzzle" на мобилках? Мне что-то игра так зашла, а на ПК я подобное не могу найти. Действительно, хоть сам пиши. Это все игры про сортировку птичек, переливание жидкостей и такое вот)

Поменяв местами два самых больших числа (14 и 15 для 4x4), мы поменяем четность инверсий

Но ведь можно просто поменять местами любые две соседних ячейки (главное чтобы среди них пустой не было)

Можно немного поменять правила решения - нужно расставить первые 13 фишек по порядку, а 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 позициями :)

Существует и другой, как мне кажется более простой, способ проверять решаемость головоломки. Заключается он в том, чтобы вычислить некую характеристику для 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 и что именно это свойство является ключевым.

У меня тоже андроид пятнашки выложены в андроид стор. Но с самого начала решил не связываться с математикой, и перемешивать пятнашки из исходного состояния случайными тыками. Подобрал число раундов, 1 раунд - смещение тыком на случайную позицию той же вертикали или горизонтали где пустое место. 200 раундов хватает для неплохого перемешивания, если под неплохим понимать то что старшие пятнашки обычно уносит в первую половину доски а младшие в конец. 400 точно хорошо перемешают