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;

- {
**1**| 1}, {**4**|2}, {**6**|3}, {**7**|4}, {**8**|5}, {**9**|6,7}, {**10**|8,9}, - {
**11**|10-13}, {**12**|14-17}, {**13**|18-23}, {**14**|24-29}, {**15**|30-39,41}, - {
**16**|40,42-53}, - {
**17**|54-70}, - {
**18**|71-91}, -
{
**19**|92-120,122,126}, - {
**20**|121,123-125,127-154,157,158}, - {
**21**|155,156,159-207,209,216}, -
{
**22**|208,210-215,217-265,268,269,273}, - {
**23**|266,267,270-272,274-353,355,361,364,369,373}, -
{
**24**|354,356-360,362,363,365-368,370-372,374-446,448,450,451,453,456-459,461,468,479}.

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.

- {
**1**|1}, {**4**|2}, {**6**|3}, {**7**|4}, {**8**|5}, {**9**|6,7}, {**10**|8,9}, {**11**|10-13}, - {
**12**|14-17}, {**13**|18-23}, {**14**|24-29}, {**15**|30-39,41}, {**16**|40,42-53}, - {
**17**|54-70}, {**18**|71-91}, {**19**|92-120, 122, 126}, {**20**|121, 123-125, 127-154, 157, 158}, - {
**21**|155, 156, 159-209, 216}, {**22**|210-215, 217-265, 267-269, 271-273, 276}, - {
**23**|266, 270, 274, 275, 277-359, 361-364, 366-373, 376, 378, 380, 384, 386}, - {
**24**|360, 365, 374, 375, 377, 379, 381-383, 385, 387-475, 477, 479-481, 485, 486, 488}, - {
**25**|476, 478, 482-484, 487, 489-641, 643-645, 647-650, 653-659, 661, 664, 672, 675}, - {
**26**|642, 646, 651, 652, 660, 662, 663, 665-671, 673, 674, 676-832, 834, 836, 838-840, 842, 846, 853, 858, 866}, - {
**27**|833, 835, 837, 841, 843-845, 847-852, 854-857, 859-865, 867-1098, 1100-1116, 1119-1128, 1130, 1132, 1133, 1135, 1136, 1138, 1140-1146, 1151-1154, 1157, 1158, 1160, 1167, 1173, 1179}

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

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;

- {
**1**|1}, {**4**|2}, {**6**|3}, {**7**|4}, {**8**|5}, {**9**|6,7}, {**10**|8,9}, {**11**|10-13}, - {
**12**|14-17}, {**13**|18-23}, {**14**|24-29}, {**15**|30-39,41}, {**16**|40,42-53}, - {
**17**|54-70}, {**18**|71-91}, {**19**|92-120, 122, 126}, {**20**|121, 123-125, 127-154, 157, 158}, - {
**21**|155, 156, 159-209, 216}, {**22**|210-215, 217-265, 267-269, 271-273, 276}, - {
**23**|266, 270, 274, 275, 277-359, 361-364, 366-373, 376, 378, 380, 384, 386}, - {
**24**|360, 365, 374, 375, 377, 379, 381-383, 385, 387-475, 477, 479-481, 485, 486, 488}, - {
**25**|476, 478, 482-484, 487, 489-641, 643-645, 647-650, 653-659, 661, 664, 672, 675}, - {
**26**|642, 646, 651, 652, 660, 662, 663, 665-671, 673, 674, 676-832, 834, 836, 838-840, 842, 846-847, 853, 858, 866}, - {
**27**|833, 835, 837, 841, 843-845, 848-852, 854-857, 859-865, 867-1116, 1119-1128, 1130, 1132, 1133, 1135, 1136, 1138, 1140-1146, 1151-1154, 1157, 1158, 1160, 1165, 1167, 1173, 1179} - {
**28**|1117-1118, 1129, 1131, 1134, 1137, 1139, 1147-1150, 1155-1156, 1159, 1161-1164, 1166, 1168-1172, 1174-1178, 1180-1472, 1474-1484, 1486-1490, 1492, 1496, 1498, 1500-1501, 1504-1505, 1510-1511, 1513, 1520, 1523-1524, 1526, 1544}, - {
**29**|1473, 1485, 1491, 1493-1495, 1497, 1499, 1502-1503, 1506-1509, 1512, 1514-1522, 1525, 1527-1543, 1545-1966, 1968-1977, 1979-1986, 1988-1994, 1996-1998, 2000-2005, 2007-2008, 2011-2016, 2018-2020, 2022, 2024, 2028, 2030, 2032, 2036, 2056, 2066, 2074, 2090-2091, 2094, 2096, 2134, 2136}

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;

- {
**30**|1967, 1978, 1987, 1995, 1999, 2006, 2009-2010, 2017, 2021, 2023, 2025-2027, 2029, 2031, 2033-2035, 2037-2055, 2067-2073, 2075-2089, 2092-2093, 2095, 2097-2133, 2135, 2137-2594, 2596-2602, 2604-2611, 2614-2616, 2618-2620, 2623, 2626, 2630-2633, 2636 2639-2640, 2642-2646, 2648, 2652, 2654, 2660, 2664, 2668-2670, 2673, 2675, 2682, 2693, 2710, 2714-2716, 2718, 2739}

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;

- {
**31**|2595, 2603, 2612-2613, 2617, 2621-2622, 2624-2625, 2627-2629, 2634-2635, 2637-2638, 2641, 2647, 2649-2651, 2653, 2654-2659, 2661-2663, 2665-2667, 2671-2672, 2674, 2676-2681, 2683-2692, 2694-2709, 2711-2713, 2717, 2719-2738, 2740-3464, 3466-3467, 3469-3473, 3475-3484, 3486, 3488-3493, 3496-3500, 3502, 3504, 3506-3510, 3513, 3517, 3520-3525, 3528, 3530-3531, 3535-3536, 3539, 3544-3545, 3551-3556, 3558, 3563-3564, 3567, 3571, 3576, 3584, 3586, 3591, 3595, 3600, 3607, 3610, 3613-3614, 3617, 3641, 3647, 3650, 3725, 3755}, - {
**32**|3465, 3468, 3474, 3485, 3487, 3494-3495, 3501, 3503, 3505, 3511-3512, 3514-3516, 3518-3519, 3526-3527, 3529, 3532-3534, 3537-3538, 3540-3543, 3546-3550, 3557, 3559-3562, 3565-3566, 3568-3570, 3572-3575, 3577-3583, 3585, 3587-3590, 3592-3594, 3596-3599, 3601-3606, 3608-3609, 3611-3612, 3615-3616, 3618-3640, 3642-3646, 3648-3649, 3651-3724, 3726-3754, 3756-4533, 4535-4542, 45-45, 4547-4554, 4556-4592, 4594-4600, 4603-4604, 4606-4615, 4617-4622, 4624-4625, 4627, 4630-4640, 4643, 4645-4646, 4648-4650, 4652-4656, 4658, 4663-4664, 4666, 4668-4669, 4672, 4674, 4687-4688, 4696-4698, 4700, 4702, 4704-4709, 4713, 4716-4717, 4724-4725, 4731, 4734-4736, 4741, 4744, 4754, 4759, 4763, 4777-4778, 4780-4781, 4796, 4801, 4805, 4846, 4988}

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.

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.

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.

- A005670 (Mrs. Perkins’s quilt: smallest coprime dissection of
*n*×*n*square) for*n*= 1 , . . . ,120:

1, 4, 6, 7, 8, 9, 9, 10, 10, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15,*15*, 16,*15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19* - A045846 (Number of distinct ways to cut an
*n*×*n*square into squares with integer sides) for*n*= 1, . . . ,9:

1, 2, 6, 40, 472, 10668, 450924, 35863972, 5353011036. - A089046 (Least edge-length of a square dissectable into at least
*N*squares in the Mrs Perkins’s quilt problem) for*N*= 1, . . . ,19:

1, 2, 2, 2, 3, 3, 4, 5, 6, 8, 10, 14, 18, 24, 30,*40, 54, 71, 92*. - A089047 (Greatest edge-length of a square dissectable into up to
*N*squares in Mrs Perkins’s quilt problem) for*N*= 1 , . . . ,18:

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 13, 17, 23, 29,*41, 53, 70, 91*. - A018835 (Minimal number of smaller integer-sided squares that tile an
*n*×*n*square) for*n*= 2 , . . . ,126:

4, 6, 4, 8, 4, 9, 4, 6, 4, 11, 4, 11, 4, 6, 4, 12, 4, 13, 4, 6, 4, 13, 4, 8, 4, 6, 4, 14, 4, 15, 4, 6, 4, 8, 4, 15, 4, 6, 4, 15, 4, 16, 4, 6, 4, 16, 4, 9, 4, 6, 4, 16, 4, 8, 4, 6, 4, 17, 4, 17, 4, 6, 4, 8, 4,*17, 4, 6, 4, 18, 4, 18, 4, 6, 4, 9, 4, 18, 4, 6, 4, 18, 4, 8, 4, 6, 4, 18, 4, 9, 4, 6, 4, 8, 4, 19, 4, 6, 4, 19, 4, 19, 4, 6, 4, 19, 4, 19, 4, 6, 4, 19, 4, 8, 4, 6, 4 , 9, 4, 11, 4, 6, 4, 8, 4* - A211302 (Minimal number of smaller integer-sided squares that tile a
*p*×*p*square, where*p*=*i*-th prime) for*i*= 1, . . . ,30:

4, 6, 8, 9, 11, 11, 12, 13, 13, 14, 15, 15, 15, 16, 16, 16, 17, 17,*17, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19*. - A221841 (Number of ways to dissect a square into
*N*squares up to symmetry) for*N*= 1, . . . ,18:

1, 0, 0, 1, 0, 1, 2, 6, 16,*56, 183, 657, 2277, 8813, 34178, 137578, 558734, 2285694*. - A221842 (Number of ways to dissect a square into
*N*squares) for*N*= 1, . . . ,18:

1, 0, 0, 1, 0, 4, 8, 36, 105,*384, 1340, 4975, 17676, 69052, 270716, 1093218, 4455047, 18246018*. - A221844 (Number of prime dissections of an
*n*×*n*square into integer-sided squares up to symmetry) for*n*= 1 , . . . ,9:

1, 1, 2, 11, 76,*1490, 56977, 4495010, 669203525*. - A221845 (Number of prime dissections of an
*n*×*n*square into integer-sided squares) for*n*= 1 , . . . ,9:

1, 1, 5, 38, 471, 10661, 450923, 35863932, 5353011030. - A224239 (Number of inequivalent ways to cut an
*n*×*n*square into squares with integer sides) for*n*= 1 , . . . ,12:

1, 2, 3, 13, 77, 1494, 56978, 4495023, 669203528, 187623057932,*98793520541768, 97702673827558670*. - A sequence not currently in the OEIS is the number of size collections in prime dissections of integer-sided squares into
*N*squares, for*N*= 1, . . . ,18:

1, 0, 0, 1, 0, 1, 1, 2, 4, 7, 18, 40, 119, 323, 1100, 3594, 13068, 47444.

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**

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.

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