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

Привет, я создатель известного в узких кругах приложения 15 Puzzle для Android.

В статье я расскажу, как я генерирую стартовые позиции для своей игры, а также о том, как я добавлял новые конфигурации головоломки.

Игра “Пятнашки”

Классическая игра “Пятнашки” состоит из сетки 4×4, содержащей фишки с числами от 1 до 15 и одну пустую клетку:

Цель игры – перемещая фишки расположить их в возрастающем порядке:

Перемещать можно только те фишки, которые находятся рядом с пустой клеткой (по диагонали нельзя). Решение может выглядеть так:

Генерация стартовых позиций

Каждый раз решать одну и ту же позицию будет скучно, поэтому неплохо было бы найти способ их генерации.

Но сначала давайте разберемся, сколько всего существует уникальных стартовых позиций.

Так как у нас 16 клеток, а каждая клетка может иметь одно из 16 состояний (число или пустое), всего существует 16! (20 922 789 888 000) вариантов. Однако, только половина из них решаемы. Таким образом, имеем 16! / 2 (примерно 1013) стартовых позиций, из которых мы можем достичь целевую.

Значит, при генерации начального состояния нам нужно гарантировать его решаемость, иначе игрок не сможет решить пазл.

Набор предопределенных позиций

Одно из решений может выглядеть так – взять те стартовые состояния, в которых мы уверены, что они решаемые, и выбирать случайное каждый раз.

У такого решения есть проблема – нужно где-то хранить эти состояния. Если мы будем хранить 16! / 2 позиций в виде массива из 16 32-битных чисел, нам потребуется примерно 608 ТБ. А если мы еще захотим иметь разные размеры пазлов (3×3, 5×5 и т.д.), то места нужно будет еще больше.

Есть и другая проблема – как-то нужно сгенерировать 1013 позиций (и каждую из них как-то проверить, что она решаема). Можно создать, например, 105 стартовых состояний, но они в какой-то момент начнут повторяться.

Но если мы заранее можем сгенерировать пусть даже 105 состояний, может будем делать это “на лету”?

Случайные ходы

Вместо подготовки стартовых позиций, мы можем генерировать их по запросу. Алгоритм может быть таким:

1. Начинаем с финальной позиции (здесь и далее 0 – пустая клетка):

    1   2   3   4  5   6   7   8  9  10  11  12 13  14  15   0 

2. Выбираем случайную фишку, например, 6:

    1   2   3   4  5  >6<  7   8  9  10  11  12 13  14  15  >0< 

3. Делая разрешенные ходы, перемещаем 0 на место 6:

    1   2   3   4  5  >0<  6   7  9  10  11   8 13  14  15  12 

4. Повторяем шаги 2-3, пока не получим приемлемый результат

Этот метод гарантирует, что получившаяся позиция будет решаемой. Остается только вопрос – сколько раз нужно повторить шаги 2-3?

Вот график моей симуляции с разным числом итераций и средним количеством необходимых для оптимального решения ходов:

Средняя длина оптимального решения равна 52.59, то есть 150 итераций (повторений шагов 2-3 алгоритма) вполне достаточно.

Проблема с этим методом в том, что на каждой итерации алгоритма (где мы перемещаем 0 в выбранную клетку) в среднем мы будем делать ~2.67 операций обмена в массиве состояния (всего ~400 за 150 итераций). И хотя это не будет заметно для современных компьютеров (и телефонов), есть вариант получше.

Перемешивание с проверкой

Вариант получше – так же берем начальную позицию и перемешиваем. Для 4×4 перемешивание массива из 16 чисел можно совершить за 15 операций обмена, что намного лучше 400.

За 15 операций обмена (дополнительные 0.5 пока проигнорируем) средняя длина решения 53 хода, что почти на 1 ход “сложнее”, чем метод 150 случайных ходов.

Но так как 50% состояний нерешаемы, в половине случаев мы будем генерировать тупиковую позицию.

А что, если бы существовал способ проверить, решаема полученная конфигурация или нет? Берем финальную позицию, перемешиваем, проверяем, и, если все еще нерешаемо – повторяем процесс. При шансе успеха в 50% нужно будет повторить процесс всего несколько раз.

И такой способ есть.

Решаемость

Суть решаемости состоит в четности и инверсиях.

Первым шагом мы считаем количество инверсий в нашей позиции:

Для каждого числа k в позиции (слева направо, сверху вниз), считаем количество чисел, которые стоят после k и меньше этого k (кроме 0)

По сути, мы считаем количество нарушений натурального порядка. Для финальной позиции количество инверсий будет равно 0, т.к. все числа в восходящем порядке.

Давайте посмотрим, как меняется число инверсий, когда мы делаем ход. Например, в этой позиции 52 инверсии:

   8   4  12   3   14   0   9  15    7   2   5   1   10  11  13   6 

Подсчеты

   8   4  12   3  14   0   9  15   7   2   5   1  10  11  13   6  →  7    ^   4  12   3  14   0   9  15   7   2   5   1  10  11  13   6  →  3         ^  12   3  14   0   9  15   7   2   5   1  10  11  13   6  →  9             ^   3  14   0   9  15   7   2   5   1  10  11  13   6  →  2                 ^  14   0   9  15   7   2   5   1  10  11  13   6  →  9                     ^   0   9  15   7   2   5   1  10  11  13   6  →  5                             ^  15   7   2   5   1  10  11  13   6  →  8                                 ^   7   2   5   1  10  11  13   6  →  4                                     ^   2   5   1  10  11  13   6  →  1                                         ^   5   1  10  11  13   6  →  1                                             ^   1  10  11  13   6  →  0                                                 ^  10  11  13   6  →  1                                                     ^  11  13   6  →  1                                                         ^  13   6  →  1                                                             ^   6  →  0                                                                 ^    ==                                                                     52 

Если мы делаем ход в горизонтальном направлении, то число инверсий не меняется:

   8   4  12   3   14  >9< >0< 15    7   2   5   1   10  11  13   6 

Так как мы не считаем 0, порядок чисел остается таким же.

Однако, ход по вертикали меняет количество инверсий. Переместив 4, получим 53:

   8  >0< 12   3   14  >4<  9  15    7   2   5   1   10  11  13   6 

Обратите внимание, что мы не только меняем количество инверсий, но и четность: было 52, стало 53.

Чтобы понять, почему число инверсий меняется, посмотрим на состояния до:

8   4  12   3  14   0  - остальные числа - 

И после:

8   0  12   3  14   4  - остальные числа - 

В виде таблицы:

Для пазлов с шириной в 4 клетки между 0 и перемещаемым числом будет всегда находится 3 других числа. Так как 3 нечетное, никогда не возникнет ситуация, когда количество чисел “до” и количество чисел “после” будет одинаковым. Таким образом, возможны такие варианты:

• Если 3 числа больше, чем перемещаемое число, то число инверсий уменьшается на 3

• Если 2 числа больше, чем перемещаемое число, то число инверсий уменьшается на 1

• Если 1 число больше, чем перемещаемое число, то число инверсий увеличивается на 1

• Если нет чисел больше, чем перемещаемое число, то число инверсий увеличивается на 3

Для пазлов с нечетной шириной всегда будет находится четное количество чисел, поэтому четность инверсий не меняется

В финальной позиции 0 находится в первой строке снизу (считать будем всегда снизу), т. е. четность инверсий не будет совпадать с четностью номера строки пустой клетки.

Таким образом, позиция будет решаемой в двух случаях:

• Число инверсий четное и 0 в нечетной строке

• Число инверсий нечетное и 0 в четной строке

Весь алгоритм для определения решаемости позиции:

1. Посчитать количество инверсий

2. Посмотреть на ширину пазла:

   • если ширина нечетная и число инверсий четное, то позиция решаемая (иначе – нерешаемая)

   • если ширина четная:

     1. Найти номер строки пустой клетки, считая снизу

     2. Посмотреть на число инверсий:

        • если число инверсий четное и номер строки пустой клетки нечетный, то позиция решаемая (иначе – нерешаемая)

        • если число инверсий нечетное и номер строки пустой клетки четный, то позиция решаемая (иначе – нерешаемая)

Пример:

  12  13  11   2    4   5   3  14    1   9  15   6    8   7   0  10 

1. Посчитать количество инверсий – 52

2. Ширина пазла четная, номер строки пустой клетки – 1

3. Число инверсий четное (52), номер строки пустой клетки нечетный (1), поэтому позиция решаемая (в 57 ходов)

Что делать, если позиция нерешаемая? Как я уже говорил ранее, можно перемешивать массив чисел, пока не получим решаемую позицию. А можно воспользоваться небольшой хитростью:

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

То есть, получая после перетасовки нерешаемую комбинацию, мы просто меняем местами два числа, делая ее решаемой.

Вот откуда берутся дополнительные 0.5 на графике – в 50% случаев мы сразу получим правильную позицию, а в остальных нам нужно будет сделать одну дополнительную операцию (16-ю), что в результате дает нам 15.5 операций обмена в среднем.

Расширение игры

Различные ширина и высота

Возможно вы обратили внимание, что решаемость пятнашек привязана к ширине пазла, но о высоте не сказано ни слова. Ошибки нет: высота пазла может быть любой, а правила будут работать те же.

Змейка, спираль и прочие

До этого момента мы рассматривали только финальные позиции, где числа идут в возрастающем порядке, слева направо, сверху вниз. Но также мы можем расположить цифры в другом порядке. Например, “змейка”:

   1   2   3   4    8   7   6   5    9  10  11  12    0  15  14  13 

К сожалению, для такой конфигурации наш алгоритм работать не будет. Чтобы исправить эту проблему, давайте посмотрим, как именно мы считаем инверсии:

Для каждого числа k в позиции (слева направо, сверху вниз)

То есть мы обходим клетки в порядке чисел финальной позиции (o – начало, x – конец):

   o   →   →   →    →   →   →   →    →   →   →   →    →   →   →   x 

Но для “змейки” порядок другой:

   o   →   →   ↘    ↙   ←   ←   ↙    ↘   →   →   ↘    x   ←   ←   ↙ 

Нам всего лишь нужно изменить порядок обхода для каждой второй строки.

И не нужно проверять ширину

Чтобы это понять, посмотрим, что происходит, когда мы делаем ход в змейке:

   1   2   3   4    8   7   6   5   >9<  10  11  12   >0<  15  14  13 

Для простоты будем смотреть только на затрагиваемые числа:

   -   -   -   -    -   -   -   -   >0<  10  11  12   >9<  15  14  13 

В любом случае, даже для других размеров пазла, количество чисел между пустой клеткой и перемещаемой будет четным:

   1   2   3    6  >0<  4    7  >5<  8 

   -   -   -    6  >5<  -    7  >0<  - 

Как мы видим, четность инверсий не меняется.

Алгоритм прост:

1. Обходим клетки в порядке, в котором числа находятся в финальной позиции, считаем количество инверсий

2. Если число инверсий четное, позицию можно решить, иначе – нельзя

Для такой “спирали”:

   o   →   →   ↘    ↗   →   ↘   ↓    ↑   x   ↙   ↓    ↖   ←   ←   ↙ 

Алгоритм аналогичный. Также алгоритм будет работать для любой конфигурации, если мы можем нарисовать линию, не отрывая ручку от бумаги:

  ↗   ↘   x   o   ↑   ↓   ↑   ↓   ↑   ↘   ↗   ↓   ↖   ←   ←   ↙ 

Случайное отсутствующее число

Есть еще одна интересная конфигурация пятнашек: вместо удаления 16 с поля, удаляем любое другое случайное число.

Применяя наш алгоритм на таких конфигурациях, мы будем получать 50% нерешаемых состояний, хотя алгоритм будет говорить обратное:

  12   8   7  15    0   6   4   1   10   9  13  11    3  16  14   5 

В этой позиции отсутствует число 2, 50 инверсий и пустая клетка стоит в третьей строке (помним, что считаем снизу), то есть, позиция решаемая. Однако, попробовав решить ее вы получите нечто такое (11 и 10 в обратном порядке):

   1   0   3   4    5   6   7   8    9  11<>10  12   13  14  15  16  

Такое будет происходить в случаях, когда номер строки пустой клетки в финальной позиции четный.

Что тут можно сделать?

Универсальный алгоритм

Давайте обратим внимание на две вещи:

1. Четность количества инверсий в стартовой и финальной позиции

2. Четность номера строки пустой клетки в стартовой и финальной позиции

Для пазлов с нечетной шириной мы проверяем, совпадает ли четность числа инверсий для стартовой и финальной позиции.

Для пазлов с четной шириной номер строки пустой клетки может быть любым, поэтому мы просто возьмем разницу между номерами строк в начальной и финальной позиции.

Обобщая, алгоритм достижимости из стартовой позиции S финальной позиции G такой:

1. Посчитать количество инверсий в G – I(G)

2. Посчитать количество инверсий в S – I(S)

3. Если:

   • ширина нечетная, а четность I(G) и I(S) совпадает, G достижимо из S (другими словами, S – решаемая позиция)

   • ширина четная:

     1. Найти номер строки1 пустой клетки в G – B(G)

     2. Найти номер строки пустой клетки в S – B(S)

     3. Если I(G):

        • четно, а четность I(S) и B(G) - B(S)2 совпадает, G достижимо из S

        • нечетно, а четность I(S) и B(G) - B(S) различается, G достижимо из S

4. В прочих случаях G недостижимо из S

1 Можно считать снизу, сверху, с 0 или 1 – не важно. Так как в следующем шаге мы вычитаем номера строк, нас интересует только разница позиций пустых клеток в стартовом и финальном состояниях

2 B(G) - B(S) можно заменить на B(G) + B(S), потому что нам нужна только четность

Hidden text

На самом деле, нам не нужны никакие дополнительные алгоритмы.

Можно просто делать отображение нужной нам позиции на позицию классических пятнашек.

Реализация алгоритма на Java:

/**  * Подсчет количества инверсий в {@code list}  */ int inversions(     List<Integer> list ) {     int inversions = 0;     int size = list.size();     for (int i = 0; i < size; i++) {         int n = list.get(i);         if (n <= 1) {             // для 0 и 1 проверка не нужна             continue;         }         for (int j = i + 1; j < size; j++) {             int m = list.get(j);             if (m > 0 && n > m) {                 inversions++;             }         }     }     return inversions; }  /**  * Проверка на то, что состояние {@code goal} достижимо из состояния  * {@code start} для пазла шириной {@code width}  */ boolean isSolvable(     List<Integer> start,     List<Integer> goal,     int width ) {     int startInversions = inversions(start);     int goalInversions = inversions(goal);     if (width % 2 == 0) {         int goalZeroRow = goal.indexOf(0) / width;         int startZeroRow = start.indexOf(0) / width;         if (goalInversions % 2 == 0) {             return startInversions % 2 == (goalZeroRow + startZeroRow) % 2;         } else {             return startInversions % 2 != (goalZeroRow + startZeroRow) % 2;         }     } else {         // четность 'startInversions' и 'goalInversions' должна совпадать         return startInversions % 2 == goalInversions % 2;     } } 

Бонус: случайные цели

Универсальный алгоритм будет работать для любых конфигураций пазла, вне зависимости от позиции пустой клетки или отсутствующего числа.

Заключение

Спасибо, что дочитали статью до конца. Надеюсь, вы теперь знаете чуть больше о пятняшках.

И, если хотите поиграть в саму игру, попробуйте мою реализацию на Android.