L Polyominoes

L Polyominoes

An L polyomino is a rectangle with a rectangular notch removed from one corner. When oriented properly, these resemble the capital letter L, a large rectangle with a smaller rectangle removed from the upper right. More often we orient the polyomino so that it lies on its back, with its foot sticking up. We refer to this polyomino as "lying on its back", or "face up".

Suppose the L polyomino has width w and height h, where w >= h. Remove a y×z rectangle from the upper right corner. This shape is said to be "lying on its back", because it is oriented horizontally. Rotate it 90° counter clockwise and it is "standing up", or "pointing up".

  1. L polyominoes of order 2.

    If z is half of h or y is half of w, the polyomino has order two. Henceforth we shall assume z is not half of h and y is not half of w.

  2. Pieces never lie face down on the floor.

    If piece a lies face down on the floor, its tab pointing right, and piece b is immediately to the right of a, b cannot place its base or back against a, else the notch of a is permanently isolated. If b is the 180° rotation of a, it cannot slide its tab under the tab of a (z < h/2), or the two tabs leave a thin gap (z > h/2). So the face of b slides under the tab of a.

    If there are no gaps anywhere, y = z and z = w-y, hence w = 2y. This contradicts {1}, so there must be a gap between the tab of a and the notch of b. This means z = w-y and z > y. In other words, z+y = w, and z is the larger.

    Only the tab of a piece can fit into the resulting gap of width z-y. Let the tab of c fill the corner of a and b. If c faces left over a, we have a gap of height y - (h-z). If this gap is nonzero, only a tab of thickness h-z will fit in. Yet y, the length of such a tab, is less than z, so the tab wouldn't reach all the way to c. The gap is 0, y = h-z, and h = w. We are dealing with a shape bounded by a square. If c completely fills the gap above b, the shape is established, a 3×3 square minus a 1×2 rectangle. This has order 28. If c and d both point their tabs down into the notch of b, the shape is established, a 4×4 square minus a 1times3 rectangle. This was handled in the section on special shapes.

    Finally we let c face right. Since d cannot stand next to c facing left, c fills the gap entirely, giving y + h-z = z. Now c hangs z-(h-z) squares beyond b. Slide d beneath c and assume d points right. This gives a gap of height w-h. We dealt with the square shape, w = h, in the last paragraph, so this gap is real, and must be filled. Since w is y+z, and z is larger, w < 2z < 2h. There isn't room for another horizontal piece atop d. If we try to slide the face of e in the gap we add w-y to h. This is larger than w+h-z, which exceeds w. Only a tab can fit, and it must fit precisely, giving 2h-z = w. This establishes the shape, a 5×4 rectangle minus a 2×3 rectangle. This was handled in the section on special shapes. Therefore d must stand back-to-back against b. Verify that d cannot point down; its notch could not be completely filled.

    If c is flush with the tab of d, then 2(h-z) = z. This establishes the shape, a 3×3 square minus a 1×2 rectangle, which has order 28.

    If c extends beyond the tab of d, we have a gap of height y to fill. Thus h-z = y, and we have a square shape that was handled earlier.

    Thus c does not reach the edge of d. Place e in the corner of c and d, and remember that e must not extend to the right of d, else we have a gap of height y (as described in the last paragraph) that cannot be filled. The tab presents the smallest edge, of length h-z, and that would completely cover the top of d and force c back onto b, which is impossible.

    Henceforth we can assume that a piece never lies face down on the floor, or faces the left or right wall.

  3. Square pieces never point down onto the floor.

    If the shape is taken from a square, as indicated by h = w, pieces can never point down onto the floor. Redefine the roles of h and w, and the piece is lying face down on the floor, which contradicts {2}.

  4. Pieces cannot point down on the floor when y < h.

    Let a point down onto the floor, and note that b cannot slide its face into the notch of a, else the shape has order 2. Thus b points towards or away from a, and when y < h, b must point towards a. We may also assume w > h by {3}.

    If the notch of a is not completely filled by b, the remaining gap must be filled by the face of c pointing up. However, this causes c to stand in the notch of b, which is impossible, since y < h. Therefore b fills the notch of a completely, and y = h-z.

    If the faces of a and b touch, y = z, giving a shape of order 2. So we have a gap of width y-z in the notch of b.

    Place c in the corner of a and b. Suppose c lies face down and points left, extending over the top of a. If z = w-y then we have a square (h=w). If z > w-y then z > h-y, yet z = h-y. Therefore c points right, and completely fills the notch of b, giving w-y = y-z.

    Note that c extends z squares beyond b. Slide d below c. If d faces left it must fit exactly, giving w-y = h. Yet w-y = y-z, so h = y-z, which contradicts y < h. Instead, d must lie down and point right. We already know z+y = h, hence z < w-y. Thus c does not reach the notch of d. Place e in the corner of c and d. If e extends beyond d we have a gap of height z that cannot be filled. Only the tab of e might fit, setting z + h-z <= w-y. Combine with w-y = y-z, and h <= y-z. Yet h exceeds y, so c cannot lie face down atop b.

    We now know that c points down onto b. If c faces right, its tab fills the entire gap, giving y=z + h-z, or y = h. So c faces left, d stands back-to-back against c, and 2(h-z) = y-z. this implies 2h = y+z, yet y+z is h. That takes care of c, and b, hence a cannot point down.

  5. Small notch: y < h/2 and z < h/2.

    Suppose our shape has a small notch, y and z are less than half of h. Let a tile the origin - the lower left corner of the tiled rectangle. By {4}, its back must be placed against the floor or the left wall. We can always reflect the tiled rectangle, so assume a lies on its back, its notch at the upper right. piece b, immediately to the right of a on the floor, cannot place its back or base against a, else the notch cannot be filled.

    Suppose b stands up and faces left. If the two notches do not coincide in height, one or the other will create a gap that cannot be filled. Thus h-z = w-y. It is possible that w = h and y = z, but this will be handled in the next paragraph. For now, assume w > h, hence y > z. This is illustrated by a 8×7 rectangle with a 3×2 notch removed. The a-b gap has width y+z, which is strictly less than h. It must be filled by a tab of width w-y or h-z (same thing). Assume c lies on top of a, and the two are 180° rotations of each other. We say that a and c are "interlocked". A rectangular space now exists between c and the left wall, just above a. Its width is w-2y and its height is h-z. Rewrite w-2y as h-z-y, a width considerably smaller than h, and even smaller than the tab h-z. Nothing can fill this space. Thus c stands up, with its tab pointing down into the a-b gap. If c faces left there is a gap between a and the overhang of c, having height y-z. This is clearly unfillable, unless y = z (no gap), but we're assuming y > z, so let's move on. Let c face right and interlock with b. The rectangular space between c and the left wall now has width w-y and height w-z. A tab of width w-y can indeed slide into this space, but in order to reach all the way down to a, w-z must equal y or z. If y+z is at least w then y+z exceeds h, which contradicts (y and z) < h/2. Thus b does not stand up next to a.

    Since b does not stand up next to a, it must lie down on the flor, the horizontal reflection of a. This presents a 2y×z gap which will be filled by c. Suppose c is horizontal, hence 2y = w-y, or w = 3y. If c points left then the space between c and the left wall has width y, and cannot be filled. If c points right then this space has width 2y, just like the a-b gap. Since 2y < h, only a tab or face can slide into this space. Yet the space has height h-z, which is longer than y or z.

    Now c must point downward, its tab filling the double notch. This implies 2y = h-z. The vertical gap between c and (a or b) has height y-z, which implies y >= z. Nothing fits into a gap of height y, much less y-z, so y must equal z. Combined with the last equation, y = z = h/3. If w = h, a situation that was postponed before, we have established the shape, a 3×3 square minus a 1×1 square. Again, nothing fills the space above a, to the left of c. hence w > h.

    Place d on top of a, at the left wall, and note that d must stand up and face right. Any other pieces between d and c must also stand up. If there is an adjacent piece e it must face d, creating a double notch that is filled by the tab of f. If f faces left the space between f and the left wall, h-2z = z, is simply too small. If f faces right the gap is h-z, so the tab of g might slide in, but then y >= w-y, even though 2y < h. Thus d is the lone vertical piece.

    If c faces left then w-y = h+z, or w = h + 2y. This establishes the shape, a 5×3 rectangle minus a 1×1 square, which was handled in the section on special shapes. Thus c faces right, and w-y = h. This establishes the shape, a 4×3 rectangle minus a 1×1 square. This polyomino has order 50. That completes the analysis of the small notch, with (y and z) < h/2.

  6. Tall thin notch: y < h/2 and z > h/2.

    Thanks to {4}, a lies on the floor, its notch at the upper right. Suppose b lies on the floor next to a, and presents a double notch that will be filled by c. Unfortunately the tab of c isn't long enough to do the job. But c might lie face down, if 2y = w-y. If c points left then the space between c and the left wall has width y, which can only be filled if h-z = y. Slide d into this slot, facing right, and let e fill the corner created by c and d, having width w-z and height 2y.

    If e points up we must compare w-z and h (y+z). Sinze z > y, 3y-z < y+z. Thus e extends beyond c, over b, producing a gap of height h-z. An even longer gap is produced if e lies on its back. Let f slide its tab between e and b. We can't afford any gaps between e and f, so w-z+y is either w or h. The former forces y = z (contrary to our assumptions), and the latter implies 4y = h+z = y+z+z, or 3y = 2z. This establishes the shape, a 6×5 rectangle minus a 2×3 rectangle, which was handled in the section on special shapes.

    If e points down into the c-d corner, and its tab does not cover all of c, we find a (w-h)×y gap. If w = h we find the now-familiar shape of order 28, so we do have a gap to fill. Even if f could fill this gap with its tab, lying face down, it would crash into b.

    Next, e might point down and face d, wrapping around c, whence w-z = z. Thus 2z = 3y, building the same shape we considered before, a 6×5 rectangle minus a 2×3 rectangle.

    That brings us to the last orientation of e, lying face down. Since w-y > w-z, e still extends beyond c. Once again we ask the tab of f to slide under without gaps, forcing w-z+y = w-y, or 2y = z. This gives our order 28 shape again.

    Next assume c points right. Since 2y < h, d places its face or tab in the gap above a. If its tab is down, then 2y = h-z, and the tab cannot reach all the way down to a. So d is the vertical reflection of a. Let e fill the gap between c and the tab of d. Thus 2z-h is either 2y or h-z. Assume the former, hence z-y is half of h. The gap between the tabs of d and e is z-y, or half of h. Since 3y is at least h, 2y is more than half of h, so let the tab of f fill the corner of d and e. If f faces left we can't afford a gap between d and f, hence y = h-z. This makes y ¼ of h and z ¾ of h, hence 3y < h, hence w < h, which is impossible. So f faces right and its tab fills the entire gap, hence h-z = h/2, giving a shape of order 2. Therefore e lies on its back across c, and 2z = 2h-z, or z = 2h/3. Remember that y is at least h/3, else h < w. If y is exactly h/3 we create a shape we've seen before, of order 28, so assume y > h/3. If f, above d, points up, we have a gap of width w-h = 3y-h, which is smaller than y. If filled by the tab of g, we have 3y = 4h/3, or 9y = 4h. This establishes the shape, a 12×9 rectangle minus a 4×6 rectangle. It also produces a thin gap between e and g that cannot be filled. So f lies back-to-back atop d. Place g above f. If g stands up or lies on its back we have a gap of height z. Now 2y is too large, and h-z is too small, so g is the vertical reflection of f. The double notch has height 2z. If h stands up in this double notch we will not be able to fill the notch of h, because of the tab of g, which is longer than h-z. Nor can h face left, because 2y < 2z. We must fill the double notch with two horizontal pieces, reaffirming 2z = h + h-z. Once h and i are placed, i extends above the top surface of g. This is exactly the same pattern we saw 2h rows below. By induction, pieces climb up the left wall forever. That completes the case of b lying down and pointing towards a.

    At this point b stands up and faces left. Note that w-y >= h-y > h-z, so the notch of a is lower, and must be filled first. Since w-y > y, only the thin tab of c can fill the notch of a. In fact c and b interlock. Thus y = h-z. Also, h-z + y = w-y, or w = 3y. Choose any z where z > y and z <= 2y, and we have h = y+z and w = 3y. When z = 2y we find the shape of order 28 again. Thus we may assume z is strictly between y and 2y. Piece d filss the space between c and the left wall, just above a. Pieces d and a are vertical reflections, giving a gap between c and the tab of d of height 2z-3y. If there is no gap, we have 2z = 3y. This establishes the shape, a 6×5 rectangle minus a 2×3 rectangle, which we saw before. So there is a real gap, filled by the tab of e. If 2z-3y = h-z = y, then z is twice y, which has already been handled. This completes the case of b standing up.

    When this result is combined with {5}, we can assume, hereinafter, that y is at least h/2.

  7. y = h/2.

    We may assume w > h, else the shape has order 2.

    Let a lie on the floor and point right. Suppose b lies on the floor next to a, and presents a double notch of size h×z. Suppose c fills this double notch, or at least the left side of it, by lying face down, whence w-y <= h. If c points left then the space between c and the left wall has width w-2y = w-h <= y. A tab must precisely fill this space. Thus y = h-z, which gives a shape of order 2. So c points right, and w-y is precisely h. Our shape is a square with a tab attached. The space between c and the left wall now has width h, the side of the square. If d fills this space, and is the vertical reflection of a, there is a gap between c and the tab of d. This gap has height 2z-h, which forces z > h/2. The gap is filled by the tab of e, hence 2z-h = h-z, or 3z = 2h. This establishes the shape, a 9×6 rectangle minus a 3×4 notch. This was handled in the section on special shapes.

    If we still want c to point right, d must point up the left wall. Let e fill the corner of c and d. If e presents a flat side, any side, against d, the notch of d cannot be filled. If e lies face down and points left, the tabs of d and e collide, or there is a gap between them that must be filled by the tab of f. This establishes the shape, a 6×4 rectangle minus a 2×3 rectangle. However there are thin gaps around f that cannot be filled. Finally e might lie back-to-back atop c, pointing towards d. If d and e are flush then z is half of h, which gives an order of 2. Since the pieces are not flush, we have a gap above d or e, of width z or y respectively, that cannot be filled. That's it for e, and d, and c lying face down.

    Since w > h, c cannot lie on its back inside the double notch, and we can't fit two downward tabs precisely in the double notch, so c stands up. Since w exceeds h, the tab of c pokes well above the a.b landscape, but what about the notch of c? If the notch is actually lower than h, we have w-y + h-z < h, or y+z > w. Piece d could lie face down in the notch of c, pointing over the tab of c -- we know there's room. Yet this leaves a square gap of side z-(w-y). With w-y at least h/2, we can't put another piece face down in this gap. Even the tab of e is too large. So we must use tabs to fill the notch of c. One thin tab cannot fill the notch, since h-z is not half of h. If two thin tabs fill the notch, one of the two pieces, facing away from the tab of c, creates a gap of width z that cannot be filled.

    Suppose the notch of c is flush with its neighbor, hence w-y = z. If c faces right, the space between c and the left wall has width z, and can only be filled by the vertical reflection of a. Since z exceeds h/2, there is a gap between the tabs of c and d, that must be filled by the tab of e. This leaves a gap above the notch of c with height h/2 that cannot be filled. So c faces left, and the space between c and the left wall has width 2z. Let d sit atop a, against the left wall. If d lies on its back, the gap between the tabs of d and c has width z-h/2. This cannot equal z, hence z-h/2 = h-z, or z = 3h/4. This establishes the shape, a 5×4 rectangle minus a 2×3 rectangle. This was handled in the section on special shapes. If d points up the left wall, the gap between d and the tab of c has width 2z-h. Thus 2z-h = h-z, or z = 2h/3. This establishes the shape, a 7×6 rectangle minus a 3×4 rectangle. Yet when the notch of d is filled, we always find inaccessible gaps. So we may assume the notch of c rises above a and b. In other words, w-y > z.

    Let d, just to the left of c, lie down on top of a, and suppose c faces right. We know w > y+z, and if y > z, w > 2z, whence c won't fit. So y < z, and the tab of d extends beyond the tab of c. If there is a gap between c and d, place another piece in the gap. Either way, we have to fill the notch of c, a gap of height y. Only the tab of e can point into the notch of c, and it isn't long enough to reach the tab of c. So c faces left and d wraps around c, giving 2z = w-y. If z < h/2, the tabs of c and d collide. Thus z > h/2, and there is a gap between the tabs of d and c. Let the tab of e fill the corner where c and d meet. If e faces left, there is a gap between d and e that cannot be filled. So e faces right and interlocks with the tab of c, and z = 3h/4. This establishes the shape, an 8×4 rectangle minus a 2×3 rectangle. This was handled in the section on special shapes. That's the end of d lying down.

    If d points down onto a, and c faces right, y+z = w; yet w > y+z. If c faces left, y+z = w-y, and h-z = w-y, hence y+2z = h. This establishes the shape, a 5×4 rectangle minus a 2×1 rectangle. The disposition of this shape is unknown.

    Finally let d point up along the left wall. Suppose c faces d, the two pieces out of phase by z squares. With w-y > z, only the thin tab can be used to fill the notch of c. In fact we must use two of them, one facing left, and that forces y = z. Thus c faces right. If z < y, the bracketed notch of d cannot be filled, hence z > y. Let e fill the corner where c and d meet. If e presents a straight left edge, it brackets the notch of d, which cannot be filled. If e extends beyond the tab of c, the notch of c cannot be filled. So e interlocks with d, and y = z-y, which is impossible. That's it for d, and c rising above the landscape.

    We've place the notch of c below, at, and above the a b line, and made no progress. Thus b does not point towards a. Instead, b stands up and faces a.

    If the notch of b is higher than the tab of a, the gap of width h/2 cannot be filled.

    Suppose they are flush, hence h-z = w-y, and z < y. The gap is y+z, which is less than h. Place c in the notch of a. It can't stand up, and its tab won't precisely reach the notch of a, so c is horizontal. If it points right, it must be a perfect fit in the notch, yet z < y, hence the two tabs collide. Thus c points left across a. If c is a perfect fit we have w-y = y+z. This establishes the shape, a 5×4 rectangle minus a 2×1 rectangle, whose disposition is unknown. If we need to supplement with the tab of d, we have w-y + h-z = y+z, which forces 2z = w, and w becomes smaller than h.

    Finally let the notch of b remain lower than the tab of a, whence w-y < h-z. Clearly y has to be larger than z, to make up for the fact that w exceeds h. Now w-y, which is larger than y, is larger than z, so the face of c will not fit into the notch of b. Nor will the tab, since h-z > z. That takes care of b standing next to a.

    Henceforth we can assume y > h/2.

  8. Square notches.

    Assume y = z, a square notch. We've already dealt with y <= h/2, and z is no more than h, hence h/2 < y < h. Note that {4} is in force; pieces either stand up or lie face up on the floor.

    Place a in the lower left corner of the rectangle and assume it points right. Without regard to b, assume c points down into the notch of a and faces left. If c reaches the left wall we have w-y = y, giving a shape of order 2. So we have a gap of w-2y by w-y to fill. Neither tab nor face can reach down to a, so w-2y is at least h. All pieces between c and the left wall stand up. Let d point up the left wall and place e on top of d. If e is anything other than the reflection of d, we have a square notch to fill, similar to the notch of a. This can only be done with tabs, two tabs in fact, but there is no room for the face of f in the space between d and c. So e points down and f fills the notch of d. If f stands up its face fills the double notch perfectly. This sets w = 3y, yet the height of d is at most w-2y, setting h <= y. Thus f points right. Reasoning as above, the face of f cannot fill a double notch formed by d and g. Nothing else can stand next to d, so d is entirely sufficient, and w-2y = h. The gap between f and e, of thickness 2y-h, can only be filled by a tab. This establishes the shape, a 7×3 rectangle minus a 2×2 square. This was handled in the section on special shapes. Thus c does not point down and face left.

    Suppose c lies face down and points left. Its tab cannot touch the left wall, else the shape has order 2. Thus w exceeds 2y. If the face of b slides under c, w-y = h-y. Turn the piece around and call it the tab. Thus the tab of b slides under c. If there is no gap then w-y = 2y. The gap above a can only be filled by a tab, and that gives a shape of order 2. So there is a gap between c and b, which is filled by the tab of f. Thus h+w = 4y. If the tab of d fills the gap above a, we have w-2y = h-y. This establishes the shape, a 5×3 rectangle minus a 2×2 square. This piece has order 270. With w no larger than 3y, the gap of w-2y is smaller than h, hence d cannot point up. That takes care of c wrapping around the face of a.

    If b points or faces right, or faces left (with w > h), the notch of a can only be filled by tabs. Two tabs to be exact, else the shape has order 2. Yet this forces c to wrap around the face of a. Thus b is the horizontal reflection of a.

    If c lies face down in the notch of a, it points right and fills the double notch perfectly, setting w = 3y. If the tab of d fills the gap above a we have h-y = y. If d points up the left wall we have H <= 2y. Of course h must be strictly less than 2y, so other vertical pieces fill the gap. If e places its back against d, we can't fill the square notch of d without crashing into the left wall. Thus d and e face each other, and 2h is no more than 2y, which is impossible. Therefore d is the vertical reflection of a. The tab of e fills the gap between c and d, and that establishes the shape, a 6×3 rectangle minus a 2×2 square. This has order 396.

    Let c lie down in the double notch, hence 2y exceeds w. Whether c points right or left, and whatever we put next to c (if it points right), the notch of c presents a gap that has width y. We must fill it with two pieces that protrude in opposite directions. Let c point right, hence the gap above a is w-y by h-y. Let d lie face down in this gap, the vertical reflection of a. Let e be one of the two pieces in the gap of c. It wraps around c and crashes into d (since y exceeds w-y). Thus c points left, and e rises above a, turns left, and crashes into the left wall.

    Assume c points down into the notch of a, and faces right. If there is a gap next to c, and it is filled by d, we have a perfect fit, and a shape of order two. Thus there is no gap, and h-y = 2y. This contradicts y > h/2.

    Finally we have shown that c stands up in the notch of a. Let d fill the gap between c and b, wrapping around the face of b. Suppose c faces right, hence the gap above a is w-y square. If d does not rise above c, d lies face down, 2y = h+w-y, and h <= w-y. This sets y >= h, impossible. Thus d rises above c, and the notch of c must be filled by two pieces that protrude in opposite directions. Call these e and f, and place g in the corner of a and c. Verify that g points up and faces right, its face fitting perfectly into the gap of height w-y between a and e. This means w-y is at least h. Now we know d can't lie face down, so it points down, whence 2h-y = 2y, and y is 2/3 of h. Verify that additional pieces cannot stand up between d and the left wall. This establishes the shape, the polyomino of order 270, which we've seen before.

    Now we know c faces left. Suppose it does not rise above a, hence w-y < y. As before, e and f fill the notch of c by protruding left and right. The gap above a has height h-y. We know w exceeds h, else c may as well be lying down in the double notch, and we already dealt with that. So g can only fit its tab in the gap, and it would crash into the left wall. Therefore c rises above a, and w exceeds 2y. If g, above a, is the vertical reflection of a, we need a perfect fit around c, hence 2y = w-y. Again d points down, making y 2/3 of h. This establishes the shape, the polyomino of order 396, which we've seen before. the same holds if g points down and wraps around c. Thus g stands next to c and points up. Now w-y is at least h, d points down, y is 2/3 of h, additional pieces between d and the left wall lead to contradictions, and we find the shape of order 270. Those are all the orientations of c, and that's it for the square notch.

  9. y = h and h+z = w.

    This shape has order 4.

  10. y=h.

    Suppose a points down onto the floor and b points into a. Thanks to {9}, the toe of c cannot fill the gap between a and b. If we want a to point down, b points right, filling the notch of a. Thanks to {9}, a and b are not flush. Suppose a extends beyond the toe of b, hence z > w-h. Only the toe of c can fit into the notch of b, and this leaves a small unfillable gap. So the toe of b is farther right, giving w-h > z.

    There's lots more work to be done here.