Пятнашки

1. Игра в 15

В 1878 году Ноем Чепмэном была придумана игра пятнашки (такен). Головоломка состоит из 15 одинаковых квадратных костяшек, лежащих в квадратной коробке. Каждый такой элемент пронумерован. Коробка же имеет размер 4x4 костяшек (1 квадратик остается пустым). Также могут встречаться и другие вариации этой игры 3x3, 5x5 и другие. Цель игры проста - расположить костяшки по возрастанию номеров, двигая их внутри коробки.

2. Математика перестановок

Количество возможных начальных положений пятнашек равно n!

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

3. Формулировка задачи

Дано 2 матрицы: изначальная и конечная. Реализовать решение задачи (осуществляя поиск в глубину), применяя эвристику.

4. Решение

Для просмотра решения на языке Python вы можете посетить мой репозиторий.