Enigmatic Code

Programming Enigma Puzzles

Enigma 1474: Nativity places

From New Scientist #2635, 22nd December 2007

Miss Amber is holding the dress rehearsal for the school Nativity play. The choir has 81 children, consisting of 9 each of angels, barn owls, chickens, dogs, ewes, farmhands, goats, horses and innkeepers. She marked out a 9×9 grid on the stage and some of the children are already in the grid (below).

Surprisingly, Miss Amber was able to add the other children to the grid, making sure each row, column and 3×3 box contains all the 9 characters. Find the 3×3 box in the bottom left-hand corner of the finished grid.

[enigma1474]

Advertisements

One response to “Enigma 1474: Nativity places

  1. Jim Randell 14 January 2013 at 9:08 am

    It quickly becomes apparent that this isn’t a standard “Sudoku” style puzzle. (For instance there is no possible letter to fit the empty square that is fourth from the left on the top row). And since the puzzle states “each row, column and 3×3 box contains all of the 9 characters”, the only Sudoku rule that is missing is “each square contains one of the characters A-I”, and since empty squares must be allowed it follows that some squares must contain more than one character.

    There are rather a lot of squares already filled out and a strategy that looks through each group (row, column, box) to see where the remaining values must be placed completes after two iterations. The following Python program solve the puzzle in 43ms.

    from enigma import chunk, sprintf, printf
    
    # possible values
    values = set('ABCDEFGHI')
    
    # create the initial grid
    (A, B, C, D, E, F, G, H, I) = 'ABCDEFGHI'
    grid = [
      [ A ], [   ], [   ], [   ], [ D ], [   ], [ I ], [ E ], [ C ],
      [   ], [ C ], [ H ], [ E ], [ G ], [ A ], [ B ], [ F ], [   ],
      [ F ], [   ], [ D ], [ B ], [ I ], [   ], [ G ], [   ], [ H ],
      [ G ], [ D ], [ E ], [   ], [ F ], [ B ], [ C ], [   ], [   ],
      [ B ], [ A ], [ I ], [ C ], [ H ], [   ], [   ], [ D ], [   ],
      [   ], [ H ], [ F ], [   ], [ E ], [ I ], [ A ], [ G ], [   ],
      [   ], [   ], [ C ], [ H ], [ A ], [ D ], [ E ], [ B ], [   ],
      [   ], [ I ], [ G ], [ F ], [   ], [   ], [ H ], [   ], [ A ],
      [ E ], [ B ], [   ], [ G ], [ C ], [   ], [ D ], [ I ], [ F ],
    ]
    
    # groups
    groups = [
      # rows
      [  0,  1,  2,  3,  4,  5,  6,  7,  8 ],
      [  9, 10, 11, 12, 13, 14, 15, 16, 17 ],
      [ 18, 19, 20, 21, 22, 23, 24, 25, 26 ],
      [ 27, 28, 29, 30, 31, 32, 33, 34, 35 ],
      [ 36, 37, 38, 39, 40, 41, 42, 43, 44 ],
      [ 45, 46, 47, 48, 49, 50, 51, 52, 53 ],
      [ 54, 55, 56, 57, 58, 59, 60, 61, 62 ],
      [ 63, 64, 65, 66, 67, 68, 69, 70, 71 ],
      [ 72, 73, 74, 75, 76, 77, 78, 79, 80 ],
      # columns
      [  0,  9, 18, 27, 36, 45, 54, 63, 72 ],
      [  1, 10, 19, 28, 37, 46, 55, 64, 73 ],
      [  2, 11, 20, 29, 38, 47, 56, 65, 74 ],
      [  3, 12, 21, 30, 39, 48, 57, 66, 75 ],
      [  4, 13, 22, 31, 40, 49, 58, 67, 76 ],
      [  5, 14, 23, 32, 41, 50, 59, 68, 77 ],
      [  6, 15, 24, 33, 42, 51, 60, 69, 78 ],
      [  7, 16, 25, 34, 43, 52, 61, 70, 79 ],
      [  8, 17, 26, 35, 44, 53, 62, 71, 80 ],
      # boxes
      [  0,  1,  2,  9, 10, 11, 18, 19, 20 ],
      [  3,  4,  5, 12, 13, 14, 21, 22, 23 ],
      [  6,  7,  8, 15, 16, 17, 24, 25, 26 ],
      [ 27, 28, 29, 36, 37, 38, 45, 46, 47 ],
      [ 30, 31, 32, 39, 40, 41, 48, 49, 50 ],
      [ 33, 34, 35, 42, 43, 44, 51, 52, 53 ],
      [ 54, 55, 56, 63, 64, 65, 72, 73, 74 ],
      [ 57, 58, 59, 66, 67, 68, 75, 76, 77 ],
      [ 60, 61, 62, 69, 70, 71, 78, 79, 80 ],
    ]
    
    # map of related squares (row, column, box)
    related = dict((i, set().union(*(g for g in groups if i in g)).difference([i])) for i in range(81))
    
    def solve(grid):
      n = 0
      # find a group that is not completed
      for g in groups:
        # what values are not yet filled out in this group?
        vs = values.difference(*(grid[x] for x in g))
        if len(vs) == 0:
          n += 1
          continue
        # for each unplaced value
        for v in vs:
          # where can it go?
          ps = list(i for i in g if v not in set().union(*(grid[x] for x in related[i])))
          # if there's only one possible position
          if len(ps) == 1:
            # then place it
            grid[ps[0]].append(v)
      return n
    
    # solve the grid by repeated application of solve
    (i, n, m) = (0, 0, len(groups))
    while n < m:
      n = solve(grid)
      i += 1
      printf("[{i}] completed {n} groups (of {m})")
    
    # output the grid
    fmt = "[{:" + str(max(len(g) for g in grid)) + "s}]"
    for (i, r) in enumerate(chunk(grid, 9)):
      for (j, x) in enumerate(r):
        print(fmt.format(''.join(sorted(x))), end=' ')
        if j % 3 == 2: print('  ', end='')
      print()
      if i % 3 == 2: print('')
    

    Solution: The 3×3 box in the bottom left hand corner of the completed puzzle is: empty, F, C; D, I, G; E & H, B, A.

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: