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]

Advertisements

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
    
    # determine adjacent squares
    def adjacent(N, p):
      y, x = divmod(p - 1, N)
      adj = set()
      if x > 0: adj.add(p - 1)
      if x < N - 1: adj.add(p + 1)
      if y > 0: adj.add(p - N)
      if y < N - 1: adj.add(p + N)
      return adj
    
    # 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:
          ps.add(tuple(sorted(ss)))
        return
    
      # add in an adjacent square
      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:
        s.add(tuple(sorted(ss)))
        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.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: