Enigmatic Code

Programming Enigma Puzzles

Enigma 1251: Jigsaw of rectangles

From New Scientist #2407, 9th August 2003 [link]

It is day 10 of Frances’s holiday and she is cutting rectangles out of cardboard. She is cutting out every rectangle with whole number sides and area at most 10.

When she has finished she has 15 rectangles, which are:

1×1, 1×2, 1×3, 1×4, 2×2, 1×5, 1×6, 2×3, 1×7, 1×8, 2×4, 1×9, 3×3, 1×10, 2×5.

Frances then tries to fit the 15 pieces together to make a square, with no overlapping pieces and no holes. She finds it is impossible. In fact she tried a similar thing on day 2 of her holiday with all rectangles of area at most 2, on day 3 with area at most 3, …, on day 9 with area at most 9; on each day she found it was impossible to make a square.

Frances continues through her holiday, on day 11 with area at most 11, on day 12 with area at most 12, and so on. Each day she finds it impossible to make a square until one memorable day when she finds it is possible.

Which day of the holiday was that memorable day?

[enigma1251]

Advertisements

3 responses to “Enigma 1251: Jigsaw of rectangles

  1. Jim Randell 4 March 2015 at 7:34 am

    It’s straightforward to find on what day it may be possible to assemble the rectangles into a square, which is what this program does. It runs in 34ms.

    from itertools import count
    from enigma import divisor_pairs, is_square, printf
    
    # record rectangles and total area
    (rs, A) = ([], 0)
    
    # consider increasing maximum areas
    for n in count(1):
      # add in rectangles of area n
      for (p, q) in divisor_pairs(n):
        rs.append((p, q))
        A += n
    
      # check to see if the total area is a square number
      s = is_square(A)
      if s is not None:
        printf("n={n}, A={A}, rs=({rs} rectangles), s={s}", rs=len(rs))
        if n > 1: break
    

    Solution: The memorable day was the 43rd day of the holiday.

    There are 88 rectangles and they would make a 46×46 square.

    The program finds when it may be possible to assemble the rectangles into a square, but doesn’t actually show that it is possible.

    I tried to use a variation of my program for Enigma 17 to find a packing of the rectangles into the square, but it took too long.

    Then I discovered that Eric Huang, one of the authors of several papers on Optimal Rectangle Packing, has made his C++ rectangle packing code available at [ https://code.google.com/p/rectpack/ ], so I downloaded it, got it to compile, and give it this packing problem to chew on, but it didn’t find a solution in a reasonable time either.

    Nevertheless, here is an arrangement that shows it is possible.

    Enigma 1251 - Solution

    (and of course any rectangular region of this solution that consists of two or more rectangles can be rearranged to give a further solution, and chunks that form a block the full width (or height) of the square can be moved)).

    A heuristic packer may find a solution, or if you sneakily feed the rectangles to my packer in the order and orientation given above it will find a solution. But neither of these is really satisfactory.

    If you leave the program above running you will find that the days where the total area of all rectangles is a square number follow the following sequence:

    1, 43, 169, 227, 735, 10664, 14702, 78159, 5431210, … (A083357 in OEIS).

    The sides of the corresponding squares are:

    1, 46, 205, 281, 992, 16808, 23544, 134943, 10917412, … (A083358 in OEIS).

    • Jim Randell 18 March 2015 at 9:59 am

      Eric Huang’s optimal rectangle packer (rectpack) will pack the top 20 rows of the solution given above instantaneously. I’ve been running it over the bottom 26 rows (using a Virtual Machine, so I can run it overnight and then suspend it during the day when I want to use my laptop) for a while and it has come up with an alternative packing, after using 10d09h52m56s (just short of 250 hours) of CPU time.

      Here’s the packing it found:

      Enigma 1251 - rectpack lower

      Now I’ll try it on the full problem, and report back if it finds a packing.

  2. Brian Gladman 4 March 2015 at 10:10 pm

    Here is my version, extended to give the sequences that Jim describes above. It uses a standard number theory function that is implemented in my number theory library (which is available at http://ccgi.gladman.plus.com/wp/?page_id=1500 – you will need the latest version as earlier versions have an issue that will affect this enigma).

    from itertools import count
    from number_theory import tau
    
    fs = '{:>8d} cards (max area {:>7d}) in a square of side {:>8d}, area {:>16d}'
    
    # for the area of the square and the number of rectangles used to fill it
    area = rects = 0
    # the area of the cards being added in this round
    for max_area in count(1):
      # use the number theory function tau(n) function to compute the number of
      # different integer sided rectangles of area max_area (i.e. the number of
      # divisor pairs for max_area)
      nr = (tau(max_area) + 1) // 2
      # add the number of rectangles and their area to the running totals
      rects += nr
      area += nr * max_area
      # check for a square value
      sq = int(area ** 0.5 + 0.5)
      if sq ** 2 == area:
        # output the results up to a maximum value
        print(fs.format(rects, max_area, sq, area))
        # this will take several minutes
        if max_area >= 5431210:
          break
    

    As implemented the program will take several minutes to produce:

           1 cards (max area       1) in a square of side        1, area                1
          88 cards (max area      43) in a square of side       46, area             2116
         455 cards (max area     169) in a square of side      205, area            42025
         641 cards (max area     227) in a square of side      281, area            78961
        2497 cards (max area     735) in a square of side      992, area           984064
       50331 cards (max area   10664) in a square of side    16808, area        282508864
       71743 cards (max area   14702) in a square of side    23544, area        554319936
      446467 cards (max area   78159) in a square of side   134943, area      18209613249
    42533284 cards (max area 5431210) in a square of side 10917412, area  119189884777744
    

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: