Enigmatic Code

Programming Enigma Puzzles

Enigma 1428: Foursight

From New Scientist #2589, 3rd February 2007

If you place a 1, 2, 3 or 4 in each of the sixteen places in a 4 × 4 grid, with no digit repeated in any row or column, then you end up with a “Latin square”. Then you can read eight four-figure numbers in the grid, namely across each of the four rows and down each of the four columns.

Your task today is to construct such a Latin square in which those eight numbers are all different, none is a prime, no two are reverses of each other, and:

(1st column × 3rd column) ÷ (2nd row × 3rd row) > 4

What is your Latin square?

[enigma1428]

6 responses to “Enigma 1428: Foursight

  1. Jim Randell 21 May 2013 at 7:34 am

    This Python program runs in 800ms.

    from itertools import permutations
    from enigma import concat, is_prime, is_distinct, printf
    
    # arrangements of 1,2,3,4
    ns = list()
    for s in permutations('1234'):
      n = concat(*s)
      if is_prime(int(n)): continue
      ns.append(n)
    
    # row 1
    for r1 in ns:
      # row 2
      for r2 in ns:
        if not is_distinct(r2[0], r1[0]): continue
        # row 3
        for r3 in ns:
          if not is_distinct(r3[0], r1[0], r2[0]): continue
          for r4 in ns:
            # make the columns
            cs = list(concat(*s) for s in zip(r1, r2, r3, r4))
            # check they are all valid
            if not all(n in ns for n in cs): continue
            # and check all the numbers and their reverses are distinct
            fs = set(cs).union((r1, r2, r3, r4))
            if len(fs.union(n[::-1] for n in fs)) != 16: continue
            # check the inequality
            if not(int(cs[0]) * int(cs[2]) > 4 * int(r2) * int(r3)): continue
    
            for r in (r1, r2, r3, r4):
              print(' '.join(r))
    

    Solution: The Latin square is:

    Enigma 1428 - Solution

  2. Ahmet Saracoğlu 21 May 2013 at 3:10 pm
    M=[[0 for i in range(16)] for i in range(16)]
    S=[[0, 1, 2, 3], [4, 5, 6, 7], [8,9,10,11],[12,13,14,15]]
    
    
    def CheckRule(C):
    	numbers,k=[0]*9,0
    
    
    	for i in range(0,16,4):
    		coef,number=1000,0
    		for j in range(i,i+4):
    			number=number+(C[j]*coef)
    			coef//=10
    		numbers[k]=number
    		k+=1
    
    	for i in range(0,4):
    		coef,number=1000,0
    		for j in range(i,16,4):
    			number=number+(C[j]*coef)
    			coef//=10
    		numbers[k]=number
    		k+=1
    
    	if (numbers[4]*numbers[6])/(numbers[1]*numbers[2])<=4:
    		return False
    
    
    
    
    	for i in range(8):
    		if  IsPrime(numbers[i]):
    			return False
    
    
    
    	for i in range(7):
    		num1=numbers[i]
    		strnum1=str(num1)
    		for j in range(i+1,8):
    			num2=numbers[j]
    			if (num1==num2):
    				return False
    			strnum2=str(num2)
    			#print(strnum1,strnum2,strnum2[3:0:-1])
    			if strnum1==(strnum2[3:0:-1]+strnum2[0]):
    				return False
    
    
    	print (numbers)
    	return True
    
    
    
    
    def Solve(C,v,n):
    	for color in range(1,5):
    		C[v]=color
    		if (Valid(C,v)):
    			if (v==n):
    				if (CheckRule(C)):
    					print(C)
    
    			else:
    				Solve(C,v+1,n)
    def IsPrime(number):
    	root=round(number**0.5)+1
    	for i  in range (2,root):
    		if (number%i)==0:
    			return False
    	return True
    
    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=15,False,[0]*16
        Solve(C,0,n)
    
    
    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 CreateIncidence(n):
    	for i in range(n):
    		for j in range(n):
    			Matrix(i,j,n)
    
    def SolveLatinArt():
    
    	CreateIncidence(4)
    	latin()			
    
    SolveLatinArt()	
    

    I used the same algorithm in solving the latin art in the notable enigmas, my algorithm is based upon on a recursive graph coloring algorithm

    • Ahmet Saracoğlu 21 May 2013 at 3:11 pm

      The output is:
      [3241, 1432, 2314, 4123, 3124, 2431, 4312, 1243, 0]
      [3, 2, 4, 1, 1, 4, 3, 2, 2, 3, 1, 4, 4, 1, 2, 3]

  3. Ahmet Saracoğlu 21 May 2013 at 3:24 pm

    Hi Jim, what method would you use for calculating the running time for your codes? I appreciate for your answer 🙂

  4. geoffrounce 26 April 2017 at 4:02 pm
    % A Solution in MiniZinc
    
    % 4 by 4 grid
    %   A B C D 
    %   E F G H
    %   I J K L 
    %   M N P Q
    
    include "globals.mzn";
    
    predicate is_prime(var int: x) = 
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
      ((i < x) -> (x mod i > 0));
    
    set of int: digit = { 1,2,3,4 };
    var digit: A; var digit: B; var digit: C; var digit: D;
    var digit: E; var digit: F; var digit: G; var digit: H;
    var digit: I; var digit: J; var digit: K; var digit: L;
    var digit: M; var digit: N; var digit: P; var digit: Q;
    
    % all rows have different digits
    constraint alldifferent([A,B,C,D]) /\ alldifferent([E,F,G,H])
    /\ alldifferent([I,J,K,L]) /\ alldifferent([M,N,P,Q]);
    
    % all columns have different digits
    constraint alldifferent([A,E,I,M]) /\ alldifferent([B,F,J,N])
    /\ alldifferent([C,G,K,P]) /\ alldifferent([D,H,L,Q]);
    
    % Row numbers
    var 1234..4321 : ABCD = 1000*A + 100*B + 10*C + D;
    var 1234..4321 : EFGH = 1000*E + 100*F + 10*G + H;
    var 1234..4321 : IJKL = 1000*I + 100*J + 10*K + L;
    var 1234..4321 : MNPQ = 1000*M + 100*N + 10*P + Q;
    
    % Column numbers
    var 1234..4321 : AEIM = 1000*A + 100*E + 10*I + M;
    var 1234..4321 : BFJN = 1000*B + 100*F + 10*J + N;
    var 1234..4321 : CGKP = 1000*C + 100*G + 10*K + P;
    var 1234..4321 : DHLQ = 1000*D + 100*H + 10*L + Q;
    
    % All eight numbers are different
    constraint alldifferent( [ABCD, EFGH, IJKL, MNPQ,
    AEIM, BFJN, CGKP, DHLQ] );
                       
    % None of the eight numbers is prime                                 
    constraint sum ( [is_prime(ABCD), is_prime(EFGH), is_prime(IJKL),
    is_prime(MNPQ), is_prime(AEIM), is_prime(BFJN), is_prime(CGKP), 
    is_prime(DHLQ)] ) == 0;
    
    % No two numbers are reverse of each other
    % check reverse of pairs of row numbers
    constraint (1000*D + 100*C + 10*B + A) != EFGH 
    /\ (1000*D + 100*C + 10*B + A) != IJKL
    /\ (1000*D + 100*C + 10*B + A) != MNPQ;
    
    constraint 1000*H + 100*G + 10*F + E != IJKL
    /\ 1000*H + 100*G + 10*F + E != MNPQ;
    
    constraint 1000*L + 100*K  + 10*J + I != MNPQ;
    
    % check reverses of pairs of column numbers
    constraint 1000*M + 100*I + 10*E + A != BFJN
    /\ 1000*M + 100*I + 10*E + A != CGKP
    /\ 1000*M + 100*I + 10*E + A != DHLQ;
    
    constraint 1000*N + 100*J + 10*F + B != CGKP 
    /\  1000*N + 100*J + 10*F + B != DHLQ;
    
    constraint 1000*P + 100*K + 10*G + C != DHLQ;
    
    % there are more rows/cols to check for a rigorous solution,
    % but this is enough checking to find the answer...
    
    % (1st column × 3rd column) ÷ (2nd row × 3rd row) > 4
    constraint (AEIM * CGKP) > 4 * (EFGH * IJKL) ;
    
    solve satisfy;
    
    output [ "Latin square is: " ++ " \n " ++ show(ABCD) ++ " \n " ++ show(EFGH) ++ 
    " \n " ++ show(IJKL) ++ " \n " ++ show(MNPQ)  ++ "\n " ];
    
    % Latin square is:
    % 3241 
    % 1432 
    % 2314 
    % 4123
    % Finished in 134msec
    
    

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

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

%d bloggers like this: