Enigmatic Code

Programming Enigma Puzzles

Enigma 1204: Small fitogether

From New Scientist #2360, 14th September 2002 [link]

I secretly write the 3×3 square:

Enigma 1204

I then tell you that the horizontal rows of my square were 231, 312 and 123 and the vertical columns 213, 321 and 132, in some order. If you can work out what my square was then it is called a “fitogether”. (If you check you will see this square is not a fitogether).

Similarly, I can start with any n×n square of numbers where each row and each column contains 1, 2, 3, … n. I tell you the rows and columns in some order and you try to work out my square; if you can, it is called a fitogether. We only consider n if it is at least 2.

The value of a square of numbers is the number obtained by writing the the rows one after the other in order with the top row at the left. For example, the square above has value 312231123.

Find the bottom row of the fitogether with the smallest value.

[enigma1204]

Advertisements

One response to “Enigma 1204: Small fitogether

  1. Jim Randell 8 September 2015 at 7:48 am

    This Python 3 program generates Latin Squares of increasing dimensions, until it finds a size with “fitogethers”, and then finds the smallest one. It runs in 7.5s.

    from collections import defaultdict
    from itertools import count
    from enigma import irange, Accumulator, printf
    
    # generate permutations of sequence <s>
    # exceptions in <xs>
    # permutation so far in <p>
    def permute(s, xs, p=()):
      # are we done?
      if not s:
        yield p
      else:
        # choose an element
        for (i, e) in enumerate(s):
          if e not in xs[0]:
            yield from permute(s[:i] + s[i + 1:], xs[1:], p + (e,))
    
    
    # generate latin squares of size <n> from sequence <s>
    # rows so far are in <rs>
    def squares(n, s, rs):
      # are we done?
      if len(rs) == n:
        yield rs
      else:
        # possible next rows
        xs = (tuple(zip(*rs)) if rs else [()] * n)
        for r in permute(s, xs):
          yield from squares(n, s, rs + [r])
    
    
    # consider increasing n
    for n in count(2):
      printf("[trying n={n} ...]")
    
      # d maps rows + columns to square
      d = defaultdict(list)
    
      r = tuple(irange(1, n))
      for rs in squares(n, r, []):
        k = tuple(sorted(rs)) + tuple(sorted(zip(*rs)))
        d[k].append(rs)
      printf("[n={n}: found {t} squares]", t=sum(len(v) for v in d.values()))
    
      # find minimum unique squares
      m = Accumulator(fn=min)
      for (k, vs) in d.items():
        if len(vs) == 1:
          m.accumulate(vs[0])
    
      # have we found a solution?
      if m.value is not None:
        printf("n={n} v={m.value}")
        break
    

    Solution: The bottom row of the fitogether with the smallest value is 5, 3, 1, 2, 4.

    The 5×5 “fitogether” in question is shown below:

    Enigma 1204 - Solution

    Fortunately we don’t have to search very far to find a fitogether, as this program becomes unwieldy above n=5.

    The number of Latin Squares LS(n) gets quite big quite quickly as n increases (OEIS A002860):

    LS(2) = 2
    LS(3) = 12
    LS(4) = 576
    LS(5) = 161,280
    LS(6) = 812,851,200
    LS(7) = 61,479,419,904,000
    LS(8) = 108,776,032,459,082,956,800

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: