# Enigmatic Code

Programming Enigma Puzzles

## Enigma 312: Six-stamp sheet

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 N by tearing out a connected set 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 N as big as possible, and state what N is.

[enigma312]

### 2 responses to “Enigma 312: Six-stamp sheet”

1. Jim Randell 25 September 2015 at 8:55 am

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.

```from collections import Counter
from itertools import permutations
from enigma import irange, Accumulator, printf

# we represent the grid as:
#
#   0 1 2
#   3 4 5

stamps = set(irange(0, 5))

# then the adjacency list is:
set((1, 3)), # 0
set((0, 2, 4)), # 1
set((1, 5)), # 2
set((0, 4)), # 3
set((1, 3, 5)), # 4
set((2, 4)), # 5
)

# find all possible blocks of adjacent stamps
def block(b, r):
if b in blocks: return
r.append(b)
for i in stamps:
if i in b: continue
block(b.union([i]), r)

blocks = []
for i in stamps:
block(set([i]), blocks)

# number of different blocks
B = len(blocks)
printf("number of blocks = {B}")

# determine what values can be made from stamps <vs>
# without using the stamps in indices <zs>
def values(vs, zs):
return Counter(sum(vs[i] for i in s) for s in blocks if not zs.intersection(s))

# decompose <t> into <n> numbers
# m - smallest allowable number
def decompose(t, n, m=1, s=()):
if n == 1:
if not(t < m):
yield s + (t,)
else:
for x in irange(m, t // 2):
yield from decompose(t - x, n - 1, x, s + (x,))

# update <vs> to insert values from <s> into spaces <fs>
def update(vs, fs, s):
vs = list(vs)
for (i, v) in zip(fs, s):
vs[i] = v
# return the new values
return vs

# vs - stamps, 0 = unassigned
# c - Counter of values that can be made from <vs>
# zs - unassigned indices in <vs>
# r - Accumulator object for results
def solve(vs, c, zs, r):
# find the smallest value not in c
for n in irange(1, B + 1):
if n not in c: break
# are we done?
if not zs:
N = n - 1
# record N
r.accumulate(N)
if r.value == N: printf("N={N} {vs}")
return
# add in some new values, so we can make n
for k in irange(n, 1, step=-1):
# make k from j numbers
for j in irange(1, len(zs)):
for s in decompose(k, j, 1):
# assign the values to j of the unassigned spaces
for zs1 in permutations(zs, j):
# check n is now a possible value
vs2 = update(vs, zs1, s)
zs2 = zs.difference(zs1)
c2 = values(vs2, zs2)
if n in c2:
solve(vs2, c2, zs2, r)

r = Accumulator(fn=max)

# try with 1 in a corner position (0) and in an edge position (1)
for i in (0, 1):
vs = [0] * 6
vs[i] = 1
zs = set(i for (i, v) in enumerate(vs) if v == 0)
solve(vs, values(vs, zs), zs , r)

printf("max N = {r.value}")
```

Solution: The maximum values for N is N=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:

8 = (8) = (2, 6)
17 = (2, 15) = (1, 2, 6, 8)
18 = (1, 2, 15) = (4, 6, 8)
23 = (8, 15) = (2, 6, 15)

For the second arrangement the repeated values are:

5 = (5) = (2, 3)
10 = (2, 8) = (2, 3, 5)
11 = (1, 2, 8) = (1, 2, 3, 5)
22 = (5, 17) = (2, 3, 17)

2. hakank 26 September 2015 at 11:31 pm

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.

```import cp,util.

main => go.

go =>
Rows = 2,
Cols = 3,
N = Rows*Cols,
Graph=connected_cells(Rows,Cols),
cl_facts(Graph), % make p(From,To) available

All = [],
Table = [], % for table_in/2
foreach(I in 1..2**(N)-1)
Bin = [J.to_integer() : J in I.to_binary_string()].reverse(),
C = [J : J in 1..Bin.len, Bin[J]=1],
OK = sum([1: K in C, L in C, K != L, (p(K,L) ; member(T,C), p(K,T), p(T,L))]),
if OK >= (C.len*C.len-1) div 2 then
All := All ++ [C],
Bin2 = ([0:_ in 1..N-Bin.len] ++ Bin.reverse()).to_array(),
Table := Table ++ [Bin2]
end
end,
MaxM = _,
OK = true,
foreach(M in 5..100, OK == true)
printf("m=%d ", M),
stamps(Rows,Cols,Table,M, X) ->
println(x=X), MaxM := M
;
OK := false
end,

println(maxM=MaxM),

% println("\nOptimal solutions:"),
% Sols = findall(X, stamps(Rows,Cols,Table,MaxM, X)).sort_remove_dups(),
% foreach(Sol in Sols) println(Sol) end,
nl.

% CP approach using table_in/2 to handle the valid stamp combinations
stamps(Rows,Cols,Table, M, X) =>

N = Rows*Cols,
X = new_array(Rows,Cols),
X :: 1..M div 2,
X1 = X.vars(),
Y = new_array(M,N),
Y :: 0..1,

foreach(Num in 1..M)
table_in(Y[Num],Table),
Num #= sum([Y[Num,I]*X1[I] : I in 1..N])
end,
lex2(X),
solve(\$[min,split],X++Y).

% symmetry breaking
lex2(X) =>
Len = X[1].length,
foreach(I in 2..X.length)
lex_le([X[I-1,J] : J in 1..Len], [X[I,J] : J in 1..Len])
end.

% create the graph
connected_cells(Rows,Cols) = Graph =>
V = -1..1,
Graph = [\$p(From,To) : I in 1..Rows, J in 1..Cols, A in V, B in V,
I+A in 1..Rows,J+B in 1..Cols, abs(A+B)=1, From = (I-1)*Cols + J,
To = (I+A-1)*Cols + J+B].

```