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]

Advertisements

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.

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: