### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,183)
- misc (2)
- project euler (2)
- puzzle (46)
- site news (46)
- tantalizer (49)
- teaser (3)

### Site Stats

- 184,818 hits

Advertisements

Programming Enigma Puzzles

5 June 2017

Posted by on **From New Scientist #2268, 9th December 2000** [link]

George is building a patio, which will be covered using one-foot-square concrete slabs of seven different colours. He has divided the rectangular patio into seven rectangular zones, without any gaps.

Each zone will be covered by slabs of one colour, with five different colours appearing around the perimeter of the patio, and four different colours at the corners. The seven rectangular zones are all different shapes, but all have the same perimeter, which is less than 60 feet.

What are the dimensions of the patio that George is building?

This puzzle is referenced by **Enigma 1221**.

[enigma1112]

Advertisements

%d bloggers like this:

See also:

Enigma 17,Enigma 1251.At first I missed the fact that the seven zones were rectangular, and was worried that this was going to be quite a tricky problem to solve. Once I realised that the zones were rectangular it seemed like a more tractable problem, which can be solved using rectangle packing.

This Python 3 program runs in 2.17s (or 1.06s using PyPy).

Run:[ @repl.it ]Solution:George’s patio is 26 feet by 32 feet.The seven rectangular areas are: 2×25, 3×24, 5×22, 6×21, 7×20, 8×19, 13×14. Each having a perimeter of 54 feet.

Here’s a diagram of how the rectangular areas fit together:

The program considers 15,705 different collections of rectangles and grids, which would take a long time of we passed each of them to the

pack()function directly, and we would have to examine the results to check that the results are in the required configuration (i.e. with five different regions making up the perimeter, and four of these in the corners). Instead I use this information to pack five rectangles along the perimeter, and if that is possible then we only have two remaining rectangles to fit into the central hole (which I do use the rectangle packer for, although it is a bit of overkill).This Enigma proved an ideal candidate for MinZinc, consisting mainly of geometrical constraints

to check the packing of the rectangles. It was also quite fast – 129 msec in Geocode (bundled) and relatively short code. I found the perimeter of the seven rectangles to be 54 ft.

I used the diagram Jim included in the Enigma 1221, as it had the same requirements for colours.

Labelling the rectangles from 1 to 7 (corresponds with A to G in my program) we can get quite a compact MiniZinc model.

On my machine this runs in 96ms with the [[

mzn-g12fd]] solver (and only 98ms if [[mzn-g12fd -a]] is used).