как программно создать правильную загадку 15 в коде

Question

Я построил 15 головоломок в JS, но мое поколение случайных головоломок создает экземпляры неразрешимой головоломки. Это может быть потому, что я не руководитель отдела компьютерных наук, но я не уверен, как работать с такими вещами, как вычисление числа инверсий в перестановке в коде. Мне интересно, как написать свой код, чтобы я мог проверить, что любое заданное начальное состояние моей головоломки разрешимо. Я видел еще 15 головоломок в опубликованных приложениях, которые неразрешимы, так что, похоже, я не единственный, у кого есть проблема.

Я видел этот пост, но он останавливается на уровне CS, и я ищу реализацию кода, которая помогла бы мне понять это немного лучше: 15 Эвристическая головоломка

Я использую JS, но любая помощь и объяснение на каком бы языке ни были полезны.

Answer 1

Алгоритм разрешимости основан на четности инверсии и объяснен в 15 Puzzle - Wolfram Math World Его не должно быть слишком сложно преобразовать в код. IIRC, поменяв местами два смежных квадрата в неразрешимой начальной точке, делает ее разрешимой, но вам нужно будет это подтвердить.

Обратите внимание, что это точный алгоритм, определяющий, может ли головоломка быть решена, а не эвристика для определения последовательности шагов в решении.

Answer 2

То, к чему я прибегал в комментарии, но не был уверен, что это правильный подход:

1. Начните с "правильной" последовательности из 15 цифр /board
2. Генерирование случайного числа "пропусков", которое вы можете применить к доске
3. Создание N списка допустимых пропусков на основе случайного числа, которое вы сгенерировали
4. Теперь у вас должна быть действующая игра.

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