Теоретические основы разработки (математические, алгоритмические)

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

Математическое описание.

Нерешаемая комбинация, предложенная Ноем Чепменом

Пятнашки представляют собой классическую задачу для моделирования эвристических алгоритмов. Обычно задачу решают через количество перемещений и поиск манхэттенского расстояния между каждой костяшкой и её позицией в собранной головоломке. Для решения обычно используется алгоритм IDA*

Можно показать, что ровно половину из всех возможных 20 922 789 888 000 (=16!) начальных положений пятнашек невозможно привести к собранному виду: пусть квадратик с числом расположен до (если считать слева направо и сверху вниз) квадратиков с числами меньшими . Будем считать , то есть если после костяшки с -м числом нет чисел, меньших , то . Также введем число — номер ряда пустой клетки (считая с 1). Если сумма

является нечётной, то решения головоломки не существует.

Для обобщённых пятнашек (с бо́льшим, чем 15, количеством костяшек) задача поиска кратчайшего решения является NP-полной.

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

· IDA*

Алгоритм A* с итеративным углублением (iterative deepening A*, IDA*) — применение идеи итеративного углубления в контексте эвристического поиска.

Неинформированный алгоритм итеративного углубления останавливает развёртывание, когда глубина поиска d превышает текущий предел глубины l. Информированный алгоритм IDA* останавливает развёртывание, когда оценка f(n) стоимости пути через текущий узел n превышает текущий предел стоимости путиbound.

Алгоритм IDA* отличается минимальными затратами памяти по сравнению с A* и сравнительно малым (в случае удачного выбора эвристики) количеством развёрнутых узлов по сравнению с IDDFS.

Псевдокод

node текущий узел

g стоимость начала решения root..node

f оценка стоимости минимального пути через node

h(node) эвристическая оценка стоимости остатка пути node..goal

cost(node, succ) функция стоимости пути

is_goal(node) функция проверки цели

successors(node) функция развёртывания узла node

procedure ida_star(root, cost(), is_goal(), h())

bound := h(root)

loop

t := search(root, 0, bound)

if t = FOUND then return FOUND

if t = ∞ then return NOT_FOUND

bound := t

end loop

end procedure

function search(node, g, bound)

f := g + h(node)

if f > bound then return f

if is_goal(node) then return FOUND

min := ∞

for succ in successors(node) do

t := search(succ, g + cost(node, succ), bound)

if t = FOUND then return FOUND

if t < min then min := t

end for

return min

end function

Примерный алгоритм, с которым можно легко собрать Пятнашки:

Алгоритм ни в коем разе не претендует на оптимальный и самый лучший. Итак по шагам:

1. Ставим "1" на свое место.
2. Ставим "2" на свое место.
3. Ставим "3" на место "4".
4. Ставим "4" на место "8".
Таким образом получаем следующий расклад:

5. Ставим "3" и "4" на свое место
6. Ставим "5" и "6" на свое место "7" и "8" аналогично "3" и "4" Получаем:

7. Ставим "7" и "8" на свои места Выставленные фишки больше никогда не трогаем.
8. Ставим "9" в правый нижний угол, чтобы исключить неопределенную ситуацию
9. Ставим "13" на место "9", "9" на место "10" Получаем:

10. Ставим "13" и "9" на свои места и больше их не трогаем.
11. Загоняем "10" сначало на место "14" а затем в правый нижний угол, чтобы выстроить правильную последовательность. Получаем:

11. Ставим "11" на место "10", чтобы предотвратить неопредленную ситуацию
12. Ставим "10" в правый нижний угол.
13. Ставим "11" на "15".
12. Поднимаем "10" на место"12" под нее ставим "11" и "12" на место "15" Получаем:

13. И очевидными шагами достигаем цели..

Второй примерный алгоритм, сборки головоломки:

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

Стадия 1: сборка верхней строки.

В итоге вы соберёте строку слева на право.

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

Если это не последняя цифра строки, достаточно просто правильно её разместить, просто держите в уме следующие заметки:

Никогда не трогайте части собранные ранее.

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

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

Вниз, вниз, право, вверх, лево, вверх,право, вниз, лево, вверх. Это должно поместить часть на место. Заметим, что это временно нарушает последовательность частей, собранных ранее.

Стадия 2: Сборка остальных частей.

Используйте технику, описанную в стадии 1, что бы последовательно собрать каждую строку, кроме двух последних.

Поверните головоломку на четверть поворота вправо. Левая колонка из двух строк теперь стала верхней строкой.

Используйте технику из стадии 1, что бы последовательно собрать каждую строку, пока их не останется две. Это значит, что осталось собрать квадрат 2 на 2.

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

Если осталось две части которые нужно поменять местами, то головоломку нельзя собрать пока две другие части так же не будут обменены местами. Если где то в головоломке есть ещё две части, которые нужно поменять, то вам придётся собирать головоломку сначала.

Если вы хотите собрать головоломку так, что бы пробел остался в месте отличном от нижнего правого угла, то вы можете использовать тот же метод. Когда окажется. что не собранная строка должна будет иметь пропуск, переверните головоломку вверх ногами и начните её собирать с другого конца. В конце концов не собранная область опять сократится до квадрата 2 на 2, но в этом случае он не будет лежать в нижнем правом углу.

Существуют более быстрые пути сборки последних двух частей строки. Один хороший способ заключается в том, что бы разместить последнюю часть в предпоследнюю позицию строки и затем поставить предпоследнюю часть строки на место (которая сместит последнюю часть на своё законное место).

В моем приложении реализована возможность изменения размера игрового поля для упрощения или усложнения игры, а так же регулируется степень перемешивания костяшек.