### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,123)
- misc (2)
- project euler (2)
- puzzle (31)
- site news (43)
- tantalizer (31)
- teaser (3)

### Site Stats

- 168,282 hits

Programming Enigma Puzzles

25 September 2015

Posted by on **From New Scientist #1460, 13th June 1985** [link]

They are now printing stamp-books with stamps of different values on the same sheet. Let us take this a stage further, and design a sheet of 3 × 2 stamps, so that you can make up a postage of any whole number of pence from 1 up to

Nby tearing out aconnectedset of one or more stamps.“Connected” means edge-connected, not just corner-touching, so that, for instance, the sheet illustrated achieves only

N=5, since neither 4+2 nor 5+1 is a connected set, and so 6 is impossible.Make a sketch showing how to make

Nas big as possible, and state whatNis.

[enigma312]

Advertisements

%d bloggers like this:

See also:

Enigma 270,Enigma 1596.In Enigma 1596 we saw that N=36 is possible, and as there are 40 possible blocks the upper bound is N=40.

This Python 3 program is adapted from my recursive solution to Enigma 270. It finds the possible arrangement of blocks of stamps, and then recursively assigns stamps to the grid to find the maximum possible value for N. It runs in 17.2s.

Solution:The maximum values forNisN=36.There are two different ways of achieving this, shown below (along with their reflections):

As there are 40 ways of making blocks of stamps, some denominations must be repeated.

For the first arrangement the repeated values are:

For the second arrangement the repeated values are:

A solution in Picat using a combination of logic programming (e.g. member/2 for building the valid configurations), plain iterative programming, and Constraint Programming (for solving the specific instances): http://hakank.org/picat/six_stamp_sheet.pi

It find max M=36 in 2.7s.