/
enigma_411_the_third_woman.pi
80 lines (61 loc) · 2.52 KB
/
enigma_411_the_third_woman.pi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/*
Enigma 411: The third woman in Picat.
Enigma 411: The third woman
https://enigmaticcode.wordpress.com/2017/08/25/enigma-411-the-third-woman/#comment-5889
"""
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?
"""
This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
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.