Пентамино́ (от др.-греч. πέντα пять, и домино) — полимино из пяти одинаковых квадратов, то есть плоские фигуры, каждая из которых состоит из пяти одинаковых квадратов, соединённых между собой сторонами («ходом ладьи»). Этим же словом иногда называют головоломку, в которой такие фигуры требуется укладывать в прямоугольник или другие формы.
Самая распространённая задача о пентамино — сложить из всех фигурок, без перекрытий и зазоров, прямоугольник.
Поскольку каждая из 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]. На современном компьютере подобные головоломки решаются за считанные секунды.
Сделать развивающюю игрушку для ребенка свомими руками из бумаги не сложно самому.
A pentomino is a polyomino composed of five (Ancient Greek πέντε / pénte) congruent squares, connected along their edges (which sometimes is said to be an orthogonal connection).
There are 12 different free pentominoes, often named after the letters of the Latin alphabet that they vaguely resemble. Ordinarily, the pentomino obtained by reflection or rotation of a pentomino does not count as a different pentomino.
The F, L, N, P, Y, and Z pentominoes are chiral in two dimensions; adding their reflections (F', J, N', Q, Y', S) brings the number of one-sided pentominoes to 18. The others, lettered I, T, U, V, W, and X, are equivalent to some rotation of their mirror images. This matters in some computer games, where mirror image moves are not allowed, such as Tetris-clones and Rampart.
Each of the twelve pentominoes can be tiled to fill the plane. In addition, each chiral pentomino can be tiled without using its reflection.
A standard pentomino puzzle is to tile a rectangular box with the pentominoes, i.e. cover it without overlap and without gaps. Each of the 12 pentominoes has an area of 5 unit squares, so the box must have an area of 60 units. Possible sizes are 6×10, 5×12, 4×15 and 3×20. The avid puzzler can probably solve these problems by hand within a few hours. A more challenging task, typically requiring a computer search, is to count the total number of solutions in each case.
The 6×10 case was first solved in 1960 by Colin Brian and Jenifer Haselgrove.[1] There are exactly 2339 solutions, excluding trivial variations obtained by rotation and reflection of the whole rectangle, but including rotation and reflection of a subset of pentominoes (sometimes this is possible and provides in a simple way an additional solution; e.g., with the 3×20 solution shown, the other one is obtained by rotating a set of seven pentominoes. (Leave the U, X, P, I and V as they are and rotate the middle section, as a whole, around.))
The 5×12 box has 1010 solutions, the 4×15 box has 368 solutions, and the 3×20 box has just 2 solutions (one is shown in the figure and the other one explained in the text.)
A somewhat easier (more symmetrical) puzzle, the 8×8 rectangle with a 2×2 hole in the center, was solved by Dana Scott as far back as 1958[2]. There are 65 solutions. Scott's algorithm was one of the first applications of a backtracking computer program. Variations of this puzzle allow the four holes to be placed in any position. One of the external links uses this rule. Most such patterns are solvable, with the exceptions of placing each pair of holes near two corners of the board in such a way that both corners could only be fitted by a P-pentomino, or forcing a T-pentomino or U-pentomino in a corner such that another hole is created.
from http wikipedia.org
Самая распространённая задача о пентамино — сложить из всех фигурок, без перекрытий и зазоров, прямоугольник.
Поскольку каждая из 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]. На современном компьютере подобные головоломки решаются за считанные секунды.
Сделать развивающюю игрушку для ребенка свомими руками из бумаги не сложно самому.
A pentomino is a polyomino composed of five (Ancient Greek πέντε / pénte) congruent squares, connected along their edges (which sometimes is said to be an orthogonal connection).
There are 12 different free pentominoes, often named after the letters of the Latin alphabet that they vaguely resemble. Ordinarily, the pentomino obtained by reflection or rotation of a pentomino does not count as a different pentomino.
The F, L, N, P, Y, and Z pentominoes are chiral in two dimensions; adding their reflections (F', J, N', Q, Y', S) brings the number of one-sided pentominoes to 18. The others, lettered I, T, U, V, W, and X, are equivalent to some rotation of their mirror images. This matters in some computer games, where mirror image moves are not allowed, such as Tetris-clones and Rampart.
Each of the twelve pentominoes can be tiled to fill the plane. In addition, each chiral pentomino can be tiled without using its reflection.
A standard pentomino puzzle is to tile a rectangular box with the pentominoes, i.e. cover it without overlap and without gaps. Each of the 12 pentominoes has an area of 5 unit squares, so the box must have an area of 60 units. Possible sizes are 6×10, 5×12, 4×15 and 3×20. The avid puzzler can probably solve these problems by hand within a few hours. A more challenging task, typically requiring a computer search, is to count the total number of solutions in each case.
The 6×10 case was first solved in 1960 by Colin Brian and Jenifer Haselgrove.[1] There are exactly 2339 solutions, excluding trivial variations obtained by rotation and reflection of the whole rectangle, but including rotation and reflection of a subset of pentominoes (sometimes this is possible and provides in a simple way an additional solution; e.g., with the 3×20 solution shown, the other one is obtained by rotating a set of seven pentominoes. (Leave the U, X, P, I and V as they are and rotate the middle section, as a whole, around.))
The 5×12 box has 1010 solutions, the 4×15 box has 368 solutions, and the 3×20 box has just 2 solutions (one is shown in the figure and the other one explained in the text.)
A somewhat easier (more symmetrical) puzzle, the 8×8 rectangle with a 2×2 hole in the center, was solved by Dana Scott as far back as 1958[2]. There are 65 solutions. Scott's algorithm was one of the first applications of a backtracking computer program. Variations of this puzzle allow the four holes to be placed in any position. One of the external links uses this rule. Most such patterns are solvable, with the exceptions of placing each pair of holes near two corners of the board in such a way that both corners could only be fitted by a P-pentomino, or forcing a T-pentomino or U-pentomino in a corner such that another hole is created.
from http wikipedia.org
No comments:
Post a Comment