Enigmatic Code

Programming Enigma Puzzles

Enigma 1225: Rows are columns

From New Scientist #2381, 8th February 2003 [link]

First draw a chessboard. Now number the horizontal rows 1, 2, …, 8 from top to bottom and number the vertical columns 1, 2, …, 8 from left to right. You have to put a whole number in each of the sixty-four squares, subject to the following:

1. No two rows are exactly the same.
2. Each row is equal to one of the columns, but not to the column with the same number as the row.
3. If N is the largest number you write on the chessboard then you must also write 1, 2, …, N−1 on the chessboard.

The sum of the sixty-four numbers you write on the chessboard is called your total.

What is the largest total you can obtain?

See also Enigma 1248.

[enigma1225]

Advertisements

4 responses to “Enigma 1225: Rows are columns

  1. Jim Randell 16 June 2015 at 8:12 am

    A similar problem was published as Enigma 1248, so, having already solved that I was able to adapt my code to solve this problem.

    This Python program runs in 664ms.

    from collections import Counter
    from itertools import permutations
    from enigma import irange, Accumulator, chunk, printf
    
    # merge <s> with <t> in grid <g>
    def merge(g, s, t):
      for (i, x) in enumerate(g):
        if x == s:
          g[i] = t
    
    # create an N x N grid with specified rows and columns equated
    # rcs - list of (r, c) (0-indexed)
    def grid(N, rcs):
      # label the squares
      n = 1
      # make the grid
      g = [0] * (N * N)
      # equate the rows and columns
      for (r, c) in rcs:
        for i in irange(0, N - 1):
          (ri, ci) = (r * N + i, c + N * i)
          if g[ri] == 0:
            if g[ci] == 0:
              # allocate a new label
              g[ri] = g[ci] = n
              n += 1
            else:
              g[ri] = g[ci]
          else:
            if g[ci] == 0:
              g[ci] = g[ri]
            elif g[ci] != g[ri]:
              # merge the two labels
              merge(g, max(g[ri], g[ci]), min(g[ri], g[ci]))
      return g
    
    
    import sys
    N = (8 if len(sys.argv) < 2 else int(sys.argv[1]))
    
    r = Accumulator(fn=max)
    
    # choose a permutation
    rs = tuple(irange(0, N - 1))
    for cs in permutations(rs):
      if any(cs[i] == i for i in rs): continue
      # generate the grid
      g = grid(N, zip(rs, cs))
      # no two rows are the same
      if len(set(chunk(g, N))) != N: continue
      # count the remaining occurrences
      c = Counter(g)
      # the maximum sum uses the the numbers 1 to N by occurrence order
      m = sum(i * n for (i, n) in enumerate(sorted(c.values()), start=1))
      r.accumulate_data(m, g)
      if r.value == m:
        printf("[m={m} {g}]")
    
    printf("max = {r.value}")
    

    Solution: The largest possible total for an 8×8 grid is 544.

    Here’s an example layout:

    Enigma 1225 - Solution

    In this instance the correspondence between rows and columns is (1, 2, 3, 4, 5, 6, 7, 8) → (2, 1, 4, 3, 6, 5, 8, 7), i.e. alternate pairs are swapped. Each number from 1 to 16 appears 4 times, hence the sum is 4×T(16) = 544.

    This puzzle seems to have attracted the attention of academia, and is mentioned in several papers (including a 50 page chapter on a solution in Prolog). In particular:

    [2005] “Enigma 1225: Prolog-Assisted Solution of a Puzzle Using Discrete Mathematics”, A. Csenki

    [2009] “A Constraint-based Approach to Enigma 1225”, Hadrien Cambazard, Barry O’Sullivan, Barbara M. Smith

    The first of these paper uses Prolog’s unification mechanism to process the problem (which is essentially the same process I use in the grid() function to equate the rows and columns). The second paper uses a constraint based programming language.

    While these papers go on to develop more sophisticated algorithms to attack this particular problem (but they don’t apply to Enigma 1248), it is perhaps surprising how poorly their initial attempts perform. In [2009] it is stated that the run time of their initial algorithm for N=6 is greater than 1 hour, and in [2005] the run time of their initial algorithm for N=8 is 209.6s.

    I dug out my 12″ Powerbook (from 2005, so contemporary with the earlier paper) and ran my Python program (using Python 2.7.2) and it runs the N=8 case in 13.5s. Although I don’t pretend my algorithm is sophisticated and will quickly get bogged down for larger values of N.

    • Jim Randell 21 June 2015 at 10:42 am

      Here’s an alternative program that uses the same technique as my original program to compute the value of the grid, but instead of considering all possible mappings between rows and columns only considers “representative” mappings (as described in the paper [2005]).

      This runs much faster and allows us to consider larger grids. For example for N=8 my original program constructed 14833 grids. The program below only constructs 7 grids. So it runs in 46ms for the N=8 case and can be used to consider much larger values for N. (This program deals with values up to 42 in less than a minute).

      from collections import Counter
      from enigma import irange, Accumulator, chunk, printf
      
      # merge <s> with <t> in grid <g>
      def merge(g, s, t):
        for (i, x) in enumerate(g):
          if x == s:
            g[i] = t
      
      # create an N x N grid with specified rows and columns equated
      # rcs - list of (r, c) (0-indexed)
      def grid(N, rcs):
        # label the squares
        n = 1
        # make the grid
        g = [0] * (N * N)
        # equate the rows and columns
        for (r, c) in rcs:
          for i in irange(0, N - 1):
            (ri, ci) = (r * N + i, c + N * i)
            if g[ri] == 0:
              if g[ci] == 0:
                # allocate a new label
                g[ri] = g[ci] = n
                n += 1
              else:
                g[ri] = g[ci]
            else:
              if g[ci] == 0:
                g[ci] = g[ri]
              elif g[ci] != g[ri]:
                # merge the two labels
                merge(g, max(g[ri], g[ci]), min(g[ri], g[ci]))
        return g
      
      
      
      import sys
      N = (8 if len(sys.argv) < 2 else int(sys.argv[1]))
      
      # label the rows
      rows = tuple(irange(0, N - 1))
      
      # generate non-decreasing sequences that sum to <t> (minimum element <m>)
      def decompose(t, m=1):
        for i in irange(m, t // 2):
          for s in decompose(t - i, i):
            yield [i] + s
        yield [t]
      
      # generate representative row/column mappings for an n x n grid
      def columns(n):
        # decompose n
        for p in decompose(n, 2):
          # partition the rows into cycles
          i = 0
          ss = []
          for j in p:
            ss.append(rows[i:i + j])
            i += j
          # and generate columns assignments
          cs = [None] * n
          for s in ss:
            for (i, j) in zip(s, s[1:] + s[:1]):
              cs[i] = j
          yield cs
      
      
      r = Accumulator(fn=max)
      
      # consider representitive columns
      for cols in columns(N):
        # generate the grid
        g = grid(N, zip(rows, cols))
        # no two rows are the same
        if len(set(chunk(g, N))) != N: continue
        # count the remaining occurrences
        c = Counter(g)
        # the maximum sum uses the the numbers 1 to N by occurrence order
        m = sum(i * n for (i, n) in enumerate(sorted(c.values()), start=1))
        r.accumulate_data(m, g)
        if r.value == m:
          printf("[m={m} {g}]")
          
      printf("max = {r.value}")
      

      As noted in paper [2009] the maximal solution observed is always the smallest viable decomposition of N. Which would mean (as the decompositions are generated in lexicographical order) that as soon as a solution is found the program could exit. If we do this we can find solutions up to N=450 in under a minute.

  2. Brian Gladman 20 June 2015 at 9:31 pm
    from sys import argv
    from itertools import permutations
    
    # output a filled grid
    def out_grid(g, n):
      for r in range(n):
        for c in range(n):
          print('{:02d}'.format(g[c + n * r]), end=' ')
        print()
      print()
    
    # fill row (r) in the N by N grid (g) starting with the next 
    # value (v) such that column cols[r] is equal to row r
    def fill_grid(g, r, v, cols, N):
      # have we finished?
      if r == N:
        yield g
      else:
        # the column in row r 
        for c in range(N):
          # the grid positions (r, c), (c, cols[r]) and (cols[c], r)
          # must all be equal
          i, j, k = c + N * r, cols[r] + N * c, r + N * cols[c]
          # if all three are equal
          if g[i] == g[j] == g[k]:
            # and all three are not set, set them to the next value
            if g[i] == 0:
              g[i] = g[j] = g[k] = v = v + 1
            else:
              continue
          # if two are not set, set them to the other (set) value
          elif g[i] == g[j] == 0 or g[j] == g[k] == 0 or g[k] == g[i] == 0:
            g[i] = g[j] = g[k] = g[i] + g[j] + g[k]
          # if only one is not set, the other two must be equal
          elif g[i] == 0 or g[j] == 0 or g[k] == 0:
            # if they are equal set the unset value to their value
            if g[j] == g[k] or g[k] == g[i] or g[i] == g[j]:
              g[i] = g[j] = g[k] = (g[i] + g[j] + g[k]) // 2
            else:
              return
          # there is no solution if three set values are not equal 
          elif len(set((g[i], g[j], g[k]))) > 1:
            return
        yield from fill_grid(g, r + 1, v, cols, N)
    
    N = 8 if len(argv) < 2 else int(argv[1])
    
    # for the solution count and maximum grid sum
    cnt, max_sum = 0, 0
    # for each permutation mapping rows to columns
    for r2c in permutations(range(N)):
      # no row number maps to the same column number 
      if all(r != c for r, c in enumerate(r2c)):
        # find filled grids
        for g in fill_grid([0] * N ** 2, 0, 0, r2c, N):
          # save the maximum grid sum and the solution count
          sm = sum(g)
          if sm >= max_sum:
            max_sum = sm
            cnt += 1
            print(sm, r2c)
            out_grid(g, N)
    print('{} solutions with a maximum grid sum of {}.'.format(cnt, max_sum))
    
    • Brian Gladman 20 June 2015 at 10:44 pm

      I forget to mention that, for reasons I haven’t worked out yet, my solution above doesn’t work for odd N.

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: