Mrs. Perkins's Quilts
Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
"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
[more]
Contributed by: Ed Pegg Jr and Richard K. Guy (April 2010)
Open content licensed under CC BY-NC-SA
Snapshots
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