Tiling 2-Deficient Rectangular Solids with L-Trominoes in Three and Higher Dimensions

In 1954 Solomon Golomb [4] showed that if you remove a square from a chess board of size 2N x2N then the resulting board can always be tiled by L-shaped trominoes (polyominoes of three squares). In the 1980s Chu and Johnsonbaugh [2, 3] characterized which 2D MxN boards are tilable by L-tromines if you remove an arbitrary square. In recent work [1], the current authors showed that arbitrary 3D rectangular boards with one cube removed, of dimension KxLxM, where KLM 1 (mod 3) and K,L,M > 1 are L-tilable. We also extended this result to all higher dimensions.

2-deficient boards (boards with two squares or cubes removed) are especially interesting because it is easy to see that there are no rectangular NxM boards that are generically tilable in the sense that they can be tiled with L-trominoes regardless of the squared removed – just remove two squares that effectively isolate a corner square. However, in 2008 Starr [7] showed that all 3D cubical boards of dimension NxNxN for N 2 (mod 3) with two cubes removed are L-tilable. In the present work we extend Starr’s result to show that indeed the same is true for arbitrary 3D rectangular boards of dimension KxLxM, where KLM 2 (mod 3), and K,L,M > 1. As in our earlier work, we extend the result to all higher dimensions.

By: Arthur Befumo, Jonathan Lenchner

Published in: RC25628 in 2016


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .