From the web:
<<It’s famously known as the Einstein Riddle because it was supposedly created by Einstein as a young man for fun.
But there are some claims online that it actually was invented by the author of Alice’s Adventures in Wonderland, Lewis Carrol.
It’s highly unlikely that it was written by Einstein, but that doesn’t really matter.
There are 5 houses painted five different colors.
In each house lives a person with a different nationality.
These five owners drink a certain type of beverage, smoke a certain brand of cigar, and keep a certain pet.
No owners have the same pet, smoke the same brand of cigar, or drink the same beverage.
-
The Brit lives in the red house -
The Swede keeps dogs as pets -
The Dane drinks tea -
The green house is on the left of the white house -
The person who smokes Pall Malls rears birds -
The owner of the yellow house smokes Dunhill -
The green house’s owner drinks coffee -
The man living in the center house drinks milk -
The Norwegian lives in the first (leftmost) house -
The man who smokes Blends lives next to the one who keeps cats -
The man who keeps horses lives next to the man who smokes Dunhill -
The owner who smokes BlueMaster drinks beer -
The German smokes Princes -
The Norwegian lives next to the blue house -
The man who smokes Blends has a neighbor who drinks water
Now to solve, tell me who owns the fish?
Exactly as stated on the website: I solved it, but it did take me a bit of scribbling on paper.
Then I thought if and how it was possible to make Julia do it.
I actually found it much less challenging to do with pen and paper, but in the end (after understanding the syntax of the @variableS macro, for example, one of the main difficulties) I managed to come up with a script that works (I think).
I still have doubts about the interpretation of rule 4 and whether it is possible to write the constraints I used in a more concise way.
I would also be curious to hear about different models of the problem
E.riddle
using JuMP
using HiGHS
using Random
begin
quiz5case = Model(HiGHS.Optimizer)
set_silent(quiz5case)
begin
N=shuffle(["NO","DK","UK","DE","SE"])
A=shuffle(["cats","horses","birds","fishs","dog"])
C=shuffle(["yellow","blue","red","green","white"])
D=shuffle(["water","the","milk","coffee","beer"])
S=shuffle(["Dunhill","Blends","PallMall","Prince","BlueMaster"])
end
@variables(quiz5case,begin
xn[j in 1:5, k in N], Bin
xa[j in 1:5, k in A], Bin
xc[j in 1:5, k in C], Bin
xd[j in 1:5, k in D], Bin
xs[j in 1:5, k in S], Bin
end)
@constraints(quiz5case, begin
[n in N], sum(xn[:,n])==1
[a in A], sum(xa[:,a])==1
[c in C], sum(xc[:,c])==1
[d in D], sum(xd[:,d])==1
[s in S], sum(xs[:,s])==1
[i in 1:5], sum(xn[i,:])==1
[i in 1:5], sum(xa[i,:])==1
[i in 1:5], sum(xc[i,:])==1
[i in 1:5], sum(xd[i,:])==1
[i in 1:5], sum(xs[i,:])==1
r1[i in 1:5], xn[i,"UK"]==xc[i,"red"]
r2[i in 1:5], xn[i,"SE"]==xa[i,"dog"]
r3[i in 1:5], xn[i,"DK"]==xd[i,"the"]
#r4[i in 2:5], xc[i,"green"] .<= 1 .- xc[1:i-1,"white"]
r4a, xc[5,"green"]==0
r4b[i in 1:4], xc[i,"green"] <= xc[i+1,"white"]
r5[i in 1:5], xc[i,"green"]==xd[i,"coffee"]
r6[i in 1:5], xs[i,"PallMall"]==xa[i,"birds"]
r7[i in 1:5], xc[i,"yellow"]==xs[i,"Dunhill"]
r8[i=3], xd[i,"milk"]==1
r9[i=1], xn[i,"NO"]==1
r10a[i =1], xs[i,"Blends"]<=xa[i+1,"cats"]
r10b[i=5], xs[i,"Blends"]<=xa[i-1,"cats"]
r10c[i in 2:4], xs[i,"Blends"]<=xa[i+1,"cats"] + xa[i-1,"cats"]
r11a[i=1], xs[i,"Dunhill"]<=xa[i+1,"horses"]
r11b[i=5], xs[i,"Dunhill"]<=xa[i-1,"horses"]
r11c[i in 2:4], xs[i,"Dunhill"]<=xa[i+1,"horses"] + xa[i-1,"horses"]
r12[i in 1:5], xs[i,"BlueMaster"]==xd[i,"beer"]
r13[i in 1:5], xn[i,"DE"]==xs[i,"Prince"]
r14a[i=1], xn[i,"NO"]<=xc[i+1,"blue"]
r14b[i=5], xn[i,"NO"]<=xc[i-1,"blue"]
r14c[i in 2:4], xn[i,"NO"]<=xc[i+1,"blue"] + xc[i-1,"blue"]
#r14[i=2], xc[i,"blue"]==1
r15a[i=1], xs[i,"Blends"]<=xd[i+1,"water"]
r15b[i=5], xs[i,"Blends"]<=xd[i-1,"water"]
r15c[i in 2:4], xs[i,"Blends"]<=xd[i+1,"water"] + xd[i-1,"water"]
end);
# 1. L’inglese vive in una casa rossa
# 2. Lo svedese ha un cane
# 3. Il danese beve the
# 4. La casa verde è a sinistra della casa bianca
# 5. Il padrone della casa verde beve caffè
# 6. La persona che fuma Pall Mall ha gli uccellini
# 7. Il padrone della casa gialla fuma sigarette Dunhill’s
# 8. L’uomo che vive nella casa centrale beve latte
# 9. Il norvegese vive nella prima casa
# 10. L’uomo che fuma Blends vive vicino a quello che ha i gatti
# 11. L’uomo che ha i cavalli vive vicino all’uomo che fuma le Dunhill’s
# 12. L’uomo che fuma le Blue Master beve birra
# 13. Il tedesco fuma le Prince
# 14. Il norvegese vive vicino alla casa blu
# 15. L’uomo che fuma le Blends ha un vicino che beve acqua
optimize!(quiz5case)
solution_summary(quiz5case)
f(x, R)=getindex.(Ref(R),[findfirst(==(1),r) for r in eachrow(x.data)])
permutedims(hcat([f(value.(x),R) for (x,R) in zip([xn,xa,xc,xd,xs],[N,A,C,D,S])]...))
end
# "NO" "DE" "SE" "DK" "UK"
# "birds" "fish" "dog" "cat" "horse"
# "green" "blue" "white" "yellow" "red"
# "coffee" "water" "milk" "the" "beer"
# "PM" "Pr" "Bl" "Du" "BM"
# "NO" "DE" "SE" "UK" "DK"
# "fish" "cat" "dog" "horse" "birds"
# "green" "blue" "yellow" "red" "white"
# "coffee" "water" "milk" "beer" "the"
# "Bl" "Pr" "Du" "BM" "PM"
# "NO" "DE" "SE" "DK" "UK"
# "birds" "cats" "dog" "fishs" "horses"
# "green" "blue" "white" "yellow" "red"
# "coffee" "water" "milk" "the" "beer"
# "PallMall" "Prince" "Blends" "Dunhill" "BlueMaster"
# green vicino white a sinistra
# "NO" "DK" "UK" "DE" "SE"
# "cats" "horses" "birds" "fishs" "dog"
# "yellow" "blue" "red" "green" "white"
# "water" "the" "milk" "coffee" "beer"
# "Dunhill" "Blends" "PallMall" "Prince" "BlueMaster"
possible objective function
This objective function would smooth out all interpretations of rule 4
@objective(quiz5case, Min, sum(xc[:,"white"].*[1:5...]) - sum(xc[:,"green"].*[1:5...]) )
)