# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1661: Latin art

From New Scientist #2827, 27th August 2011 [link]

Joe drew a 5 by 5 grid and numbered the squares from 1 to 25 as indicated. He asked Penny to colour the 25 squares using the minimum number of colours, ensuring that for each square and the two, three or four squares next to it no two colours in that set were the same. Penny painted squares 1 and 23 red.

What other numbered squares did Penny paint red?

[enigma1661]

### 4 responses to “Enigma 1661: Latin art”

1. jimrandell 4 December 2011 at 12:33 pm

This was a good programming challenge. I adapted an algorithm I’d previously written to strategically solve Sudoku puzzles (and also used on Enigma 1657).

The following Python code runs in 32ms.

```import copy

class Impossible(Exception): pass
class Solved(Exception): pass

class Puzzle:

def __init__(self, grid):
self.grid = [ [[]] * 5 for i in range(5) ]
self.colours = [ 1, 2, 3, 4, 5 ]
self.remaining = 25
# fill out the grid of possibilities
for i in range(5):
for j in range(5):
g = grid[i][j]
if g:
self.grid[i][j] = [ g ]
self.remaining -= 1
else:
self.grid[i][j] = copy.copy(self.colours)

def clone(self):
return copy.deepcopy(self)

def become(self, other):
for x in vars(other).keys():
setattr(self, x, getattr(other, x))

def remove(self, i, j, c):
if i < 0 or i > 4 or j < 0 or j > 4: return
s = self.grid[i][j]
if c not in s: return
s.remove(c)
if len(s) == 0:
raise Impossible
if len(s) == 1:
self.remaining -= 1
if self.remaining < 1: raise Solved

def eliminate(self):
n = self.remaining
for i in range(5):
for j in range(5):
if len(self.grid[i][j]) == 1:
c = self.grid[i][j][0]
self.remove(i-1, j, c)
self.remove(i+1, j, c)
self.remove(i, j-1, c)
self.remove(i, j+1, c)
self.remove(i-1, j-1, c)
self.remove(i+1, j-1, c)
self.remove(i-1, j+1, c)
self.remove(i+1, j+1, c)
self.remove(i-2, j, c)
self.remove(i+2, j, c)
self.remove(i, j-2, c)
self.remove(i, j+2, c)
return self.remaining < n

def hypothetical(self):
for i in range(5):
for j in range(5):
if len(self.grid[i][j]) < 2: continue
for c in self.grid[i][j]:
new = self.clone()
new.grid[i][j] = [c]
new.remaining -= 1
if new.solve():
self.become(new)
return True
raise Impossible
return False

def _solve(self, strategy):
while self.remaining:
while strategy[0](): pass
for s in strategy[1:]:
if s(): break

def solve(self):
try:
self._solve([self.eliminate, self.hypothetical])
except(Impossible, Solved):
pass
return self.remaining == 0

grid = [
[  1,  0,  0,  0,  0 ],
[  0,  0,  0,  0,  0 ],
[  0,  0,  2,  0,  0 ],
[  0,  3,  4,  5,  0 ],
[  0,  0,  1,  0,  0 ],
]

p = Puzzle(grid)
if p.solve():
# print the grid
reds = []
for i in range(5):
for j in range(5):
print(p.grid[i][j][0], end='')
if p.grid[i][j][0] == 1: reds.append(i*5 + j + 1)
print()
# print the reds (= colour 1)
reds.remove(1)
reds.remove(23)
print('reds =', reds)
```

Solution: The other red squares are 9, 12 and 20.

2. Ahmet Saracoğlu 16 May 2013 at 1:21 pm
```def SolveLatinArt():
M=[[0 for i in range(25)] for i in range(25)]
S=[[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]]
CreateIncidence(5)
latin()

def Matrix(i,j,n):
for k in range(j+1,n):
itemij,itemik=S[i][j],S[i][k]
M[itemij][itemik]=1
M[itemik][itemij]=1

for k in range(i+1,n):
itemij,itemik=S[i][j],S[k][j]
M[itemij][itemik]=1
M[itemik][itemij]=1
def MatrixDiag(n):
for i in range(n):
for j in range(0,n):
itemij,itemdij=S[i][j],S[i+1][j+1]
M[itemij][itemdij]=1
M[itemdij][itemij]=1

for i in range(n):
for j in range(n,0,-1):
itemij,itemdj=S[i][j],S[i+1][j-1]
M[itemij][itemdj]=1
M[itemdj][itemij]=1
def CreateIncidence(n):
for i in range(n):
for j in range(n):
Matrix(i,j,n)
MatrixDiag(n-1)
SolveLatinArt() # Main Function

def Solve(C,v,n,flag):

for color in range(5):

C[v]=color

if (Valid(C,v)):
if (v==n):
flag=True
if C[0]==C[22]==0:
print (C)

else:
Solve(C,v+1,n,flag)

def Valid(C,v):

for i in range(0,v):
if C[i]==C[v]:
if M[i][v]==1:
return False

return True

def latin():
n,flag,C=24,False,[0]*25
flag=Solve(C,0,n,flag)
if flag==False:
print("No Solution exists")

SolveLatinArt()
# These are all permutations that satisfy the conditions saying that cell 1 and cell23 are both in red colors, as being seen below.
[0, 1, 2, 3, 4, 2, 3, 4, 0, 1, 4, 0, 1, 2, 3, 1, 2, 3, 4, 0, 3, 4, 0, 1, 2]
[0, 1, 2, 4, 3, 2, 4, 3, 0, 1, 3, 0, 1, 2, 4, 1, 2, 4, 3, 0, 4, 3, 0, 1, 2]
[0, 1, 3, 2, 4, 3, 2, 4, 0, 1, 4, 0, 1, 3, 2, 1, 3, 2, 4, 0, 2, 4, 0, 1, 3]
[0, 1, 3, 4, 2, 3, 4, 2, 0, 1, 2, 0, 1, 3, 4, 1, 3, 4, 2, 0, 4, 2, 0, 1, 3]
[0, 1, 4, 2, 3, 4, 2, 3, 0, 1, 3, 0, 1, 4, 2, 1, 4, 2, 3, 0, 2, 3, 0, 1, 4]
[0, 1, 4, 3, 2, 4, 3, 2, 0, 1, 2, 0, 1, 4, 3, 1, 4, 3, 2, 0, 3, 2, 0, 1, 4]
[0, 2, 1, 3, 4, 1, 3, 4, 0, 2, 4, 0, 2, 1, 3, 2, 1, 3, 4, 0, 3, 4, 0, 2, 1]
[0, 2, 1, 4, 3, 1, 4, 3, 0, 2, 3, 0, 2, 1, 4, 2, 1, 4, 3, 0, 4, 3, 0, 2, 1]
[0, 2, 3, 1, 4, 3, 1, 4, 0, 2, 4, 0, 2, 3, 1, 2, 3, 1, 4, 0, 1, 4, 0, 2, 3]
[0, 2, 3, 4, 1, 3, 4, 1, 0, 2, 1, 0, 2, 3, 4, 2, 3, 4, 1, 0, 4, 1, 0, 2, 3]
[0, 2, 4, 1, 3, 4, 1, 3, 0, 2, 3, 0, 2, 4, 1, 2, 4, 1, 3, 0, 1, 3, 0, 2, 4]
[0, 2, 4, 3, 1, 4, 3, 1, 0, 2, 1, 0, 2, 4, 3, 2, 4, 3, 1, 0, 3, 1, 0, 2, 4]
[0, 3, 1, 2, 4, 1, 2, 4, 0, 3, 4, 0, 3, 1, 2, 3, 1, 2, 4, 0, 2, 4, 0, 3, 1]
[0, 3, 1, 4, 2, 1, 4, 2, 0, 3, 2, 0, 3, 1, 4, 3, 1, 4, 2, 0, 4, 2, 0, 3, 1]
[0, 3, 2, 1, 4, 2, 1, 4, 0, 3, 4, 0, 3, 2, 1, 3, 2, 1, 4, 0, 1, 4, 0, 3, 2]
[0, 3, 2, 4, 1, 2, 4, 1, 0, 3, 1, 0, 3, 2, 4, 3, 2, 4, 1, 0, 4, 1, 0, 3, 2]
[0, 3, 4, 1, 2, 4, 1, 2, 0, 3, 2, 0, 3, 4, 1, 3, 4, 1, 2, 0, 1, 2, 0, 3, 4]
[0, 3, 4, 2, 1, 4, 2, 1, 0, 3, 1, 0, 3, 4, 2, 3, 4, 2, 1, 0, 2, 1, 0, 3, 4]
[0, 4, 1, 2, 3, 1, 2, 3, 0, 4, 3, 0, 4, 1, 2, 4, 1, 2, 3, 0, 2, 3, 0, 4, 1]
[0, 4, 1, 3, 2, 1, 3, 2, 0, 4, 2, 0, 4, 1, 3, 4, 1, 3, 2, 0, 3, 2, 0, 4, 1]
[0, 4, 2, 1, 3, 2, 1, 3, 0, 4, 3, 0, 4, 2, 1, 4, 2, 1, 3, 0, 1, 3, 0, 4, 2]
[0, 4, 2, 3, 1, 2, 3, 1, 0, 4, 1, 0, 4, 2, 3, 4, 2, 3, 1, 0, 3, 1, 0, 4, 2]
[0, 4, 3, 1, 2, 3, 1, 2, 0, 4, 2, 0, 4, 3, 1, 4, 3, 1, 2, 0, 1, 2, 0, 4, 3]
[0, 4, 3, 2, 1, 3, 2, 1, 0, 4, 1, 0, 4, 3, 2, 4, 3, 2, 1, 0, 2, 1, 0, 4, 3]

```

I used a recursive graph algorithm with backtraking and listed all permutations with the constraints given in the puzzle, that is the red ones in cell 1 and cell 23. My grid index starts from 0. Firstly, I created the incidince Matrix for the given problem and then I used the graph coloring algorithm.

• Ahmet Saracoğlu 16 May 2013 at 2:48 pm

In the latin function, no need to check the flag value and sure no flag values to be returned, i was going to remove that part, but have forgotten

• Ahmet Saracoğlu 21 May 2013 at 4:48 pm

def SolveLatinArt(): M=[[0 for i in range(25)] for i in range(25)] S=[[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]] CreateIncidence(5) latin()

M and S arrays must be outside this function, they are global ones, then it must be like the following:

```M=[[0 for i in range(25)] for i in range(25)]
S=[[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]]
def SolveLatinArt():
CreateIncidence(5)
latin
```

Sorry for that, when checking I noticed that that part is different from the code on my machine and I correct it.

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