Пентамино (игра)

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

Виды и количество фигур

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

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

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

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

  

Укладка прямоугольников

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

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

Для прямоугольника 5×12 существует 1010 решений, 4×15 — 368 решений, 3×20 — всего 2 решения.

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

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

Компьютерные игры

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

Примечания

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. ↑ (англ.)Dana S. Scott (1958). "Programming a combinatorial puzzle". Technical Report No. 1, Department of Electrical Engineering, Princeton University.
3. ↑ (англ.) Donald E. Knuth. "Dancing links" (Postscript, 1.6 мегабайт). Включает краткое содержание статей Скотта и Флетчера.

См. также

• Домино
• Тетрамино
• Тетрис
• Замощение

Ссылки

Клуб любителей пентамино — можно прочесть правила, скачать компьютерную версию игры