Существует хорошо известный метод, использующий шаги (1) теста Кнута или аналогичного шаффла (2) на валидность (3), при необходимости сделайте еще один обмен.Это составляет 3 отдельных алгоритма, и (из-за шага 3) не создает всех возможных разрешимых головоломок с точно равной вероятностью.
Я думаю, что ваш вывод здесь ошибочен.Вот трехэтапный метод:
- Перемешать сетку в обычном режиме.
- Проверьте, разрешима ли сетка.
- Если сетка не разрешима, поменяйте местамиплитка с надписью 1 с плиткой с надписью 2.
Прежде всего, существует биекция между разрешимыми сетками и неразрешимыми, полученными путем перестановки плиток 1 и 2. Ясно, что перемешивание в шаге (1) создает все сетки с равной вероятностью, но только половина из них разрешима.Поэтому, если мы применим биекцию ко всем неразрешимым сеткам, то у нас останется равномерное распределение по разрешимым сеткам.(Есть ровно 2 способа «закончить» с любой данной разрешимой сеткой: либо перевести сетку в это состояние, либо перевести сетку в ее уникальное соответствующее неразрешимое состояние. Очевидно, что вероятность этого одинакова для каждой решаемой сетки.)
Доказательство правильности
Из статьи Википедии о 15 головоломках :
Инвариант - это четность перестановкивсе 16 квадратов плюс соотношение расстояния такси (количество строк плюс количество столбцов) пустого квадрата от нижнего правого угла.Это инвариант, потому что каждое движение изменяет как четность перестановки, так и четность расстояния такси.В частности, если пустой квадрат находится в правом нижнем углу, тогда головоломка разрешима тогда и только тогда, когда перестановка оставшихся частей является четной.
Из статьи Википедии о четностиперестановка :
Четная перестановка может быть получена как композиция четного числа и только четного числа обменов (называемых транспозициями) двух элементов, в то время как может быть получена нечетная перестановка(только) нечетным числом транспозиций.
Следовательно, замена (транспонирование) любых двух пронумерованных тайлов (не пустого квадрата) изменит четность перестановки (мы добавили одну транспозицию).Однако четность расстояния такси для пустого квадрата не изменяется (поскольку пустой квадрат не двигался).
Следовательно, такая операция изменит разрешимость головоломки.Другими словами, применение этой операции (например, перестановка плиток с метками 1 и 2) всегда превращает неразрешимую головоломку в разрешимую и наоборот.(Эта операция также является биекцией, потому что она обратима.)
Доказательство того, что требования (b) и (c) не могут быть выполнены одновременно
Рассмотрим начальную сетку 2x2:
1 2
3 _
и сетка "цели":
_ 3
2 1
Можем ли мы перейти от первой сетки ко второй сетке, используя не более 4 свопов (требование (b)) и сохраняя сеткуразрешима после каждого свопа (требование (c))?
Во-первых, обратите внимание, что единственный допустимый своп, удовлетворяющий требованию (c), - это перемещение пространства _ с соседней плиткой (не диагональной плиткой).По симметрии мы можем просто перемещать пространство по часовой стрелке без потери общности.Выполнение любого обмена counter по часовой стрелке бесполезно, так как оно отменяет предыдущий обмен по часовой стрелке.
Таким образом, мы неоднократно меняем пространство с соседней плиткой по часовой стрелке, пока не получим желаемую сетку,Это занимает 6 обменов.Поскольку 6> 4, требование (b) не может быть выполнено при выполнении требования (c).