Enigmatic Code

Programming Enigma Puzzles

Enigma 1367: Roman ladder

From New Scientist #2526, 19th November 2005

Enigma 1367

Your task this week is to put one of the letters I, V or X into each of the 21 squares in the ladder so that each row and column is a valid Roman numeral. All the numbers in the rows except one must be odd, and in only one case is a number in a row the same as a number in a column. If a letter appears in one row, it must appear in all rows above it.

What, from top to bottom, are the six numbers in the rows, expressed in the usual decimal form?

[enigma1367]

Advertisements

One response to “Enigma 1367: Roman ladder

  1. Jim Randell 3 December 2013 at 8:28 am

    There is already an int2roman() function in the enigma.py library. This recursive Python program solves the puzzle in 48ms.

    from collections import defaultdict
    from enigma import irange, int2roman, printf
    
    # were dealing with roman numerals from 1 to 39
    
    # record roman numerals by length, and map romans to ints
    (romans, r2i) = (defaultdict(list), dict())
    for i in irange(1, 39):
      r = int2roman(i)
      romans[len(r)].append(r)
      r2i[r] = i
    
    # create a ladder
    # rs - rows in the ladder
    # n - length of roman numeral to add
    # even - count of even numbers in the ladder
    def solve(rs, n, even):
      # are we done
      if n == 0:
        # there should be exactly one even number
        if not(even == 1): return
        # construct the columns
        cs = list(''.join(r[i] for r in rs[0:6 - i]) for i in irange(0, 5))
        # check the columns are valid roman numerals
        if not all(c in r2i for c in cs): return
        # one row also appears as a column
        if not len(set(rs) & set(cs)) == 1: return
        # output the result
        rows = tuple(r2i[r] for r in rs)
        printf("{rows} [rows={rs} cols={cs}]", rs=','.join(rs), cs=','.join(cs))
      else:
        # choose a roman numeral to add to the ladder
        for r in romans[n]:
          # letters should be a subset of the previous row
          if rs and not set(r).issubset(rs[-1]): continue
          # there can be at most one even number
          e = even + 1 - (r2i[r] % 2)
          if e < 2:
            solve(rs + [r], n - 1, e)
    
    solve([], 6, 0)
    

    Solution: The numbers in the ladder are 37, 39, 13, 3, 2 and 1.

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: