Игра «Пятнашки» · Шаг 3 из 5
Решаема ли раскладка
В 1879 году Сэм Лойд пообещал тысячу долларов тому, кто соберёт пятнашки, где переставлены 14 и 15. Денег он не отдал: такую раскладку собрать нельзя. Нельзя собрать ровно половину всех раскладок, и узнаётся это без единого хода — по чётности. Оболочка перемешивает плитки наугад и должна знать, не выпала ли такая.
Что сделать
Узнайте по чётности беспорядков и месту пустой клетки, можно ли собрать эту раскладку.
Что приходит
pole— поле списком рядов,0— пустая клетка
Что вернуть
True, если раскладку можно собрать ходами, иначе False.
Допишите функцию reshaema в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
В игре
Игра зовёт reshaema в начале каждой партии, перемешав плитки наугад. False — оболочка меняет местами две плитки, и раскладка становится решаемой. Решите шаг — и нерешаемых партий больше не будет.
Без этого шага: новая раскладка может оказаться нерешаемой — так выпадает каждая вторая.
«Восьмёрка» 3×3, где переставлены 7 и 8: [[1, 2, 3], [4, 5, 6], [8, 7, 0]]. Без пустой клетки по порядку читается 1 2 3 4 5 6 8 7 — один беспорядок, пара (8, 7). Ширина нечётная, беспорядков нечётное число — собрать нельзя, ответ False.
reshaema([[1, 2, 3], [4, 5, 6], [8, 7, 0]])
False
Прочитайте плитки по рядам сверху вниз, в ряду — слева направо, пропустив пустую клетку. Беспорядок — пара плиток, где большая стоит раньше меньшей (не обязательно рядом).
- Ширина поля нечётная (3×3, 5×5) — раскладка решаема, если беспорядков чётное число.
- Ширина чётная (4×4, 3×4) — к числу беспорядков прибавьте номер ряда пустой клетки, считая снизу и с единицы: нижний ряд — 1. Раскладка решаема, если сумма нечётная.
Ширина — длина ряда, высота может быть любой. Поле не меньше 2×2.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.