# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1505: Brief N-counter

From New Scientist #2667, 2nd August 2008

I drew a grid of squares with N rows and N columns and I wrote the numbers 1, 2, …, N² in the squares in the natural order (left to right; 1 to N in the top row, N+1 to 2N in the next, and so on).

I then cut up the grid into N pieces of various shapes, with each piece consisting of N squares. On each piece the total of the N numbers is less than 200 and is not divisible by 2, 3 or 5.

What is N?

[enigma1505]

### One response to “Enigma 1505: Brief N-counter”

1. Jim Randell 15 October 2012 at 5:38 pm

I found it was fairly easy to write a program that gets the right answer, even if the program is incorrect. But I wanted to find all possible solutions, and came up with this recursive solution. It first finds how many possible pieces there are that satisfy the conditions, then finds subsets of these pieces that cover the board. It’s not as fast as I would like – it runs in 1m55s – but it does find all 203 solutions. (A similar approach that stops after it finds the first solution for each N runs in under 1s).

```from enigma import irange, flatten, printf

# the smallest value of N squares containing the N^2 square is the right hand
# strip of squares.

# which sums: N + 2N + 3N + ... + N^2
# = N(1 + 2 + 3 + ... + N)
# = N * N*(N+1)/2
# as this sum is less than 200, this means:
# N^3 - N^2 < 400
# so N < 8

y, x = divmod(p - 1, N)

# find acceptable contiguous pieces
# N - size of the grid
# n - size of pieces we're looking for
# ss - squares in the piece
# ps - pieces we've accumulated
def pieces(N, n, ss, ps):
# are we done?
if len(ss) == n:
s = sum(ss)
if s < 200 and s % 2 > 0 and s % 3 > 0 and s % 5 > 0:
return

for s in flatten(adjacent(N, s) for s in ss):
if s in ss: continue
pieces(N, n, ss.union([s]), ps)

# find sets of pieces that cover the set
# ps - pieces we are considering
# n - number of elements to cover
# ss - pieces we have chosen
# c - elements covered so far
# s - count the solutions
def cover(ps, n, ss, c, s):
# are we done?
if len(c) == n:
return
# what non-overlapping pieces remain?
ps = list(p for p in ps if not c.intersection(p))
for i, p in enumerate(ps):
cover(ps[i+1:], n, ss.union([p]), c.union(p), s)

# display a solution
def display(N, ss):
printf("\nN={N}")
grid = [''] * (N * N + 1)
sums = []
for c, i in enumerate(ss):
label = chr(65 + c)
for j in i:
grid[j] = label
sums.append(': '.join((label, str(sum(i)))))
grid = ''.join(grid[1:])
for i in range(N):
print(grid[i * N : (i + 1) * N])
print(', '.join(sums))

# attempt solutions for N = 2 to 7
for N in irange(2, 7):
N2 = N * N
ps = set()
for i in irange(1, N2):
# accumulate pieces containing square i
pieces(N, N, set([i]), ps)

s = set()
# check each number is included in some piece
if len(set(flatten(ps))) == N2:
# find subsets of the pieces that cover the set
cover(list(ps), N2, set(), set(), s)

# display (any) solutions
for i in s:
display(N, i)

# a summary of the solutions
printf("N={N}: {p} pieces, {s} solutions", p=len(ps), s=len(s))
```

Solution: N = 6.