8
$\begingroup$

This set of T-shapes was devised by Jim Kerley who asked whether 1,2,3, or 4 sets would tile a rectangle (they will probably not, search nearly complete, tilings can be found for five sets or higher).

No overlaps/gaps, and you can flip the Ts if you think that will help. I rate this as surprisingly difficult and recommend you try it by hand before moving to a computer solution. I'm not saying you won't find a tiling by hand, but I would be impressed.

The ten T-shapes are those formed by sandwiching a rectangle with width 1 or 2, and length between 2 and 6, inclusive, between two 1×1 squares in the appropriate way. Each set has a total area of 80 squares, having pieces of size 4,5,6,7,8,6,8,10,12,14.
Here is an attempt to fit six sets in a rectangle, to illustrate how the different T-shapes fit together:

59-partial with six sets

Can you place nine sets of the ten given T-shapes in a 20x36 rectangle?

Improve this question
$\endgroup$
1
  • $\begingroup$ A single set certainly cannot fill a rectangle, because the 'height' of a T in each corner must be 2 (otherwise you can't fill the angle next to the edge), and there are are only two such tiles in a set. $\endgroup$ Commented Feb 20, 2025 at 12:18

2 Answers 2

Reset to default
5
$\begingroup$

You can solve the problem via integer linear programming as follows. Let $T=\{1,\dots,10\}$ be the set of polyomino types. Let $P$ be the set of polyominoes (one for each subset of cells in the $20 \times 36$ grid that matches one of the ten types in any of the four orientations). For each polyomino $p\in P$, let $t_p$ be the type, let $C_p$ be the set of cells it contains, and let binary decision variable $x_p$ indicate whether that polyomino appears. The constraints are \begin{align} \sum_{p\in P: (i,j)\in C_p} x_p &= 1 && \text{for $(i,j)\in [20] \times [36]$} \tag1\label1 \\ \sum_{p\in P: t_p = t} x_p &= 9 && \text{for $t\in T$} \tag2\label2 \end{align} Constraint \eqref{1} covers each cell with exactly one polyomino. Constraint \eqref{2} selects exactly $9$ polyominoes of each type.

Here is one possible tiling, with one color per type and the cells numbered according to copy ($1$ through $9$ for each type):

enter image description here

Improve this answer
$\endgroup$
5
  • $\begingroup$ How long did the solver take for this one? $\endgroup$ Commented Feb 22, 2025 at 5:49
  • $\begingroup$ @justhalf Not sure how long it would have taken to solve directly. I got impatient and wanted to see some progress, so I changed from a feasibility problem to an optimization problem by adding a binary slack variable $s_{ij}$ to \eqref{1}, relaxing \eqref{2} from $=$ to $\le$, and minimizing the infeasibility $\sum s_{ij}$. This got down to objective value $4$ (one small T missing) but then stalled. To finish things off, I performed a local search by fixing the variables for two of the ten types at a time, and solving over the rest. Took a few hours (maybe longer than solving directly). $\endgroup$ Commented Feb 22, 2025 at 14:08
  • 1
    $\begingroup$ ah, interesting. Thanks for sharing the details and some tricks, Rob. $\endgroup$ Commented Feb 22, 2025 at 14:10
  • 1
    $\begingroup$ For comparison, my 'slightly sharpened sledgehammer' approach which is simple backtracking with a beam search aided by scoring heuristic took 248.5 hours $\endgroup$ Commented Feb 23, 2025 at 2:01
  • 1
    $\begingroup$ @RobPratt it's taken me rather longer, but I finally solved it too. $\endgroup$ Commented Mar 5, 2025 at 12:47
2
$\begingroup$

My computer algorithm found a solution in 33 seconds.

It took rather longer than that to figure out: I got to 89 tiles in less than 2 minutes, but even after several days running time the last tile could not be placed.

Obviously it needs the smallest tiles in each corner, but the breakthrough came when I restricted their availabilty, and noticed that large areas can be filled without the two smallest tiles. So I held back most of the small tiles, allowing them only when the grid is nearly full.

It uses a brutal recursive and backtracking algorithm, with some heuristics about what tiles can be placed.

enter image description here

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.