Enigmatic Code

Programming Enigma Puzzles

Enigma 411: The third woman

From New Scientist #1561, 21st May 1987 [link]

The Ruritanian Secret Service has nine women agents in Britain: Anne, Barbara, Cath, Diana, Elizabeth, Felicity, Gemma, Helen and Irene. Any two of the women may or may not be in contact with each other.

To preserve security contacts are limited by the following rule: for any two of the women there is a unique third woman who is in contact with both of the women. The British Secret Service has so far discovered following pairs of women that are in contact: Anne and Cath, Anne and Diana, Cath and Barbara, Barbara and Gemma, Elizabeth and Felicity.

Which of the women are in contact with Helen? Who is the woman in contact with both Anne and Irene?

[enigma411]

2 responses to “Enigma 411: The third woman

  1. Jim Randell 25 August 2017 at 10:17 am

    Here is the problem expressed as a set of MiniZinc constraints. This model is evaluated using the [[ mzn-gecode -a ]] solver in 105ms.

    %#! mzn-gecode -a
    
    % indices for the agents
    set of int: Agents = 1..9;
    int: A = 1;
    int: B = 2;
    int: C = 3;
    int: D = 4;
    int: E = 5;
    int: F = 6;
    int: G = 7;
    int: H = 8;
    int: I = 9;
    
    % contact matrix
    array[Agents, Agents] of var 0..1: x;
    
    % no-one is in contact with themselves
    constraint forall (i in Agents) (x[i, i] = 0);
    
    % contact is a reflexive relationship
    constraint forall (i, j in Agents) (x[i, j] = x[j, i]);
    
    % each pair of agents has a unique third contact
    constraint forall (i, j in Agents where i < j) (sum (k in Agents) (x[i, k] = 1 /\ x[j, k] = 1) = 1);
    
    % known contacts
    constraint x[A, C] = 1;
    constraint x[A, D] = 1;
    constraint x[C, B] = 1;
    constraint x[B, G] = 1;
    constraint x[E, F] = 1;
    
    solve satisfy;
    

    And here is a Python program that uses the minizinc.py wrapper to take the output from MiniZinc and display the contact matrix.

    from enigma import join, printf
    from minizinc import MiniZinc
    
    # names for the agents
    names = "ABCDEFGHI"
    
    # map indices to names
    m = dict(enumerate(names, start=1))
    
    for (x,) in MiniZinc("enigma411.mzn").solve(result="x"):
      for k in sorted(x.keys()):
        printf("{k}: {v}", k=m[k], v=join(((n if x[k][i] else ' ') for (i, n) in enumerate(names, start=1)), sep=" "))
      printf()
    

    Solution: Cath and Irene are in contact with Helen. Cath is in contact with both Anne and Irene.

    Every pair of agents that does not involve C has C as their common contact (so C is the common contact for 28 of the 36 pairs).

    Here is a list of common contacts and the pairs they are the common contact for:

    A → CD
    B → CG
    C → AB, AD, AE, AF, AG, AH, AI, BD, BE, BF, BG, BH, BI, DE, DF, DG, DH, DI, EF, EG, EH, EI, FG, FH, FI, GH, GI, HI
    D → AC
    E → CF
    F → CE
    G → BC
    H → CI
    I → CH

  2. hakank 26 August 2017 at 8:21 pm

    Here’s a similar MiniZinc model – written before I read Jim’s solution – but with a little different approach: using “enum” and an explicit decision variable for the women who is in contact with Anne and Irene. Solved in 0.14s on my fastest machine.

    enum women = {Anne, Barbara, Cath, Diana, Elizabeth, Felicity, Gemma, Helen, Irene};
    
    % decision variables
    array[women,women] of var 0..1: x;
    var women: contactAnneIrene;
    
    solve satisfy;
    % solve :: int_search(x, first_fail, indomain_min, complete) satisfy;
    
    constraint
      % The British Secret Service has so far discovered following pairs of women that are in contact: 
      %    Anne and Cath, Anne and Diana, Cath and Barbara, Barbara and Gemma, Elizabeth and Felicity.
      x[Anne,Cath] = 1 /\
      x[Anne, Diana] = 1 /\ 
      x[Cath, Barbara] = 1 /\ 
      x[Barbara,Gemma] = 1 /\
      x[Elizabeth,Felicity] = 1
      /\ % contacts are symmetric.
      forall(i in women) (
        x[i,i] = 0 /\
        forall(j in women) (
          x[i,j] = x[j,i]
        )
      )
      /\
      % To preserve security contacts are limited by the following rule: 
      % for any two of the women there is a unique third woman who is in contact with both of the women. 
      forall(i, j in women where i != j) (
        sum(k in women where k != i /\ k != j) (
           x[i,k] = 1 /\ x[k,j] = 1
        ) = 1
      )
      /\ % who is in contact by Anne and Irene?
      x[contactAnneIrene,Irene] = 1 /\
      x[contactAnneIrene,Anne] = 1
    ;
    
    output 
    [
      "\(i) : \([women[j] | j in women where fix(x[i,j]) = 1])\n"
      | i in women
    ]
    ++
    [
      "\(contactAnneIrene) is the contact with Anne and Irene\n"
    ];
    

    Solution:

    Anne : [Cath, Diana]
    Barbara : [Cath, Gemma]
    Cath : [Anne, Barbara, Diana, Elizabeth, Felicity, Gemma, Helen, Irene]
    Diana : [Anne, Cath]
    Elizabeth : [Cath, Felicity]
    Felicity : [Cath, Elizabeth]
    Gemma : [Barbara, Cath]
    Helen : [Cath, Irene]
    Irene : [Cath, Helen]
    Cath is the contact with Anne and Irene
    ----------
    ==========
    

    And then a Picat model using the same principle, solved in 33ms.

    import cp.
    
    main => go.
    
    go ?=>
      Anne = 1, Barbara = 2, Cath = 3, Diana = 4, Elizabeth = 5, 
      Felicity = 6, Gemma = 7, Helen = 8, Irene = 9,
      Women = [Anne, Barbara, Cath, Diana, Elizabeth, Felicity, Gemma, Helen, Irene],
      N = Women.length,
      WomenS = [anne, barbara, cath, diana, elizabeth, felicity, gemma, helen, irene],
      
      % decision variables
      X = new_array(N,N),
      X :: 0..1,
    
      % The British Secret Service has so far discovered following pairs of women that are in contact: 
      %    Anne and Cath, Anne and Diana, Cath and Barbara, Barbara and Gemma, Elizabeth and Felicity.
      X[Anne,Cath] #= 1,
      X[Anne, Diana] #= 1,
      X[Cath, Barbara] #= 1, 
      X[Barbara,Gemma] #= 1,
      X[Elizabeth,Felicity] #= 1,
    
      % contacts are symmetric.
      foreach(I in 1..N)
        X[I,I] #= 0,
        foreach(J in 1..N) 
          X[I,J] #= X[J,I]
        end
      end,
      % To preserve security contacts are limited by the following rule: 
      % for any two of the women there is a unique third woman who is in 
      % contact with both of the women. 
      foreach(I in 1..N, J in 1..N, I != J) 
        sum([X[I,K] #= 1 #/\ X[K,J] #= 1 : K in 1..N,  K != I, K != J]) #= 1
      end,
    
      solve($[ff,split],X),
    
      foreach(I in 1..N) 
        println(WomenS[I]=[WomenS[J] : J in 1..N, X[I,J] == 1])
      end,
      % who is in contact by Anne and Irene?
      member(ContactAnneIrene,1..N),
      X[ContactAnneIrene,Irene] = 1,
      X[ContactAnneIrene,Anne] = 1,
      printf("%w is in contact with anne and irene\n",WomenS[ContactAnneIrene]),
      fail, % check for a unique solution
      nl.
    
    go => true.
    

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: