Я тут как раз пятнашку перебирал, наткнулся на классный трюк с четностью – сразу о тебе вспомнил. Ты, кстати, когда-нибудь доказывала, что решаемых положений только половина?

Вот в чем суть: представь себе 16 позиций, расположенных в порядке, как в строке, включая пустое место. Идеальное состояние – это когда все плитки находятся на своих местах, в том порядке, в котором они были изначально. Каждое допустимое действие – это смена пустого места с соседней плиткой, то есть, по сути, это перестановка двух элементов из этих 16. Каждая такая перестановка – нечетная перестановка, значит, четность всей шестнадцатьки меняется с каждым ходом. Теперь, чтобы определить четность 15 плиток, мы игнорируем пустое место. Перестановка этих 15 плиток – это просто ограничение всей шестнадцатьки до этих 15 позиций. Когда мы убираем пустое место, его положение имеет значение только тем, слева оно находится или справа от плитки, если смотреть на них в линейном порядке. Каждый горизонтальный ход меняет положение пустого места на один шаг влево или вправо, обменивая его с одной плиткой – это нечетное изменение. Каждый вертикальный ход перемещает пустое место на всю строку (15 позиций), обменивая его с 15 плитками – это тоже нечетное количество перестановок, опять же, нечетное изменение. Таким образом, каждый допустимый ход меняет четность перестановки 15 плиток. Поскольку в конечном состоянии четность – четная (инверсий нет), то решаемые состояния – это только те, у которых четность инверсий плиток плюс пустое место в правом нижнем углу. Короче говоря, каждый ход меняет четность, поэтому ты можешь попасть только в те позиции, четность которых совпадает с четностью начальной.

Ты права, вертикальное перемещение – это просто одна перестановка в сетке, но в линейном списке это равносильно нечетному числу перестановок, так что парность все равно меняется. Я просто набросал идею, не все детали продумал.