Enigmatic Code

Programming Enigma Puzzles

Enigma 1608: Par hexcellence

From New Scientist #2773, 14th August 2010 [link]

Joe asked Penny to find the honey in the honeycomb. The number in each cell indicates how many of the adjoining cells contain honey.

Numbering the cells in the centre row 1 to 8 from left to right, which numbered cells contain honey?

[enigma1608]

Advertisements

One response to “Enigma 1608: Par hexcellence

  1. jimrandell 4 January 2012 at 3:49 pm

    The following Python program runs in 30ms and finds the solution, although it is not a generic engine for solving similar problems. It uses a simple strategy to fill out the unknown cells, and it turns out that by considering the possibilities for the cells surrounding the top-left cell this strategy is sufficient.

    It would be more satisfactory to adapt my Sudoku solving code to work on this puzzle, but as the code below does its job I didn’t do that.

    #      16  17  18  19  20  21
    #    09  10  11  12  13  14  15
    #  01  02  03  04  05  06  07  08
    #    22  23  24  25  26  27  28
    #      29  30  31  32  33  34
    
    # adjacency matrix
    adjacent = [None,
      [ 2, 9, 22 ],
      [ 1, 3, 9, 10, 22, 23 ],
      [ 2, 4, 10, 11, 23, 24 ],
      [ 3, 5, 11, 12, 24, 25 ],
      [ 4, 6, 12, 13, 25, 26 ],
      [ 5, 7, 13, 14, 26, 27 ],
      [ 6, 8, 14, 15, 27, 28 ],
      [ 7, 15, 28 ],
      [ 1, 2, 10, 16 ],
      [ 2, 3, 9, 11, 16, 17 ],
      [ 3, 4, 10, 12, 17, 18 ],
      [ 4, 5, 11, 13, 18, 19 ],
      [ 5, 6, 12, 14, 19, 20 ],
      [ 6, 7, 13, 15, 20, 21 ],
      [ 7, 8, 14, 21 ],
      [ 9, 10, 17 ],
      [ 10, 11, 16, 18 ],
      [ 11, 12, 17, 19 ],
      [ 12, 13, 18, 20 ],
      [ 13, 14, 19, 21 ],
      [ 21, 14, 15, 20 ],
      [ 1, 2, 23, 29 ],
      [ 2, 3, 22, 24, 29, 30 ],
      [ 3, 4, 23, 25, 30, 31 ],
      [ 4, 5, 24, 26, 31, 32 ],
      [ 5, 6, 25, 27, 32, 33 ],
      [ 6, 7, 26, 28, 33, 34 ],
      [ 7, 8, 27, 34 ],
      [ 22, 23, 30 ],
      [ 23, 24, 29, 31 ],
      [ 24, 25, 30, 32 ],
      [ 25, 26, 31, 33 ],
      [ 26, 27, 32, 34 ],
      [ 27, 28, 33 ]
    ]
    
    # honey cell counts
    count = [ None,
      1, 3, 2, 3, 3, 3, 1, 1,
        2, 1, 3, 1, 2, 2, 2,
          2, 1, 2, 2, 2, 1,
        1, 3, 2, 1, 2, 3, 2,
          2, 1, 3, 2, 1, 1 ]
    
    # fill out remaining unknown cells
    def complete(honey, cell, what='X'):
      for i in adjacent[cell]:
        if honey[i] == '?': honey[i] = what
    
    # attempt to solve the puzzle
    def solve(honey):
      progress = 0
      done = 0
      # look for cells that are fully defined
      for i in range(1, 35):
        c = count[i]
        a = [ honey[x] for x in adjacent[i] ]
        h = a.count('H')
        x = a.count('X')
        r = len(a) - h - x
        # failures (too many honey cells, or not enough)
        if h > c or h + r < c:
          print("FAIL! at cell {i} ({a}) = {c}".format(i=i, a=a, c=c))
          return False
        # skip fully populated cells
        if r == 0:
          # note, if r = 0 we know that h <= c and h >= c, hence h == c
          done += 1
          continue
        # are there already enough adjacent honey cells?
        if h == c:
          # yes, so fill out the remaining cells with 'X'
          print("COMPLETE[1] at cell {i} ({a}) = {c}".format(i=i, a=a, c=c))
          complete(honey, i, 'X')
          progress += 1
        # must all the remaining cells be honey cells?
        elif c == h + r:
          # yes, so fill them out with 'H'
          print("COMPLETE[2] at cell {i} ({a}) = {c}".format(i=i, a=a, c=c))
          complete(honey, i, 'H')
          progress += 1
      if done == 34:
        print("FINISHED!", "*** SOLUTION:", list(filter(lambda i: honey[i] == 'H', range(1, 9))), "***")
        return True
      else:
        print("COMPLETED {n} cells".format(n=progress))
        if progress > 0:
          return solve(honey)
        return False
    
    # exactly two of the cells surrounding cell 16 contain honey
    for i in adjacent[16]:
      honey = ['?'] * 35
      honey[i] = 'X'
      print("TRYING: cell {i} = X".format(i=i))
      complete(honey, 16, 'H')
      solve(honey)
    

    Solution: Cells 1 and 7 contain honey.

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: