[ndpenrhx] Mrs. Perkins Quilt

Mrs. Perkins's Quilt is another name for Minimal Compound Imperfect Squared Square.  We explain the components of the name and explore generalizations.

We refer to Dudeney's labeled solution to the 13x13 quilt (problem 173) in his book "Amusements in Mathematics".

Minimal because it has smallest number greater than 1 (in this case, 11) of internal squares for a quilt of given size (in this case, 13x13).

Compound (not Simple) because adjacent internal squares labeled 7 and 8 form a rectangle.  The existence of two or more squares forming an internal rectangle makes it not Simple.

Imperfect (not Perfect) because 7 and 8 (as well as other pairs) are the same size.

Squared because all the internal pieces are squares.

Square because the outer border is a square.

The constraints for Mrs. Perkins's Quilt are relaxed enough that any size square is guaranteed to have a solution.  Needing to find the minimal solution is what makes the problem hard.  For other squared square (and related) problems, finding any solution may be hard; often, no solution exists for a given size square.

For Mrs. Perkins's Quilts, the outer border could be any shape composed of 1x1 squares.  What is an algorithm that finds relatively good (not necessarily minimal) solutions to arbitrary rectangles or regions?  This could be a nice xscreensaver hack, subdividing the screen into squares.  A greedy algorithm could do it, though not necessarily well.

If the outer border is not a rectangle, finding minimal partitions with internal pieces permitted to be rectangles might be tricky.

Mrs. Perkins's Quilts also have a constraint in which the solution to a larger square (outer border) is not permitted to be the solution to a smaller square simply magnified by a integral factor.  Are there instances in which, if that constraint were removed, a larger square still has a better "prime" solution than the magnification of a smaller solution?  (This seems unlikely.)

Previously on squared squares.