# 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]

### 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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.