11405

# Mrs. Perkins's Quilts

"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
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. Given all that, try to solve Dudeney's original problem: to divide a 13×13 square into 11 squares. 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. Thus, an 8×8 square divided into four 4×4 squares is not considered optimal. Any optimal quilt is a Mrs. Perkins's quilt.
One method for finding new quilts is to replace a corner square with a square as big as the original quilt, then to add two squares. A second method adds three squares the same size as the original quilt around one corner. A third method doubles all squares and divides an odd-sided corner. A quilt that uses none of these methods is called primitive. If all the squares have different sizes, the dissection is called perfect. When no two squares of the same size share a full edge, the dissection is semiperfect.
Problem C3 in R. K. Guy's Unsolved Problems in Geometry involves finding optimal quilts. In 2003, author Ed Pegg found some new best solutions with Lance Gay, and sent them to Guy, who then found even more solutions. In 2010, Guy suggested that we compile all our findings and methods for a paper, which this Demonstration strives to do. A number of new discoveries were made in the compilation process.
Above size 200, it is extremely difficult to prove that a quilt is optimal. As such, many of these findings should be considered best known. The authors welcome any improvements.
UPDATE: Results extended to 40000.

### DETAILS

In a dissection, consider each horizontal segment as a vertex in a graph, and each vertical segment as an edge. In a perfect square dissection, where no two squares of the same size touch each other, this graph is a simple three-connected planar acyclic digraph and also a polyhedral graph. The number of squares corresponds to the number of edges. For 20 and 21 edges, the number of polyhedra is 144810 and 485704, which are approachable numbers for computer searches.
In optimal quilts, two squares of the same size can touch each other. The corresponding graphs can have multiple edges and can be two-connected. For 20 and 21 edges, the number of two-connected planar graphs is 115949791342 and 663640383400, which are currently too large for a computer search.
A solution of large squares can be crushed into much smaller rectangles for what the author calls a Mondrian dissection. For details, see the Demonstration Mondrian Puzzles.
Let be the list of squares that can be divided into a minimum of squares. For example, a side 675 quilt can be divided into 25 squares. The best known solutions for each quilt are as follows:
{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, 849, 853, 858, 866},
{27|833, 835, 837, 841, 843-845, 848, 850-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-1484, 1486-1490, 1492, 1496, 1498, 1500-1501, 1504-1505, 1510-1511, 1513, 1520, 1523-1524, 1526, 1544},
{29|1485, 1491, 1493-1495, 1497, 1499, 1502-1503, 1506-1509, 1512, 1514-1519, 1521-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},
{30|1967, 1978, 1987, 1995, 1999, 2006, 2009-2010, 2017, 2021, 2023, 2025-2027, 2029, 2031, 2033-2035, 2037-2055, 2057-2065, 2067-2073, 2075-2089, 2092-2093, 2095, 2097-2133, 2135, 2137-2594, 2596-2602, 2604-2611, 2614-2616, 2618-2620, 2623-2624, 2626, 2629-2633, 2636, 2639-2640, 2642-2646, 2648-2649, 2652, 2654, 2660, 2664, 2668-2670, 2673, 2675, 2682, 2693, 2710, 2714-2716, 2718, 2739},
{31|2595, 2603, 2612-2613, 2617, 2621-2622, 2625, 2627-2628, 2634-2635, 2637-2638, 2641, 2647, 2650-2651, 2653, 2655-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, 4544-4545, 4547-4554, 4556-4592, 4594-4600, 4603-4604, 4606-4615, 4617-4622, 4624-4625, 4627, 4630-4639, 4643, 4645-4646, 4648-4650, 4652-4656, 4658, 4663-4664, 4666, 4668-4669, 4672, 4674, 4687-4688, 4696-4698, 4700, 4702, 4704-4705, 4707-4709, 4713, 4716-4717, 4724-4725, 4731, 4734-4736, 4741, 4744, 4754, 4759, 4763, 4777-4778, 4780-4781, 4796, 4801, 4805, 4846, 4988},
{33|4534, 4543, 4546, 4555, 4593, 4601-4602, 4605, 4616, 4623, 4626, 4628-4629, 4640-4642, 4644, 4647, 4651, 4657, 4659-4662, 4665, 4667, 4670-4671, 4673, 4675-4686, 4689-4695, 4699, 4701, 4703, 4706, 4710-4712, 4714-4715, 4718-4723, 4726-4730, 4732-4733, 4737-4740, 4742-4743, 4745-4753, 4755-4758, 4760-4762, 4764-4776, 4779, 4782-4795, 4797-4800, 4802-4804, 4806-4845, 4847-4987, 4989-5994, 5996-6020, 6022-6038, 6040, 6042-6049, 6051-6072, 6074-6081, 6084-6087, 6089-6093, 6096-6097, 6099-6102, 6104-6105, 6107-6112, 6114-6115, 6117-6122, 6124-6128, 6130-6131, 6133-6138, 6141-6144, 6147-6150, 6153, 6155, 6158-6159, 6163-6165, 6167-6169, 6173-6174, 6176-6177, 6180, 6182, 6184-6185, 6188-6191, 6194, 6196-6198, 6202, 6205, 6208-6209, 6212, 6216, 6224, 6227-6229, 6236, 6241, 6244-6248, 6259-6260, 6266, 6270, 6272, 6282, 6284, 6286, 6288, 6297, 6303, 6305, 6308, 6317-6318, 6320, 6326, 6335, 6341-6342, 6344-6345, 6349, 6351, 6355, 6369, 6391, 6417, 6441, 6443},
{34|5995, 6021, 6039, 6041, 6050, 6073, 6082-6083, 6088, 6094-6095, 6098, 6103, 6106, 6113, 6116, 6123, 6129, 6132, 6139-6140, 6145-6146, 6151-6152, 6154, 6156-6157, 6160-6162, 6166, 6170-6172, 6175, 6178-6179, 6181, 6183, 6186-6187, 6192-6193, 6195, 6199-6201, 6203-6204, 6206-6207, 6210-6211, 6213-6215, 6217-6223, 6225-6226, 6230-6235, 6237-6240, 6242-6243, 6249-6258, 6261-6265, 6267-6269, 6271, 6273-6281, 6283, 6285, 6287, 6289-6296, 6298-6302, 6304, 6306-6307, 6309-6316, 6319, 6321-6325, 6327-6334, 6336-6340, 6343, 6346-6348, 6350, 6352-6354, 6356-6368, 6370-6390, 6392-6416, 6418-6440, 6442, 6444-7906, 7908-7942, 7944-7945, 7947, 7950-7964, 7967-7968, 7970-7992, 7994, 7996, 7998-8004, 8006-8011, 8013-8018, 8020-8033, 8036, 8039-8046, 8049-8065, 8068, 8070, 8072, 8074-8077, 8079-8083, 8085, 8088-8089, 8091-8095, 8097-8108, 8111-8112, 8115, 8117-8118, 8120-8127, 8129, 8131, 8133, 8137, 8140-8143, 8145, 8147, 8150, 8156-8159, 8161-8165, 8168, 8170, 8174-8175, 8177-8178, 8180-8181, 8183, 8187-8191, 8194, 8196, 8199-8200, 8207, 8210-8211, 8213, 8215, 8220, 8227, 8230, 8233, 8235-8236, 8240, 8244-8245, 8251, 8254, 8259, 8262, 8267-8268, 8283, 8286, 8290, 8313, 8325, 8338, 8341, 8359, 8367, 8383, 8387, 8396, 8402, 8426, 8430, 8434, 8452, 8568}
References
[1] S. Anderson, "squaring.net", July 5, 2017.
[2] H. T. Croft, K. J. Falconer, and R. K. Guy, Section C3 in Unsolved Problems in Geometry, New York: Springer, 1991.
[3] H. E. Dudeney, Problem 173 in Amusements in Mathematics, New York: Nelson, 1917.
[4] M. Gardner, "Mrs. Perkins's Quilt and Other Square-Packing Problems," Mathematical Carnival, New York: Vintage, 1977.
[5] Ed Pegg Jr, "Mathematical Games: Square Packings," Dec. 1, 2003.
[6] S. Anderson, "Mrs. Perkins's Quilt", squaring.net/quilts/mrs-perkins-quilts, July 5, 2017.

### PERMANENT CITATION

 Share: Embed Interactive Demonstration New! Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.