# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1416: Filling in the squares

From New Scientist #2576, 4th November 2006

Susan and Paul have a new game which is played on a 4×4 array of small squares.

Two dark lines though the centre of the array, one horizontal and one vertical, divide the array into four 2×2 “regions”. If you select a square in the array, then its “environment” is the seven squares which are in the same row, column or region as the selected square.

Susan begins a game by writing 1, 2, 3 or 4 in some of the squares in the array. Paul then takes over. If he can find an empty square whose environment contains three of the four numbers then he writes the fourth number in that empty square. Paul repeats this operation on the resulting array and he does that as many times as he can. If, when Paul has finished, they find that every square of the array is full then they say that Susan made a “wise” beginning.

On Monday they played a game for which Susan made a wise beginning. On Tuesday they decided she would begin by filling one fewer squares than on Monday. After exhaustive searching they found that, with that restriction, Susan was unable to make a wise beginning.

How many squares did Susan fill on Monday?

[enigma1416]

### One response to “Enigma 1416: Filling in the squares”

1. Jim Randell 1 July 2013 at 10:55 am

This Python program runs in 76ms.

```# we need to find the smallest number of starting squares
# such that the puzzle cannot be completed.

# it needs to be 3 or greater

from itertools import combinations, count
from enigma import irange, printf

# numbers used to fill out the grid
numbers = set(irange(1, 4))

# indices of squares in the grid
squares = set(irange(0, 15))

# environment of each square
environment = (
(1, 2, 3, 4, 5, 8, 12), # 0
(0, 2, 3, 4, 5, 9, 13), # 1
(0, 1, 3, 6, 7, 10, 14), # 2
(0, 1, 2, 6, 7, 11, 15), # 3
(0, 1, 5, 6, 7, 8, 12), # 4
(0, 1, 4, 6, 7, 9, 13), # 5
(2, 3, 4, 5, 7, 10, 14), # 6
(2, 3, 4, 5, 6, 11, 15), # 7
(0, 4, 9, 10, 11, 12, 13), # 8
(1, 5, 8, 10, 11, 12, 13), # 9
(2, 6, 8, 9, 11, 14, 15), # 10
(3, 7, 8, 9, 10, 14, 15), # 11
(0, 4, 8, 9, 13, 14, 15), # 12
(1, 5, 8, 9, 12, 14, 15), # 13
(2, 6, 10, 11, 12, 13, 15), # 14
(3, 7, 10, 11, 12, 13, 14), # 15
)

# solve a grid by filling out empty squares with one
# number missing from their environment
def solve(g):
while (0 in g):
# look at empty squares
for i in squares:
if g[i] != 0: continue
# find the values not in the environment
s = numbers.difference(g[j] for j in environment[i])
if len(s) == 0: return False
if len(s) == 1:
g[i] = s.pop()
break
else:
# no progress, exit the while loop
break
return (0 not in g)

# decompose n into acceptable "colourings"
# n - number of elements in decomposition
# m - number of digits in decomposition
# d - current digit
# u - largest possible element count
# mn - smallest possible element counts
def decompose(n, m, d, u, mn):
if m == 1:
if not(n > u): yield [d] * n
else:
for n1 in irange(mn[0], min(u, n - sum(mn[1:]))):
for ns in decompose(n - n1, m - 1, d + 1, n1, mn[1:]):
yield [d] * n1 + ns

# check grids filled out with n numbers
def check(n):
# for each 4-colouring
for ds in decompose(n, 4, 1, n, [1, 1, 1, 0]):
# choose n placements
for ps in combinations(squares, n):
# fill out the grid
g = [0] * 16
for (i, d) in zip(ps, ds):
g[i] = d
# try to find a solution
if solve(g): return True
# no solutions found
return False

# start checking from 3 (there must be 3 numbers in one environment
# to get going) and look for n where grids with n numbers cannot be
# completed, but some grid with n+1 numbers can be
for n in count(3):
if not check(n) and check(n + 1):
printf("Monday: {n1} squares,  Tuesday: {n} squares", n1=n+1)
break
```

Solution: Susan filled in 4 squares on Monday.

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