Пентамино

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Сравнение систем именования пентамино. Первая схема (вверху) была предложена Соломоном Голомбом и используется в этой статье. Вторая схема (внизу) предложена Джоном Конвеем и используется, в частности, при описании конфигураций «Жизни», имеющих форму пентамино.

Пентамино́ (от др.-греч. πέντα пять, и домино) — пятиклеточные полимино, то есть плоские фигуры, каждая из которых состоит из пяти одинаковых квадратов, соединённых между собой сторонами («ходом ладьи»). Этим же словом иногда называют головоломку, в которой такие фигуры требуется укладывать в прямоугольник или другие формы.

Виды и количество фигур[править | править вики-текст]

Всего существуют 12 различных фигур (элементов) пентамино, обозначаемых латинскими буквами, форму которых они напоминают (см. рисунок). Считается, что зеркальная симметрия и вращательная симметрия не создают новых фигур. Но если считать и зеркально отражённые фигуры, то их число увеличится до 18. Такое различие имеет значение, например, в компьютерной игре, вариации «Тетриса»  — «Пентиксе».

Если рассматривать вращения фигур на 90°, то существуют следующие категории симметрии:

  • L, N, P, F и Y могут быть ориентированы 8 способами каждая: 4 поворотами и ещё 4 зеркальными отображениями.
  • Z может быть ориентирована 4 способами: 2 — поворотами, 2 — зеркальными отображениями.
  • T, V, U и W могут быть ориентированы поворотами 4 способами каждая.
  • I может быть ориентирована поворотами 2 способами.
  • X может быть ориентирована единственным способом.

Отсюда число фиксированных пентамино равно 5 × 8 + (1 + 4) × 4 + 2 + 1 = 63.

Например, вот восемь возможных способов ориентации пентамино L, F, P, N и Y:

L-pentomino Symmetry.svgF-pentomino Symmetry.svgP-pentomino Symmetry.svgN-pentomino Symmetry.svgY-pentomino Symmetry.svg

Составление фигур из пентамино[править | править вики-текст]

Укладка прямоугольников[править | править вики-текст]

Прямоугольники, составленные из пентамино

Самая распространённая задача в пентамино — сложить из всех фигурок, без перекрытий и зазоров, прямоугольник. Поскольку каждая из 12 фигур включает в себя 5 квадратов, то прямоугольник должен быть площадью 60 единичных квадратов. Возможны прямоугольники 6×10, 5×12, 4×15 и 3×20. Каждую из этих головоломок можно решить вручную, но более сложной задачей является подсчёт общего числа возможных решений в каждом случае. (Очевидно, прямоугольники 2×30 и 1×60 составить из пентамино невозможно, поскольку многие фигуры в них просто не помещаются по ширине.)

Для случая 6×10 эту задачу впервые решил в 1965 году Джон Флетчер [1]. Существует ровно 2339 различных укладок пентамино в прямоугольник 6×10, не считая поворотов и отражений целого прямоугольника, но считая повороты и отражения его частей (иногда внутри прямоугольника образуется симметричная комбинация фигур, поворачивая которую можно получить дополнительные решения; для прямоугольника 3×20, приведённого на рисунке, второе решение можно получить поворотом блока из 7 фигур, или, иначе говоря, если поменять местами четыре фигуры, крайние слева, и одну крайнюю справа).

Для прямоугольника 5×12 существует 1010 решений, 4×15 — 368 решений, 3×20 — всего 2 решения (отличающихся вышеописанным поворотом). В частности, существует 16 способов сложить два прямоугольника 5×6, из которых можно составить как прямоугольник 6×10, так и 5×12.

18 односторонних пентамино

Укладка прямоугольников из односторонних пентамино[править | править вики-текст]

Если дополнить набор пентамино зеркальными копиями фигур, не совпадающих со своими отражениями (F, L, P, N, Y и Z), то из полного набора в 18 односторонних пентамино можно сложить прямоугольники площадью 90 единичных квадратов (при этом фигуры не разрешается переворачивать). Задача о составлении прямоугольника 3×30 имеет 46 решений, 5×18 — более 600 тыс. решений, 6×15 — более 2 млн. решений и 9×10 — более 10 млн. решений[2]

Укладка фигур с отверстиями[править | править вики-текст]

В какой-то степени более простую (более симметричную) задачу, для квадрата 8×8 с отверстием в центре 2×2, решил еще в 1958 году Дана Скотт[3] (аспирант-математик Принстона). Для этого случая существует 65 решений. Алгоритм Скотта был одним из первых применений компьютерной программы поиска с возвратом.

Квадраты с отверстиями, составленные из пентамино
Квадраты с отверстиями, которые нельзя составить из пентамино

Другой вариант этой головоломки — выкладывание квадрата 8×8 с 4 отверстиями в произвольно заданных местах. Большинство таких задач имеют решение. Исключением являются случаи с размещением двух пар отверстий вблизи двух углов доски так, чтобы в каждый угол можно было поместить только P-пентамино, или всех четырёх отверстий вблизи одного угла так, что при любом возможном заполнении угловой клетки (с помощью U- или T-пентамино) от доски отсекается ещё одна клетка (см. рисунок).

Для решения этих задач эффективные алгоритмы описал, например, Дональд Кнут[4]. На современном компьютере подобные головоломки решаются за считанные секунды.

Задача об утроении фигур пентамино[править | править вики-текст]

Triplication of pentaminoes.png

Эта задача была предложена профессором Калифорнийского университета Р.М.Робинсоном. Выбрав одну из 12 фигур пентамино, необходимо построить из каких-либо 9 из 11 оставшихся пентамино фигуру, подобную выбранной, но в 3 раза бо́льшей длины и ширины. Решение существует для любого из 12 пентамино, причём не единственное (от 15 решений для Х до 497 для Р).[2] Существует вариант этой задачи, в котором для построения утроенной фигуры разрешается использовать также и саму исходную фигуру. В этом случае число решений от 20 для Х до 9144 для Р-пентамино.[5]

Представленное на рисунке решение[6], найденное А.ван де Ветерингом, обладает интересным свойством: каждое пентамино используется для утроения девяти из остальных, по одному разу в каждой. Таким образом, из 9 комплектов исходных фигур пентамино можно одновременно сложить все 12 утроенных пентамино.

Настольная игра[править | править вики-текст]

Пентамино может использоваться также как настольная игра для двух игроков.[7] Для игры необходима шахматная доска 8×8 и набор фигур пентамино, клетки которых имеют одинаковый размер с клетками доски. В начале игры доска пуста. Игроки поочерёдно выставляют на доску по одной фигуре, закрывая 5 свободных клеток доски. Все выставленные фигуры остаются на месте до конца партии (не снимаются с доски и не передвигаются). Проигравшим считается игрок, который первым не сможет сделать хода (либо из-за того, что ни одна из оставшихся фигур не умещается на свободных участках доски, либо потому, что все 12 фигур уже выставлены на доску).

Анализ игры достаточно сложен (так, в начале имеется даже больше возможных первых ходов, чем в шахматах). Голомб предложил следующую стратегию: стремиться разбить свободное место на доске на два равновеликих участка (и помешать сопернику сделать это). После этого на каждый ход соперника на одном из участков следует отвечать ходом на другом.

Партия в игре пентамино для двух игроков

Пример партии в пентамино показан на рисунке. Нумерация ходов сквозная (нечётные номера ходов принадлежат первому игроку, чётные — второму). Первоначально игроки делают ходы в центре доски (ходы 1–3), не позволяя друг другу разбить доску на равновеликие участки. Но затем второй игрок делает неудачный ход (4), позволяющий сопернику разбить свободное место на два участка по 16 клеток (ход 5). (В этом примере свободные участки не только равны по площади, но и совпадают по форме — симметричны относительно диагонали доски, но для стратегии это, разумеется, не обязательно.) Далее на ход второго игрока (6) на одном из этих участков первый игрок отвечает ходом на другом (7) и выигрывает. Хотя на доске ещё есть три свободных участка в пять и более клеток, но все подходящие фигуры (I, P, U) уже использованы.

Варианты настольной игры[править | править вики-текст]

Пентамино с заранее выбранными фигурами[править | править вики-текст]

В этом варианте игры игроки сначала по очереди выбирают по одной фигуре, пока все фигуры не будут распределены между ними. Далее игра проходит по правилам обычного пентамино, с той разницей, что каждому из игроков разрешается ходить только теми фигурами, которые он выбрал. Взявший последнюю фигуру делает первый ход.

Стратегия этого варианта игры, предложенная Голомбом, существенно отличается от стратегии обычного пентамино. Вместо того, чтобы разбить доску на равновеликие участки, игрок стремится создать на доске участки, которые можно заполнить лишь его фигурами, но не фигурами соперника. (Голомб называет такие участки «убежищами».)

Пример партии в пентамино с заранее выбранными фигурами

Пример партии в пентамино с заранее выбранными фигурами показан на рисунке. Фигуры, выбранные первым и вторым игроками, перечислены слева и справа от доски соответственно. Зачёркнутая буква обозначает, что фигура использована для хода. Сначала игроки избавляются от самых «неудобных» фигур X и W (ходы 1 и 2). Затем первый игрок создаёт «убежище» для фигуры Y (ход 3), второй — для фигур U и P (ходы 4 и 6). В конце партии (ходы 8—10) происходит заполнение этих «убежищ» и партия заканчивается победой второго игрока — у первого остаётся Т-образное пентамино, для которого на оставшейся части доски нет подходящего места.

Другие варианты[править | править вики-текст]

  • «Карточное пентамино» — вариант игры с привнесением случайных событий. Фигуры пентамино (или их буквенные обозначения) рисуют на карточках, которые тасуют и раздают игрокам. Игроки выбирают фигуры в соответствии с розданными им карточками. Далее игра идёт по правилам пентамино с заранее выбранными фигурами.
  • Пентамино для четырёх игроков. Четыре игрока, сидящие по четырём сторонам доски, играют двое на двое (игроки, сидящие друг напротив друга, образуют команду). Проигравшей считается команда, игрок которой первым не сможет сделать хода. В эту игру можно играть по любому из трёх вышеописанных вариантов — обычному, с заранее выбранными фигурами или «карточному».
  • «Кто-кого?» В игре участвует от двух до четырёх игроков, но каждый из них играет только за себя. Победителем считается сделавший последний ход, ему засчитывается 10 очков. Игрок, который должен ходить после победителя (т.е. первым не сможет сделать хода) получает 0 очков, а все остальные игроки — по 5 очков. Может быть сыграно несколько партий, набранные в них очки суммируются. Игра также может проводиться по любому из трёх вышеописанных вариантов правил.

Компьютерные игры[править | править вики-текст]

С конца 1980-х годов неоднократно выходили различные компьютерные игры, основанные на пентамино. Наиболее известная — основанная на идее тетриса игра пентикс (Pentix). Один из новейших примеров — игра Dwice, которую разработал в 2006 году изобретатель Тетриса Алексей Пажитнов.

Пентамино в «Жизни» Конвея[править | править вики-текст]

Эволюция R-пентамино

Из всех пентамино самой долгой эволюцией обладает R-пентамино. Эволюция этого пентамино становится тривиальной лишь спустя 1103 поколения[8][9]. После 1103 поколений развития R-пентамино популяция состоит из 25 объектов: 8 блоков, 6 планеров, 4 ульев, 4 мигалок, 1 лодки, 1 каравая и 1 корабля[8][10].

Первый из шести планеров образуется спустя 69 поколений эволюции. Он был замечен в 1970 году Ричардом Гаем и стал первым зарегистрированным планером[8][9][10].

Примечания[править | править вики-текст]

  1.  (англ.)John G. Fletcher (1965). "A program to solve the pentomino problem by the recursive use of macros". Communications of the ACM 8, 621–623.
  2. 1 2 Gerard's Polyomino Solution Page
  3.  (англ.)Dana S. Scott (1958). "Programming a combinatorial puzzle". Technical Report No. 1, Department of Electrical Engineering, Princeton University.
  4.  (англ.) Donald E. Knuth. "Dancing links" (Postscript, 1.6 мегабайт). Включает краткое содержание статей Скотта и Флетчера.
  5. The Poly Pages
  6. http://www.recmath.org/PolyPages/PolyPages/Pictures1/AvdW.gif
  7. Гарднер М. Математические новеллы. — Пер. с англ. Ю. А. Данилова. — М.: Мир, 1974. — 456 с., илл. — Глава 7. Пентамино и полиомино: пять игр и серия задач. — с.81—95
  8. 1 2 3 Клумова И. Н. Игра «Жизнь» // Квант. — 1974. — № 9. — С. 26—30.
  9. 1 2 R-pentomino. ConwayLife.com. Архивировано из первоисточника 17 августа 2013.
  10. 1 2 Game of Life :: Walks of Life :: Interesting Patterns. Архивировано из первоисточника 17 августа 2013.

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]