### Random Post

### Recent Posts

### Recent Comments

Jim Randell on Puzzle #52: Bus change | |

Jim Randell on Enigma 967: Prime cubes | |

GeoffR on Enigma 1707: Making progr… | |

Jim Randell on Enigma 1707: Making progr… | |

Jim Randell on Tantalizer 409: Fe, Fi, Fo,… |

### Archives

### Categories

- article (11)
- enigma (1,364)
- misc (4)
- project euler (2)
- puzzle (90)
- puzzle# (47)
- site news (58)
- tantalizer (92)
- teaser (7)

### Site Stats

- 231,891 hits

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.

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.

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.