Enigmatic Code

Programming Enigma Puzzles

Enigma 1260: Latin fives

From New Scientist #2416, 11th October 2003 [link]

Enigma 120Your task today is to put one letter C, L, X, V or I into each of the 25 squares in the grid so that each row and each column (read downwards) forms a different valid Roman numeral. The sum of the numbers in the rows is to equal the sum of the numbers in the columns. Use the smallest number of Cs you can. As a hint, one of your diagonals will be a valid Roman numeral and the other will contain only one letter.

What are:

(a) the sum of the numbers in the rows (or columns); and
(b) the Arabic value of the valid diagonal?

[enigma1260]

Advertisements

2 responses to “Enigma 1260: Latin fives

  1. Jim Randell 27 January 2015 at 8:14 am

    This Python program runs in 53ms.

    from collections import defaultdict
    from enigma import irange, int2roman, roman2int, Accumulator, printf
    
    # collect 5-letter roman numerals by prefix
    romans = defaultdict(list)
    for i in irange(1, 399):
      r = int2roman(i)
      if len(r) == 5:
        for i in irange(0, 5):
          romans[r[:i]].append(r)
    
    # count the C's
    m = Accumulator(fn=min)
    
    # rs = rows
    # cs = columns
    # nr = number of rows
    # nc = number of columns
    # cr = count of C's in rows
    # cc = count of C's in columns
    def solve(rs, cs, nr, nc, cr, cc):
      if nr == 5:
        # sum the rows and columns
        rsi = tuple(roman2int(x) for x in rs)
        csi = tuple(roman2int(x) for x in cs)
        sr = sum(rsi)
        sc = sum(csi)
        if sr == sc:
          # count the C's
          m.accumulate_data(cr, rs)
          if cr == m.value:
            printf("{cr}: {rs} => {rsi} => {sr}, {cs} => {csi} => {sc}", rs=' '.join(rs), cs=' '.join(cs))
      else:
        # prefix for the next row
        pr = ''.join(x[nr] for x in cs)
        if pr not in romans: return
        # prefixes for remaining columns
        pcs = tuple(''.join(rs[j][i] for j in irange(0, nr - 1)) for i in irange(nc, 4))
        if any(x not in romans for x in pcs): return
        # choose the next row
        for r in romans[pr]:
          # make sure it's not already used
          if r in rs or r in cs: continue
          # if it exceeds the current best C count then give up
          n = r.count('C')
          if m.value is not None and cr + n > m.value: continue
          # and it's possible to complete remaining columns
          if any(p + x not in romans for (p, x) in zip(pcs, r[nc:])): continue
          # move on to the next column
          solve(cs, rs + [r], nc, nr + 1, cc, cr + n)
    
    solve([], [], 0, 0, 0, 0)
    print(m)
    

    Solution: (a) The sum of the numbers in the rows (or the columns) is 536. (b) The Arabic value of the valid diagonal is 162.

    There are 5,816 ways of filling out the grid with Roman Numerals (although any solution will also appear with the rows and columns interchanged, so the are essentially 2,908 different ways to fill out the grid).

    Four of these ways use only 3 C’s. These are the grids shown below (along with their reflections along the leading diagonal):

    Enigma 1260 - Solution

  2. Brian Gladman 29 January 2015 at 8:52 am

    I really enjoyed this one and I tried quite a few different approaches, most using the same ‘prefix’ based approach that you adopted. I tried a pure row based approach and also on based on starting with the centre row and column. But nothing matched the speed of the alternating row/column approach that you used so I ended up with a solution that closely follows your own.

    from collections import defaultdict
    
    # for storing roman numerals in range 1..399 by prefix
    rnb = defaultdict(list)
    # for the integer value of a roman numeral
    val = dict()
    # The range here is 1..399 because all roman numerals
    # outside this range have more than five characters 
    for n in range(1, 400):
      h, x = divmod(n, 100)
      s = 'C' * h
      q, r = divmod(x, 10)
      for i, t in enumerate((q, r)):
        u, v = 'XI'[i], 'LV'[i]
        if t == 9:
          s += u + 'CX'[i]
        elif t >= 5:
          s += v
          t -= 5
        if 1 <= t < 9:
          s += u + v if t == 4 else u * t
      if len(s) == 5:
        # for converting roman numerals to integers
        val[s] = n
        # store roman numerals in a map from their
        # prefixes 
        for i in range(6):
          rnb[s[:i]] += [s]
    
    # for the current minimum nomber of 'C's used
    min_c = None
    
    # fill in the grid recursively, alternating between
    # rows and columns 
    #   rows - the rows completed so far (number = nr)
    #   cols - the columns completed so far (number = nc)
    #
    def fill_in(rows, cols, nr, nc):
      global min_c
      # do we have a complete grid?
      if nr == 5:
        # exit if we have more 'C's than our current minimum
        c_cnt = ''.join(rows).count('C')
        if min_c and c_cnt > min_c:
          return 
        # check if the row and column sums are the same
        sum_rows = sum(val[x] for x in rows)
        if sum_rows == sum(val[x] for x in cols):
          # form the two diagonals
          fd = ''.join(rows[i][i] for i in range(5))
          rd = ''.join(rows[i][4 - i] for i in range(5))
          # check that one has five equal characters and
          # that the other is a valid roman numeral
          if len(set(fd)) == 1 and rd in val:
            diag = val[rd]
          elif len(set(rd)) == 1 and fd in val:
            diag = val[fd]
          else:
            return
          # return a solution if we have found one with a
          # new minimum number of 'C's
          # return the solution
          if not min_c or c_cnt <= min_c:
             min_c = c_cnt
             yield sum_rows, diag, rows
      else:
        # from the columns so far, find the first 'nr' characters
        # in row 'nr' and use this to find all roman numerals that
        # can be placed in this row
        for r in rnb[''.join(x[nr] for x in cols)]:
          rr = rows + [r]
          # exit if we have more 'C's than the current minimum
          c_cnt = ''.join(rr).count('C')
          if min_c and c_cnt > min_c:
            return
          # skip if we have a duplicate roman numeral or any of the
          # partially completed columns from row 'nr' upwards cannot
          # form a valid five character roman numeral
          if (r in rows or r in cols or
              any(''.join(x) not in rnb for x in tuple(zip(*rr))[nr:])):
            continue
          # now switch rows and columns and move to next row/column
          yield from fill_in(cols, rr, nc, nr + 1)
    
    for sum_rows, diag, rows in fill_in([], [], 0, 0):
      print(sum_rows, diag, rows)
    

    But there are (again!) some practical differences as I am not convinced that the checks you make on lines 36 and 39 are needed because we have not yet added another row (column) and we have already checked that the columns (rows) can be completed from this position when we added the previous row (column). I certainly find the same 5816 solutions without these checks (for a modified solver that doesn’t check the diagonals or the numbers of ‘C’s) although that is no guarantee that my logic here is correct.

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: