# Enigmatic Code

Programming Enigma Puzzles

## Puzzle #29: How many strips? How many 3×1 strips, like the example pictured [right], can be cut out of this piece of wood [left]?

[puzzle#29]

### 2 responses to “Puzzle #29: How many strips?”

1. Jim Randell 9 November 2019 at 8:08 am

I assumed the puzzle was asking what is the maximum number of strips that can be cut of the piece of wood.

There are 7 squares missing from a complete 8×8 grid, so we cannot make more than 19 strips consisting of 3 squares from the piece of wood.

This Python program searches for the maximum possible number of strips. A minimal solution is found immediately, but the program takes 2m13s to run to completion.

```from enigma import Accumulator, div, printf

# make the grid (0 can be used, -1 can't be used)
grid =  * 64
for i in [0, 6, 18, 33, 39, 45, 60]: grid[i] = -1

# try to tile the grid
# m = accumulator for count of unused squares
# g = current state of the grid
# u = number of unused squares
# i = current square to try
# v = next value to fill out on tile
def tile(m, g, u, i=0, v=1):
# are we done?
if i > 63:
if u < m.value: printf("[u={u} -> g={g}]")
m.accumulate(u)
return
elif g[:i].count(0) < m.value:
if g[i] == 0:
# can we place a vertical strip?
if i < 48 and 0 == g[i + 8] == g[i + 16]:
g[i] = g[i + 8] = g[i + 16] = v
tile(m, g, u - 3, i + 1, v + 1)
g[i] = g[i + 8] = g[i + 16] = 0
# can we place a horizontal strip?
if (i % 8) < 6 and 0 == g[i + 1] == g[i + 2]:
g[i] = g[i + 1] = g[i + 2] = v
tile(m, g, u - 3, i + 3, v + 1)
g[i] = g[i + 1] = g[i + 2] = 0
# move on to the next square
tile(m, g, u, i + 1, v)

# accumulate solutions by the smallest number of unused squares
u = grid.count(0)
m = Accumulator(fn=min, value=u)

# find tilings on the grid
tile(m, grid, u)

# output max number number of strips
n = div(u - m.value, 3)
printf("max = {n} strips")
```

Solution: 15 strips can be cut from the shape.

There are many ways to cut the 15 strips. Here are two: The unused squares are marked in green.

These can be formed using a “greedy” strategy by starting in the top left corner and moving along the row, and then moving down into the next row. In the left hand diagram we try to remove a horizontal strip first, and then a vertical strip. In the right hand diagram we try to remove a vertical strip first, and then a horizontal horizontal strip. Either of these approaches provides a maximal solution.

If instead of requiring the 3×1 strip to be straight, we wanted to cut L-shaped pieces, then we can cut 19 pieces with no wastage. • Jim Randell 16 November 2019 at 12:42 pm

The published solution includes a neat way to show there cannot be more than 15 strips.

If we label the squares “a”, “b”, “c”, starting at the top right, and working across the rows, we get a layout like this: Note how the categories run along the diagonals.

Each horizontal or vertical strip of 3 squares must use exactly 1 square from each category.

The removed squares are all category “a”, which leaves only 15 “a” squares on the board (and there are 21 “b” and 21 “c” squares), so we cannot make more than 15 strips.

Of course we still need to show that we can make 15 strips, but as detailed above a greedy algorithm immediately gives us a way to cut 15 strips, so there is no need to investigate further.

This site uses Akismet to reduce spam. Learn how your comment data is processed.