# Tiling a 16x16 square with 1x4 rectangles

Consider a 16x16 square subdivided by grid lines into unit squares. It is easy to completely tile (no overlaps, no gaps) this square with 64 1x4 rectangles. Each 1x4 rectangle in the tiling (no matter whether horizontally or vertically oriented), will be split into two non-empty regions by exactly three grid lines.

For example, see the diagram below where there are three bolded grid lines which each split the red 1x4 rectangle into two non-empty regions. The leftmost and rightmost bolded grid lines each split the 1x4 rectangle into two regions (a unit square and a 1x3 rectangle). The middle bolded grid line splits the 1x4 rectangle into two 1x2 rectangles.

The goal of this puzzle is to completely tile (no overlaps, no gaps) this 16x16 square with 64 1x4 rectangles to maximize the number of grid lines that split at least one 1x4 rectangle into two non-empty regions.

Clarification: You may position a 1x4 rectangle in the position shown in the diagram BUT that is not a requirement.

Below a solution in which every gridline splits at least one 1x4 rectangle into 2 regions:

Edit

Actually, I found an easy pattern that will work on bigger squares as well:

• white: expandible corner piece.
• green: default center piece.
• red area could be filled up however you want, it doesn't matter.

16x16

20x20

24x24

• +1 Excellent answer; clearly explained and illustrated. Commented Apr 28 at 5:02
• Ha! I called it!
– PDT
Commented Apr 29 at 10:35

Unless I've misunderstood the requirements, the following is optimal:

Every gridline splits at least one rectangle.
A single split is highlighted for each horizontal and vertical gridline:

Via integer linear programming, the maximum is...

30:

  1  1  1  1  2  2  2  2 37 38  3  3  3  3 39 40
4  4  4  4  5  5  5  5 37 38  6  6  6  6 39 40
7  7  7  7  8  8  8  8 37 38 41 42 43 44 39 40
9  9  9  9 10 10 10 10 37 38 41 42 43 44 39 40
45 11 11 11 11 12 12 12 12 46 41 42 43 44 47 48
45 13 13 13 13 14 14 14 14 46 41 42 43 44 47 48
45 15 15 15 15 49 50 51 52 46 16 16 16 16 47 48
45 17 17 17 17 49 50 51 52 46 18 18 18 18 47 48
19 19 19 19 53 49 50 51 52 54 20 20 20 20 55 56
57 58 59 60 53 49 50 51 52 54 21 21 21 21 55 56
57 58 59 60 53 22 22 22 22 54 23 23 23 23 55 56
57 58 59 60 53 24 24 24 24 54 25 25 25 25 55 56
57 58 59 60 61 62 63 64 26 26 26 26 27 27 27 27
28 28 28 28 61 62 63 64 29 29 29 29 30 30 30 30
31 31 31 31 61 62 63 64 32 32 32 32 33 33 33 33
34 34 34 34 61 62 63 64 35 35 35 35 36 36 36 36