Хочу спросить здесь тех, кто не посещает ХэшКод. Практического применения задачи не вижу, кроме как размять мозг.

Есть игра Пятнашки: поле 4 на 4, 15 плашек с числами от 1 до 15 и можно перемещать плашки по одной на свободное место не вынимая из коробки. Известно, что половина расстановок не имеет решения - на это сейчас особо не обращаем внимания. Исходная задача: определить максимальное количество ходов, необходимое для решения головоломки.

Наиболее логичное решение - обход в ширину всего дерева вариантов расстановок плашек. Но дерево очень большое, поэтому хочется научиться эффективно хранить множество уже пройденных расстановок и работать с ним в процессе обхода дерева. А для того, чтобы этого достичь, надо решить вспомогательную задачу: научиться нумеровать расстановки так, чтобы расстановки, получаемые друг из друга движением одной плашки, находились как можно ближе. Либо доказать, что это невозможно.

Немного подробней. Всего возможных расстановок 16!, т.е. около 20.9 триллиона. Занумеровать их проблем нет. И даже нет проблем отбросить половину, недостижимую из исходной расстановки 1, 2, …, 15, пусто. Но даже если завести по битику на каждое состояние – чтобы хранить, встречалась ли расстановка, потребуется 1.3 ТБ памяти. Даже если бы у меня было столько места на диске, я думаю, алгоритм работал бы смертельно медленно из-за того, что по мере обхода дерева расстановок в ширину доступ к диску получается хаотичный.

Идеальный алгоритм кодирования сопоставил бы расстановке-решению номер 1, двум вариантам, получаемым из него - 2 и 3, вариантам, получаемым из них - 4, 5, 6, 7 и т.д.

За базовый алгоритм нумерации расстановок я брал примерно следующий. Берём число на левой верхней плашке, умножаем на 15. Помечаем, что число на этой плашке встретилось. Теперь берём следую плашку и находим номер числа на ней среди всех чисел, которые ещё не встречались. Прибавляем к предыдущему произведению и умножаем на 14. И т.д. Если встречаем пустое место, то ничего не прибавляем.

Некоторого улучшения удавалось добиться кодированием плашек в другой последовательности. Например, смотрим на четверть, в которой находится пустое место. Сначала кодируем числа на плашках в четверти, находящейся от неё по диагонали, потом – в двух соседних и наконец – собственно в ней. При такой нумерации, если пустая клетка остаётся в одной четверти, то и коды расстановок находятся в пределах 4*3*2 значений. Если переходим в соседнюю четверть, то переносимся в совершенно другой отрезок кодов, но всё-таки, старшие "разряды" в основном сохраняются. Т.е. если в четвертях 1 и 4 (нумерация по часовой стрелке) расположение плашек одинаковое, то переход пустого места из 3-й во 2-ю четверть всегда сохраняет первые четыре значения, по которым строится код (они будут из 4-й четверти). Тем не менее, за два хода можно перейти в противоположную четверть и код будет, грубо говоря, произвольный.

Кому интересно, ещё есть моя же давнишняя публикация на эту тему: Исследование решения игры "пятнашки". Там есть результаты для поля 4 на 3. Аналогичный вопрос на ХэшКод: Обход всех расстановок в Пятнашках.

задан 6 Дек '13 22:32

10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×30

задан
6 Дек '13 22:32

показан
280 раз

обновлен
6 Дек '13 22:32

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru