Как перечислить все состояния в 8-головоломке?

Я решаю восьмерку. Это проблема, которая выглядит так:

введите описание изображения здесь

Изображение предоставлено: https://ece.uwaterloo.ca/~dwharder/aads/Algorithms/N_puzzles/ (вы также можете увидеть там более подробное описание 8-головоломки). Пользователь может переместить квадрат, примыкающий к заготовке, в заготовку. Задача - восстановить расположение как показано на картинке, начиная с некоторой произвольной расстановки.

Теперь, конечно, состояние можно описать как перестановку 9 цифр. В случае показанного изображения перестановка следующая:

1 2 3 4 5 6 7 8 0

Однако не все перестановки достижимы из показанной конфигурации. Поэтому у меня есть следующие вопросы.

  1. Какое количество перестановок можно получить из показанной начальной конфигурации, вставив плитки в заготовку?

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


artificial-intelligence algorithm planning sliding-tile-puzzle
person ziutek    schedule 29.10.2013    source источник
comment
Разве у головоломки 8 нет свойства, что ровно половина (всех) перестановок может быть достигнута из любого начального состояния?   -  person user2864740    schedule 29.10.2013
comment
user2864740, не знаю. Если вы знаете место, где это объясняется, поделитесь, пожалуйста.   -  person ziutek    schedule 29.10.2013
comment
Прошло некоторое время, но мне показалось, что я помню, что существуют два различных решаемых и неразрешимых набора состояний. Возможно, stackoverflow.com/a/11923585/2864740 содержит соответствующую информацию.   -  person user2864740    schedule 29.10.2013
comment
@ user2864740 - Это правильно. Существует ровно два класса эквивалентности достижимых конфигураций. Методы, использованные для доказательства этого факта для головоломки из 15 (см. Здесь), в равной степени применимы к 8-пазл. (Фактически, существуют доказательства для произвольных головоломок размером m x n.)   -  person Ted Hopp    schedule 29.10.2013
comment
Google - ваш друг: Полное решение восьмерки , среди прочего.   -  person Jim Mischel    schedule 29.10.2013

Ответы (2)


arrow_upward
2
arrow_downward

  1. 181440.
  2. Вставьте их в массив и отсортируйте, например лексикографически. Тогда преобразование целых чисел в перестановки - это O (1), а обратное - O (log n).
person j_random_hacker    schedule 29.10.2013

arrow_upward
1
arrow_downward

Что ж, если вы просто хотите перечислить различные возможные состояния, которые могут быть достигнуты, вы можете просто выполнить поиск в глубину из вашего начального состояния. Очень возможно сгенерировать действительные следующие состояния с учетом текущего состояния, например: перемещение плитки вниз в пустое пространство аналогично замене плитки 0 на плитку 3 перед ней в перестановке, если она есть. Таким образом, вы просто выполняете dfs и сохраняете хэш-набор всех перестановок в качестве посещенного массива, который может быть сохранен как целые числа или строки. их всего 9! возможных состояний, которое составляет всего 362880. Если вам нужно отображение 1-1 из набора целых чисел, просто сделайте хэш-набор хеш-таблицей, и каждый раз, когда вы обнаружите новое состояние, просто добавляйте его в хеш-таблицу по следующему индексу. Вы также можете найти кратчайшее решение, сначала сделав сначала вширь, а затем просто сломав, когда найдете решенное состояние.

person Alex    schedule 29.10.2013