Editing Pentomino (section)

=== Tiling puzzle (2D) ===
[[File:Pentomino Puzzle Solutions.svg|thumb|right|upright=2|Example tilings]]

A standard '''pentomino puzzle''' is to [[tessellation|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 6×10 case was first solved in 1960 by married couple [[C. Brian Haselgrove|Colin Brian Haselgrove]] and [[Jenifer Haselgrove]].<ref>{{cite journal |author=C. B. Haselgrove |author2=Jenifer Haselgrove |date=October 1960 |title=A Computer Program for Pentominoes |journal=[[Eureka (University of Cambridge magazine)|Eureka]] |volume=23 |pages=16–18|url=https://www.archim.org.uk/eureka/archive/Eureka-23.pdf}}</ref> There are exactly 2,339 solutions, excluding trivial variations obtained by rotation and reflection of the whole rectangle but including rotation and reflection of a subset of pentominoes (which sometimes provides an additional solution in a simple way). 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 can be obtained from the solution shown by rotating, as a whole, the block consisting of the L, N, F, T, W, Y, and Z pentominoes).

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.<ref>Dana S. Scott (1958). "Programming a combinatorial puzzle". Technical Report No. 1, Department of Electrical Engineering, Princeton University.</ref> 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.

Efficient algorithms have been described to solve such problems, for instance by [[Donald Knuth]].<ref>Donald E. Knuth. [https://arxiv.org/abs/cs/0011047 "Dancing links"]. Includes a summary of Scott's and Fletcher's articles.</ref> Running on modern [[personal computer|hardware]], these pentomino puzzles can now be solved in mere seconds.

[[File:Pentomino unsolvable.svg|thumb|left|upright=1.5|Unsolvable patterns]]
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.

The pentomino set is the only free [[polyomino]] set that can be packed into a rectangle, with the exception of the trivial [[monomino]] and [[domino (mathematics)|domino]] sets, each of which consists only of a single rectangle.