# 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.

(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:

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
```