# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1591: Pseudo coup

From New Scientist #2756, 17th April 2010 [link]

All Penny had to do this week was fill in the missing numbers so that each row, each column and each three-by-three square all had each of the numbers 1 to 9.

In printing out the puzzle Joe had interchanged some of the three-by-three squares.

Penny worked out which and filled in all the missing numbers.

What number did Penny place in the small shaded square?

[enigma1591]

### 2 responses to “Enigma 1591: Pseudo coup”

1. Jim Randell 23 January 2012 at 11:31 am

I was thinking I might have to bring to bear my generic Sudoku solving code on this one, but it turns out that a simple elimination solver is sufficient.

I first create a table of which squares are incompatible in a horizontal and vertical direction, and use this to reduce the possibilities from the rearrangement of the squares. The elimination solver is then unleashed on the composite Sudoku puzzle.

The following Python program runs in 300ms.

```from itertools import permutations
from enigma import irange, printf

numbers = set(irange(1, 9))

s = (
(0, 6, 0, 8, 4, 0, 0, 0, 9),
(0, 2, 0, 0, 3, 4, 8, 0, 0),
(0, 9, 0, 2, 0, 6, 0, 5, 0),
(0, 0, 3, 8, 5, 0, 0, 7, 0),
(9, 8, 0, 0, 0, 0, 0, 7, 3),
(0, 0, 7, 3, 0, 1, 5, 0, 0),
(4, 6, 0, 0, 0, 0, 0, 3, 1),
(0, 0, 4, 3, 0, 2, 6, 0, 0),
(5, 0, 0, 0, 8, 4, 0, 7, 0)
)

# check each square for H(orizontal) and V(ertical) incompatibility
H = [[0] * 9 for i in irange(0, 8)]
V = [[0] * 9 for i in irange(0, 8)]
for i in irange(0, 8):
for j in irange(0, 8):
if i == j: continue
if numbers.intersection(s[i][0:3]).intersection(s[j][0:3]) or \
numbers.intersection(s[i][3:6]).intersection(s[j][3:6]) or \
numbers.intersection(s[i][3:6]).intersection(s[j][3:6]):
H[i][j] = 1
if numbers.intersection(s[i][0:9:3]).intersection(s[j][0:9:3]) or \
numbers.intersection(s[i][1:9:3]).intersection(s[j][1:9:3]) or \
numbers.intersection(s[i][2:9:3]).intersection(s[j][2:9:3]):
V[i][j] = 1

# now consider all the permutations
for x in permutations(irange(0, 8), 9):
# check for H incompatibilities
if H[x[0]][x[1]] or H[x[0]][x[2]] or H[x[1]][x[2]]: continue
if H[x[3]][x[4]] or H[x[3]][x[5]] or H[x[4]][x[5]]: continue
if H[x[6]][x[7]] or H[x[6]][x[8]] or H[x[7]][x[8]]: continue
# and V incompatibilities
if V[x[0]][x[3]] or V[x[0]][x[6]] or V[x[3]][x[6]]: continue
if V[x[1]][x[4]] or V[x[1]][x[7]] or V[x[4]][x[7]]: continue
if V[x[2]][x[5]] or V[x[2]][x[8]] or V[x[5]][x[8]]: continue

# OK, create a composite Sudoku from the squares
p = (
list(s[x[0]][0:3] + s[x[1]][0:3] + s[x[2]][0:3]),
list(s[x[0]][3:6] + s[x[1]][3:6] + s[x[2]][3:6]),
list(s[x[0]][6:9] + s[x[1]][6:9] + s[x[2]][6:9]),
list(s[x[3]][0:3] + s[x[4]][0:3] + s[x[5]][0:3]),
list(s[x[3]][3:6] + s[x[4]][3:6] + s[x[5]][3:6]),
list(s[x[3]][6:9] + s[x[4]][6:9] + s[x[5]][6:9]),
list(s[x[6]][0:3] + s[x[7]][0:3] + s[x[8]][0:3]),
list(s[x[6]][3:6] + s[x[7]][3:6] + s[x[8]][3:6]),
list(s[x[6]][6:9] + s[x[7]][6:9] + s[x[8]][6:9]),
)

# and solve it
def solve(p):
progress = False
for i in irange(0, 8):
a = 3 * (i // 3)
for j in irange(0, 8):
if p[i][j]: continue
b = 3 * (j // 3)
x = numbers.difference(
p[i], # row
(p[x][j] for x in irange(0, 8)), # column
(p[a][b], p[a+1][b], p[a+2][b], p[a+1][b], p[a+1][b+1], p[a+1][b+2], p[a+2][b], p[a+2][b+1], p[a+2][b+2]) # square
)
if len(x) > 1: continue
p[i][j] = x.pop()
progress = True
return progress

while solve(p):
pass

# and find the target square
where = [(2, 0), (2, 3), (2, 6), (5, 0), (5, 3), (5, 6), (8, 0), (8, 3), (8, 6)]
(a, b) = where[x.index(2)]
printf("{x} => {p}", p=p[a][b])
```

Solution: The shaded square contains the number 4.

2. Hugh Casement 7 April 2016 at 2:26 pm

I labelled the 3×3 squares A to I in order.  There are many arrangements that resolve the incompatibilities (for example, 4 occurs twice in the second row), but this one involves fewest moves, leaving five in position:
D  B  C
H  E  A
G  F  I

I admit I didn’t then check whether the sudoku as a whole has a solution, but solved only for square C (still at top right).