Enigmatic Code

Programming Enigma Puzzles

Puzzle #29: How many strips?

From New Scientist #3255, 9th November 2019 [link] [link]

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 = [0] * 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.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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

%d bloggers like this: