Сколько возможных состояний имеет 8-головоломка?

Классическая 8-головоломка принадлежит к семейству скользящих блоков. Моя книга (Искусственный интеллект Современный подход Стюарта Рассела и Петра Норига) говорит, что 8-головоломка имеет 9!/2 возможные состояния. Но ПОЧЕМУ /2? Как вы это узнаете?

Ответы

Ответ 1

9! - общее количество возможных конфигураций головоломки, тогда как 9!/2 - общее количество разрешимых конфигураций. Например, эта конфигурация не имеет решения:

1 2 3
4 5 6
8 7

Подробнее о разрешимости некоторых конфигураций n-головоломки в этой статье Wikipedia , или, как указано в @MathWorld, приведенном в этом MathWorld объяснение.

Один из возможных способов узнать, что 9!/2 - количество разрешимых конфигураций, - это начать с решаемой головоломки и сгенерировать из нее все возможные действительные, не повторяющиеся движения.