Popov AcademyПятнашки и инварианты
Пустое место
помогает навести порядок.
Соберите числа по порядку, оставив пустую клетку внизу справа. Нажимайте на соседнюю плитку или используйте стрелки, когда поле в фокусе.
Эта перестановка получена допустимыми ходами и имеет решение.
Почему одни перестановки недостижимы?
В варианте 3×3 выпишите числа построчно, пропустив пустую клетку. Назовём инверсией пару, в которой большее число стоит раньше меньшего. У правильной доски инверсий ноль.
Горизонтальный ход порядок чисел не меняет. При вертикальном ходе плитка перепрыгивает в записи через две другие: число инверсий меняется на −2, 0 или +2. Значит, чётность сохраняется. Если в готовой доске обменять только 1 и 2, появится одна инверсия: вернуться к нулю невозможно.
У поля 4×4 вертикальный ход проходит через три числа, зато меняет и чётность номера строки пустой клетки, считая снизу. Сохраняется чётность суммы «число инверсий + строка пустой снизу». У собранной доски она нечётна. Обмен только 1 и 2 делает её чётной, поэтому опять создаёт невозможный вариант.
Как собирать обычный вариант: закрепляйте верхнюю строку, затем левый столбец, не разрушая собранное. Последние две плитки строки удобно заводить вместе через соседние свободные клетки. Возвращайтесь на шаг назад кнопкой отмены, если ход разрушил нужную пару.