Mrs Perkins's Quilt

Mrs Perkins's Quilt

Mrs Perkins's Quilt Solution

(numbering indicates the different patches, not their sizes)

"For Christmas, Mrs. Potipher Perkins received a very pretty patchwork quilt constructed of 169 square pieces of silk material. The puzzle is to find the smallest number of square portions of which the quilt could be composed and show how they might be joined together. Or, to put it the reverse way, divide the quilt into as few square portions as possible by merely cutting the stitches."

Henry E. Dudeney

Sam Loyd published The Patch Quilt Puzzle. A square quilt made of 169 square patches of the same size is to be divided into the smallest number of square pieces by cutting along lattice lines. The answer, which is unique, is composed of 11 squares with sides 1,1,2,2,2,3,3,4,6,6,7 within a square of 13. It is neither perfect nor simple. Gardner states that this problem first appeared in 1907 in a puzzle magazine edited by Sam Loyd. David Singmaster lists it as first appearing in 1914 in Cyclopedia by Loyd but credits Loyd with publishing Our Puzzle Magazine in 1907 - 08. This puzzle also appeared in a publication by Henry Dudeney as Mrs Perkins's Quilt. Problem 173 in Amusements in Mathematics. 1917

Define a quilt as a square made from smaller integer squares. The order of a quilt is the number of smaller squares. The size is the edge length of the full quilt. It is impossible to dissect the 13×13 square into fewer than 11 squares, so this dissection is optimal. An additional constraint is that the side lengths cannot have a common factor. Any optimal quilt is a Mrs. Perkins's quilt. A primitive quilt is one without any sub-quilts, or is not substantially derived from a smaller quilt. The primitive quilts are not necessarily optimal quilts.

Richard K. Guy, the maintainer of Unsolved Problems in Geometry lists optimal quilts as problem C3. As of January 7, 2003, this web page article from Ed Pegg Jr shows (in bold face) the listing of the lowest known order for a given square of size n. The first value in each bracketed list is the order. The following values are the sizes of quilts that first appear in that order. We reproduce the listing here;

Two obvious sequences can be obtained from this data;

Sequence A089046 ; "Least edge-length of a square dissectable into at least n squares in the Mrs Perkins's quilt problem.", lists the optimal quilts as the lowest known size for a given square of order n.
Sequence A089047 ; "Greatest edge-length of a square dissectable into up to n squares in the Mrs Perkins’s quilt problem.", lists the quilts with the greatest known size for a given square of order n.

Ed Pegg writes; "The above list can be attacked in two ways -- computer programs and hand analysis. Dozens of improvements were discovered by Richard Guy, Lance Gay, and Geoff Morley." Quilt construction techniques have been developed by Ed Pegg, Richard Guy and Lance Gay. Programs to search for quilts have been written by Antony Boucher and Lance Guy. Mathematica code has been written to display quilts by Ed Pegg Jr.

In 2010, Richard Guy suggested to Ed Pegg Jr that they compile all their findings and methods for a paper. Many of the larger optimal quilts were identified by Geoffrey Morley, from publications on squared squares by Duijvestijn. As Duijvestijn and Bouwkamp are no longer with us, Ed Pegg sought assistance from Stuart Anderson, who like Duijvestijn has developed software to extract square tilings from graphs. Stuart wrote some new software for finding squared squares and quilts. After Pegg and Anderson ran the computer programs for a number of months, perfect squares for orders up to 28 and a large portion of order 29 were explored, along with a complete listing of imperfect squared squares up to order 28. A number of new discoveries were made in the compilation process. While order 28 was being compiled, Ed updated the optimal quilts to order 27.

The above listing forms the basis of a Mathematica Demonstration by Ed Pegg Jr and Richard Guy;

Mrs Perkins's Demonstration

Optimal Mrs Perkins's Quilts Demonstration

After including the results from orders 28 and 29 perfect and imperfect squared squares, along with some inclusions from Ed Pegg, Stuart Anderson has updated the list;

In addition to including entries for order 28 and 29, 1099 and 1165 were included in order 27 and 847 was included in order 26.

In March/April 2013 Lorenz Milla and Stuart Anderson enumerated Simple Perfect Squared Squares (SPSSs) and Simple Imperfect Squared Squares (SISSs) with 30 squares (order 30). In January/February James Williams found large numbers (over 15 million) SPSSs in orders from 30 to 44. It is now possible to extend the listing of optimal Mrs Perkins's quilts even further. Here are some results for quilts with 30 squares;

In July-September 2013 Lorenz Milla and Stuart Anderson enumerated Simple Perfect Squared Squares (SPSSs), Compound Perfect Squared Squares (CPSSs) and Simple Imperfect Squared Squares (SISSs) with 31 and 32 squares (order 31,32). Here are some results for quilts with 31 and 32 squares;

Using the results of James Williams, it is possible to find quilts with sizes from 1 all the way up to a size of 92638 (with 44 squares). Every size in between 1 and 92638 is covered. Further down the page there are links to a listing of the Bouwkampcodes, and a postscript file of all 92638 quilts.

Best Known, Not Best Possible

It needs to be stressed that most of the results here are the best known optimal quilts A089046, the majority of them (those past order 18) have not been proven to be the best possible. The rest of the optimals should be considered as conjectures. Conway stated [11]; "G.B.Trustrum and I proved that the answer lies between two constant multiples of log n." [1] [2]

Planar graphs can be used as electrical networks to create square tilings ie, squared rectangles and squared squares. To create quilts, 2-connected planar graph embeddings need to be used, in addition to the 3-connected graphs. These 2-connected graphs are far more numerous than the 3-connected graphs. This limits what is possible using this method. With the large number of graphs, fewer orders can be exhaustively searched. In addition many quilts can only be modelled with planar multi-graphs. A multi-edge represents a contiguous block of same size squares. Multi-edge graphs are even more numerous than the simple 2-connected graphs. Plantri, the graph generator used to produce 2 and 3 connected graphs, only produces simple graphs. However it should be possible to simulate multi-graphs using plantri simple graphs with resistances of n and 1/n for n multi edges between 2 vertices, in a similar manner to Jepsen and Gu's [8] work on rectangles dissected into rectangles, then dissect the rectangles so they become the blocks of same size squares. It may be possible to prove several more orders as best possible using this method.

Recent work by Ed Wynn, and updated OEIS Sequences

A recent (August 2013) paper by Ed Wynn[14] extends the exhaustive generation of all squared square dissections, having relatively prime sides (Mrs Perkins's quilts) up to order 18, using the plantri software with a graph theoretical approach which is different to the electrical network method of BSST/Duijvestijn. The results were cross-checked by generating all dissections of small sizes using Knuth's dancing links algorithm to produce exact cover square dissections. In the paper's appendix, Ed lists values from several sequences in the OEIS with previously known values that have been confirmed in the current work (or, conversely, have been used to check the current work). Also, new (or newly definite) values are shown in italics.

These sequences include the trivial dissection of a square into itself (except where ‘smaller’ is specified, in A018835 and A211302). Sequences A045846 and A221845 have known values beyond those listed here. In particular, A045846 is known for n ≤ 15 – and the values for 10, 11 and 12 (1500957422222, 790347882174804 and 781621363452405930) were used to confirm and extend A224239.

Conjectured OEIS terms for optimal quilts and largest quilts of a given order

Sequence A089046 ; "Least edge-length of a square dissectable into at least n squares in the Mrs Perkins's quilt problem.", lists the optimal quilts as the lowest known size for a given square of order n. It is possible to conjecture additional terms to this sequence and the following one, based on incomplete squared square enumeration, beyond what has been proved by Wynn (conjectured terms are in bold).
1, 2, 2, 2, 3, 3, 4, 5, 6, 8, 10, 14, 18, 24, 30, 40, 54, 71, 92, 121, 155, 210, 266, 360, 476, 642, 833, 1117, 1473, 1967, 2595, 3465, 4534, 5374, 5498, 5591, 6079, 8794, 14151, 18883, 25739, 32797, 49694, 60050

Sequence A089047 ; "Greatest edge-length of a square dissectable into up to n squares in the Mrs Perkins’s quilt problem.", lists the quilts with the greatest known size for a given square of order n. (conjectured terms are in bold).
1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 13, 17, 23, 29, 41, 53, 70, 91, 126, 158, 216, 276, 386, 488, 675, 866, 1179, 1544, 2136, 2739, 3755, 4988, 5976, 7640, 9945, 13102, 17304, 23251, 31516, 40812, 53382, 72016, 91937, 92638

Optimal Mrs Perkins's Quilts 1 - 20

Optimal Mrs Perkins's Quilts

A list of 92638 currently best known quilts, from size 1 to 92638, taken from the tilings on this website is here (21.8M). A zipped postscript file (9.5M) of those quilts is here. There are sometimes many quilts with the same size and order, only one representative was chosen. That being the one with the numerically least Bouwkampcode string. These quilts are a combination of Ed Pegg's optimal listings and the optimal quilts from this site, they are only 'optimal' with respect to the the best known results, and in some cases the best possible for low orders (<= order 18) and small sizes, up to order 44.

The listing [12] compiled by Ed Pegg is also linked. Ed Pegg's listing also includes primitive quilts, a collection of particular quilt arrangements, and quilt producing software by Antony Boucher and Lance Guy.

    References;
  1. Dudeney, Henry Ernest. "Mrs. Perkins's Quilt.", Amusements in Mathematics, 1917. (Project Gutenberg)
  2. Conway, J. H. "Mrs. Perkins's Quilt." Proc. Cambridge Phil. Soc. 60, 363-368, 1964.
  3. Trustrum, G. B. "Mrs. Perkins's Quilt." Proc. Cambridge Phil. Soc. 61, 7-11, 1965
  4. M. Gardner, "Mrs. Perkins's Quilt and Other Square-Packing Problems," Mathematical Carnival, New York: Vintage, 1977.
  5. H. T. Croft, K. J. Falconer, and R. K. Guy, Section C3 in Unsolved Problems in Geometry, New York: Springer, 1991.
  6. Conway, J. H. "Re: [math-fun] Mrs. Perkins's Quilt - Orders 89, 90 improved over UPIG." math-fun@mailman.xmission.com mailing list. October 10, 2003.
  7. Ed Pegg, Jr., Square Packing and Mrs Perkins's Quilts
  8. Weisstein, Eric W. "Mrs. Perkins's Quilt." From Mathworld--A Wolfram Web Resource http://mathworld.wolfram.com/MrsPerkinssQuilt.html
  9. Charles H. Jepsen*, Ming Gu. "Dissections of p : q rectangles into thirteen p : q rectangular elements". Department of Mathematics, Grinnell College , 2004
  10. Paul J. Nahin "Mrs. Perkins's Electric Quilt: And Other Intriguing Stories of Mathematical Physics"
  11. R. K. Guy, OEIS A089046, "Least edge-length of a square dissectable into at least n squares in the Mrs Perkins's quilt problem."
  12. Antreas P. Hatzipolakis and J. H. Conway Math Forum Discussions
  13. Ed Pegg Jr, Lance Gay, Erich Friedman, Richard Guy, Bouwkamp, Duijvestijn and Antony Boucher, optimal quilt listings, primitive quilts, C programs
  14. Ed Wynn. Exhaustive generation of ‘Mrs Perkins’s quilt’ square dissections for low orders.