S2T2

Jim Randell 5:22 pm on 21 February 2020 Permalink Reply
Tags: by: Victor Bryant ( 139 )   

• 

  Jim Randell 8:55 pm on 21 February 2020 Permalink | Reply

  (See also: Enigma 321).

  There are only a limited number of 1-sided, 1-, 2-, 3-, 4-onimoes, and as the pieces are all different this gives us an upper limit to the total area of the squares.

  It is fairly straightforward to narrow the required answer down to one of two values on the back of an envelope. But it is fun to make a constructive solution from scratch, so here goes…

  The following program looks for possible total areas that can be made into multiple different squares.

  We then select pieces with the appropriate area and attempt to construct the different sets of squares.

  This Python 3 program is adapted from my initial solution to Enigma 321. It’s not hugely fast, but it does solve the problem in 19s.

  from itertools import product
  from copy import deepcopy
  from enigma import (irange, inf, subsets, diff, first, printf)
  
  # possible pieces in all possible orientations
  pieces = [
  
    # 1 square - 1x1 block ["O1"]
    (
      [(0, 0)],
    ),
  
    # 2 squares - 2x1 block ["I2"]
    (
      [(0, 0), (1, 0)],
      [(0, 0), (0, 1)],
    ),
  
    # 3 squares - linear, 3x1 block ["I3"]
    (
      [(0, 0), (1, 0), (2, 0)],
      [(0, 0), (0, 1), (0, 2)],
    ),
  
    # 3 squares - L shape ["V3"]
    (
      [(0, 0), (1, 0), (1, 1)],
      [(1, 0), (0, 1), (1, 1)],
      [(0, 0), (1, 0), (0, 1)],
      [(0, 0), (0, 1), (1, 1)],
    ),
  
    # 4 squares - 4x1 block, ["I4"]
    (
      [(0, 0), (1, 0), (2, 0), (3, 0)],
      [(0, 0), (0, 1), (0, 2), (0, 3)],
    ),
  
    # 4 squares - square, 2x2 block ["O4"]
    (
      [(0, 0), (1, 0), (0, 1), (1, 1)],
    ),
  
    # 4 squares - T shape ["T4"]
    (
      [(1, 0), (0, 1), (1, 1), (2, 1)],
      [(0, 0), (0, 1), (1, 1), (0, 2)],
      [(0, 0), (1, 0), (2, 0), (1, 1)],
      [(1, 0), (0, 1), (1, 1), (1, 2)],
    ),
  
    # and now the chiral ones
  
    # 4 squares - Z shape ["Z4"]
    (
      [(0, 1), (1, 1), (1, 0), (2, 0)],
      [(0, 0), (0, 1), (1, 1), (1, 2)],
    ),
  
    # 4 squares - S shape ["Z4'", "S4"]
    (
      [(0, 0), (1, 0), (1, 1), (2, 1)],
      [(1, 0), (1, 1), (0, 1), (0, 2)],
    ),
  
    # 4 squares - L shape ["L4"]
    (
      [(0, 0), (0, 1), (0, 2), (1, 2)],
      [(0, 0), (1, 0), (2, 0), (2, 1)],
      [(1, 0), (1, 1), (1, 2), (0, 2)],
      [(0, 0), (0, 1), (1, 1), (2, 1)],
    ),
  
    # 4 squares - L shape ["L4'", "R4"]
    (
      [(0, 0), (1, 0), (1, 1), (2, 1)],
      [(0, 1), (1, 1), (2, 1), (2, 0)],
      [(0, 0), (0, 1), (0, 2), (1, 2)],
      [(0, 0), (0, 1), (1, 0), (2, 0)],
    ),
  ]
  
  # try to place piece <p> at <x>, <y> in grid <grid> of dimensions <a>, <b>
  # using label <n>
  def place(p, y, x, n, grid, a, b):
    g = deepcopy(grid)
    for (dy, dx) in p:
      (py, px) = (y + dy, x + dx)
      try:
        q = g[py][px]
      except IndexError:
        return None
      if q is not None:
        return None
      g[py][px] = n
    return g
  
  # try to fit pieces <ps> into grid <grid> of dimensions <a>, <b>
  def fit(ps, n, grid, a, b):
    if not ps:
      yield grid
    else:
      # choose a piece
      for p in ps[0]:
        # try to place the piece at x, y
        for (y, x) in product(irange(0, a - 1), irange(0, b - 1)):
          g = place(p, y, x, n, grid, a, b)
          if g is not None:
            yield from fit(ps[1:], n + 1, g, a, b)
  
  # select at least <n> pieces from <ps> with a total area of <k>
  def select(ps, k, n):
    for i in irange(n, len(ps)):
      f = 0
      for s in subsets(ps, size=i):
        t = sum(len(p[0]) for p in s) 
        if t == k:
          yield s
        if not (t > k):
          f += 1
      if f == 0: break
  
  # fit the pieces <ps> into squares with sides <squares>
  def fit_squares(ps, squares, ss=[]):
    # are we done?
    if not ps:
      yield ss
    else:
      # try to fill the next square
      s = squares[0]
      # choose pieces with the right area
      for fs in select(ps, s * s, 2):
        # create an s x s empty grid and assemble the pieces in it
        grid = list([None] * s for _ in irange(1, s))
        for g in fit(fs, 1, grid, s, s):
          # fit the remaining squares
          yield from fit_squares(diff(ps, fs), squares[1:], ss + [g])
  
  # find an example fit of the pieces <ps> into each of the list of squares <ss>
  def solve(ps, ss):
    fs = list()
    for s in ss:
      f = first(fit_squares(ps, s))
      if not f: return
      fs.extend(f)
    return fs
  
  
  # express n as a sum of increasing squares (minimum: m)
  def sum_of_squares(n, m=1, s=[]):
    if n == 0:
      if len(s) > 1:
        yield s
    else:
      for i in irange(m, inf):
        i2 = i * i
        if i2 > n: break
        yield from sum_of_squares(n - i2, i + 1, s + [i])
  
  # consider increasing total area of the squares
  T = sum(len(p[0]) for p in pieces)
  for n in irange(4 + 9, T):
    sqs = list(sum_of_squares(n, 2))
    if len(sqs) < 2: continue
    printf("total area = {n} -> squares = {sqs}")
  
    # choose some of the squares
    for ss in subsets(sqs, min_size=2):
  
      # make a set of polyominoes with the appropriate total area
      for ps in select(pieces, n, 2 * max(len(s) for s in ss)):
  
        # try and fit them into the squares
        fs = solve(ps, ss)
        if fs is None: continue
  
        # output solution (number of pieces), and constructed squares
        printf("  {m} pieces", m=len(ps))
        for (s, f) in zip(ss, fs):
          printf("  {s} -> {f}")
        printf()
  

  There is only a single candidate area that can be expressed as the sum of different, non-unit squares in multiple ways.

  There are two sets of pieces that can be assembled into the required squares, but they both have the same number of pieces (one set is a mirror image of the other), and so this gives the answer.

  Solution: There are 9 jigsaw pieces.

  The 9 pieces have a total area of 29, and can be assembled into a set of (2×2, 3×3, 4×4) squares, or a set of (2×2, 5×5) squares.

  Here is a solution using the 9 pieces: O1, I2, I3, V3, I4, O4, L4, L4′, Z4.

  

  Note that we can’t turn the pieces over, so L4 and its mirror image (L4′) are different pieces (you cannot rotate one of them to give the same shape as the other), as are Z4 and its mirror image (Z4′).

  And here is another solution using the 9 pieces: O1, I2, I3, V3, I4, O4, L4, L4′, Z4′.

  

  The second set uses Z4′ instead of Z4. These pieces are mirror images of each other, so any solution for the first set also gives a solution for the second set, by reflecting it.

  There are no further solutions, even if we were are allowed to have squares that are the same size.

  It occurred to me that the squares are the same sizes as the collection of Rubik’s cubes I have available to me, so here are the diagrams made with cubes:

  

  (I’ve only got one 2×2×2 cube, so it has to be shared between the sets of squares).

  LikeLike

  • 

    Jim Randell 10:55 am on 23 February 2020 Permalink | Reply

    I encapsulated the code that deals with polyominoes into a separate file [[ polyominoes.py ]] that can be used to solve this puzzle (and Enigma 321), and I switched to using Knuth’s Algorithm X, rather than the simplistic [[ fit() ]].

    So the following program runs in a more reasonable 858ms.

    Run: [ @repl.it ]

    import polyominoes
    from enigma import irange, inf, subsets, diff, first, printf
    
    # select at least <n> pieces from <ps> with a total area of <k>
    def select(ps, k, n):
      for i in irange(n, len(ps)):
        f = 0
        for s in subsets(ps, size=i):
          t = sum(len(p[0]) for p in s) 
          if t == k:
            yield s
          if not(t > k):
            f += 1
        if f == 0: break
    
    # fit the pieces <ps> into squares with sides <squares>
    def fit_squares(ps, squares, ss=[]):
      # are we done?
      if not ps:
        yield ss
      else:
        # try to fill the next square
        s = squares[0]
        # choose pieces with the right area
        for fs in select(ps, s * s, 2):
          # create an s x s empty grid and assemble the pieces in it
          for g in polyominoes.fit(fs, s, s):
            # fit the remaining squares
            yield from fit_squares(diff(ps, fs), squares[1:], ss + [g])
    
    # find an example fit of the pieces <ps> into each of the list of squares <ss>
    def solve(ps, ss):
      fs = list()
      for s in ss:
        f = first(fit_squares(ps, s))
        if not f: return
        fs.extend(f)
      return fs
    
    
    # express n as a sum of increasing squares (minimum: m)
    def sum_of_squares(n, m=1, s=[]):
      if n == 0:
        if len(s) > 1:
          yield s
      else:
        for i in irange(m, inf):
          i2 = i * i
          if i2 > n: break
          yield from sum_of_squares(n - i2, i + 1, s + [i])
    
    # available pieces, and total area
    pieces = polyominoes.shapes("O1 I2 I3 V3 O4 I4 T4 Z4 Z4' L4 L4'", "ONE_SIDED")
    
    # consider increasing total area of the squares
    T = sum(len(p[0]) for p in pieces)
    for n in irange(4 + 9, T):
      sqs = list(sum_of_squares(n, 2))
      if len(sqs) < 2: continue
      printf("total area = {n} -> squares = {sqs}")
    
      # choose some of the squares
      for ss in subsets(sqs, min_size=2):
    
        # make a set of polyominoes with the appropriate total area
        for ps in select(pieces, n, 2 * max(len(s) for s in ss)):
    
          # try and fit them into the squares
          fs = solve(ps, ss)
          if fs is None: continue
    
          # output solution (number of pieces), and constructed squares
          printf("  {m} pieces", m=len(ps))
          for (s, f) in zip(ss, fs):
            printf("  {s} -> {f}")
          printf()
    

    LikeLike

• 

  Robert Brown 12:57 pm on 25 February 2020 Permalink | Reply

  This teaser reminds me of enigma 1491 (not on your site?) from 2008. Box of tiles 1×3, 2×4, 3×5 etc. Takes tiles out in order, one at a time, and tries to make a rectangle. Required to find a) smallest possible rectangle & b) next largest. Everyone could all do a) by hand, but b) needed a fairly complex program. Ongoing discussions gradually simplified the program algorithm, and ultimately we got it down to a series of steps that could be followed manually – could be done in about 10 minutes. It’s all on the newenigma site, but you need a user name & password to log in!

  LikeLike

• 

  Robert Brown 1:03 pm on 25 February 2020 Permalink | Reply

  Sorry, I misquoted that slightly – should say ‘required to find how many tiles for smallest rectangle’ (which of course has no gaps or overlaps)

  LikeLike

  • 

    Jim Randell 2:20 pm on 25 February 2020 Permalink | Reply

    I remember Enigma 1491. It was a fun puzzle. My notes for it are here [ @enigmaticcode ].

    When it was originally published in 2008 I wrote a Perl program to solve it, but that took 50 minutes to run. So while it was running I coded up the same algorithm in C, and that ran in 11 seconds.

    When I came to add the puzzle to the Enigmatic Code site in 2012 I wrote a Python program using a slightly different approach, and found that it ran in 9.2s. Now the same program runs in just 2.5s (probably due to improvements in the PyPy environment — I’m still using the same laptop I was using in 2012).

    LikeLike