почему-неразрешима-15-тизвенная-головоломка

Почему 15-тизвенная головоломка неразрешима

Головоломка «15», также известная как «цифровая задача 15», не является неразрешимой, а скорее целевое состояние недостижимо из некоторых начальных состояний.

Описание игры

«15-тизвенная головоломка» — это игра со слайдерами, где игровое поле представляет собой 4×4 сетку с 15 слайдерами, пронумерованными от 1 до 15, и пустым местом. Цель игрока — переместить слайдеры в порядок слева направо, сверху вниз, в результате чего получится упорядоченная последовательность от 1 до 15, а пустое место окажется в правом нижнем углу.

Неразрешимые случаи

Состояние нельзя законно перевести в целевое состояние, если и только если количество пар чисел в обратном порядке в начальном состоянии нечетное. Пара в обратном порядке — это пара чисел в последовательности, которые называются парой в обратном порядке, если их переднее и заднее положения находятся в обратном порядке величины, т. е. число спереди больше числа сзади. Например, в последовательности 2, 4, 3, 1 обратные пары — это (2, 1), (4, 3), (4, 1), (3, 1), всего четыре.

Доказательство.

Движения слайдеров на доске можно рассматривать как преобразование расположения этих слайдеров. Каждый раз, когда слайдер перемещается, фактически происходит обмен местами пустого места и соседнего слайдера. А эта операция обмена изменяет чётность инверсии расположения. Инверсия целевого состояния равна 0, что является чётным числом. Если инверсия начального состояния нечётная, то независимо от того, сколько раз происходит перемещение, её инверсия не может быть изменена на чётную, и целевое состояние не может быть достигнуто.

Если вам нравится играть в Puzzles ball, это абсолютно бесплатно, увлекательно и легко.