Jump to content
Science Forums

Einstien's puzzle


belovelife

Recommended Posts

  • Replies 38
  • Created
  • Last Reply

Top Posters In This Topic

Sorry to have ignored this thread for the past week :lol:

 

I get an “installer corrupt or incomplete” message when attempting to run the windows installer downloaded from Flowix Games, so haven’t tried the game yet. I found this copy of a game called “Sherlock”, which seems to be the same game, and finally gave it a try. I finished its first (and presumably easiest) game in an rather pathetic 13:58, though I’m sure I’d get quicker with repeated playing.

 

“Einstein’s puzzle” usually refers to a 5x5 (rather than Sherlock’s 6x6) logic puzzle called the “Zebra Puzzle”, which, legend has it, either Albert Einstein or Lewis Carol claimed only about 2% of people could solve. Usually speed isn’t considered much in solving logic puzzles – an experienced logic puzzle solver typically takes 10 to 30 minutes, using paper and pencil or equivalent, much of the time spent organizing the attributes and clues, which computerized version do for you.

 

Some logic puzzles termed “Einstein’s puzzle”, such as the “Fish” variation, can be solved with a “single pass”, while the usual Zebra variation needs 2 guesses, each with 2 possibilities, so may need 4 trys to solve the puzzle.

 

Here’s a small MUMPS program that can solve the Zebra Puzzle, but not the Fish Puzzle – that is, can’t try guesses:

x X(1),X(4) ;X: logic puzzle solver
k B,D,BD s N=5,I="" f  s I=$o(X(2,I)) q:I=""  f J=1:1:N f K=1:1:N s V=$p($p(X(2,I)," ;"),",",J),B(K,I,V)="",BD(I,V)="",D(V)=I ;X(1): init B()
n (X,B,D,BD,N,XWR,C) s (C0,S)="" f  s S=$o(X(3,S)) x X(5),XWR q:S=""&(C=C0)!'C  s:S="" C0=C i S]"" s VV=$p(X(3,S)," ;") x X(4,$p(VV,",")) ;X(4): solve
s V=$p(VV,",",2),I=D(V),K=$p(VV,",",3) zt:'$d(B(K,I,V))  k B(K,I) s B(K,I,V)="" ;X(4,1): is in #
s V1=$p(VV,",",2),I1=D(V1),V2=$p(VV,",",3),I2=D(V2),KI=$p(VV,",",4) f K=1:1:N k:'$d(B(K-KI,I1,V1)) B(K,I2,V2) k:'$d(B(K+KI,I2,V2)) B(K,I1,V1) ;X(4,"="): is/is to left or right of
s V1=$p(VV,",",2),I1=D(V1),V2=$p(VV,",",3),I2=D(V2),KI=$p(VV,",",4) f K=1:1:N k:'$d(B(K-KI,I1,V1))&'$d(B(K+KI,I1,V1)) B(K,I2,V2) k:'$d(B(K-KI,I2,V2))&'$d(B(K+KI,I2,V2)) B(K,I1,V1) ;X(4,"+-="): is next to
n (X,B,N,C) x X(5,1),X(5,2) s C=V]"" x X(5,3) i C s Q="B" f C=0:1 s Q=$q(@Q) q:Q="" ;X(5): check for uniques & clean
s (K,I,V)="" f  s K=$o(B(K)) q:'K  f  s I=$o(B(K,I)) q:I=""  f  s V=$o(B(K,I,V)) q:V=""  s (C1,B1(I,V))=$g(B1(I,V))+1,B1(I,V,K)="",B2(I,V)=K k:C1>1 B2(I,V) ;X(5,1)
s I="",V=1 f K=1:1:N q:V=""  f  s I=$o(X(2,I)) q:I=""  s V=$o(B(K,I,"")) q:V=""  i $o(B(K,I,V))="" k B2(I,V) f KK=1:1:N k:KK-K B(KK,I,V) ;X(5,2)
s (K,V)="" f  s I=$o(B2(I)) q:I=""  f  s V=$o(B2(I,V)) q:V=""  s K=B2(I,V) k B(K,I) s B(K,I,V)="" ;X(5,3)

Here’s the data that defines the Zebra Puzzle:

Blue,Green,Red,White,Yellow ;X(2,"Color")
Brit,Dane,German,Norwegian,Swede ;X(2,"Nationality")
Beer,Coffee,Milk,Tea,Water ;X(2,"Beverage")
Blue Master,Dunhill,Pall Mall,Prince,Blend ;X(2,"Cigar brand")
Cats,Birds,Dogs,Fish,Horses ;X(2,"Pet")

=,Brit,Red ;X(3,1): The Brit lives in a red house.
=,Swede,Dogs ;X(3,2)
=,Dane,Tea ;X(3,3)
=,Green,White,1 ;X(3,4): The green house is on the left of the white, next to it.
=,Green,Coffee ;X(3,5)
=,Pall Mall,Birds ;X(3,6)
=,Yellow,Dunhill ;X(3,7)
1,Milk,3 ;X(3,8)
1,Norwegian,1 ;X(3,9): The Norwegian lives in the first house
+-=,Blend,Cats,1 ;X(3,10): The man who smokes Blends lives next to the one who keeps cats
+-=,Horses,Dunhill,1 ;X(3,11)
=,Blue Master,Beer ;X(3,12)
=,German,Prince ;X(3,13)
+-=,Norwegian,Blue,1  ;X(3,14)
+-=,Blend,Water,1 ;X(3,15)

This program can only process 5 types of rules, using 3 subroutines, but it only need 4 of them for the Zebra Puzzle. Sherlock would need a few more kinds of rule processors. Many logic puzzles would need even more. I’m unaware of any comprehensive review and catalog of these rule types, or an estimate or precise proof of how many there are.

Link to comment
Share on other sites

it only as 5 puzzles :(

:(

Kaser’s Sherlock puzzle program is a free demo. If you send him $20, he’ll sell you the other 64,000 puzzles for it. As the saying goes, programmers gotta eat :hyper:

 

I tweaked (well, significantly enhanced would be a fairer description) the MUMPS code in post #9 to be able to solved the Zebra puzzle (added a “guessing” shell to the original code) with this code:

n (XLPZL,XWR,N,BD,D,B,M,K1,I1,V1) x XLPZL(1),XLPZL(4),XLPZL(8,1),XLPZL(8,2):K1,XLPZL(8,3):'F  ;XLPZL(8): find next hypothetical board
s (K1,I1,V1)="" f  s I=$o(XLPZL(3,"")) q:I=""  q:XLPZL(3,I)[";"  k XLPZL(3,I) ;XLPZL(8,0): initialize
s F=0,M=N+1,(K,I,V,K1,I1)="" f K=1:1:N f  s I=$o(BD(I)) q:I=""  f C=0:1 s V=$o(B(K,I,V)) i V="" s:C-1&(C<M) M=C,K1=K,I1=I s:'M (K1,I1)="" q ;XLPZL(8,1): find first most known unknown node
s V1=$o(B(K1,I1,V1)) i V1]"" s S=$o(XLPZL(3,""))-1,XLPZL(3,S)="1,"_V1_","_K1,V1="",F=1 ;XLPZL(8,2): make hypothesis
s S=$o(XLPZL(3,"")),F=$s(S="":1,1:XLPZL(3,S)[";")  s:F M=N+2 q:F  s V1=$p(XLPZL(3,S),",",2) k XLPZL(3,S) ;XLPZL(8,3): discard hypothesis

, generally fancied up its interface a little, then added a 3 new rule types (“is to the left of”, “isn’t between” and “is between”), and to make it capable of solving a Sherlock puzzle (and a 4th new rule type “multiple is”, that’s not necessary, but keeps the game and program rules one-for-one) with this code:

s V0=VV f I=2:1:$l(V0,",")-1 f J=I:1:$l(V0,",") s VV="=,"_$p(V0,",",I)_","_$p(V0,",",J) x XLPZL(4,0) ;XLPZL(4,"=="): multiple is: "==a,b,c,..." -> "=,a,b", "=,a,c", "=,b,c", etc.
x XLPZL(4,"<",1) f K=1:1:N k:K+KI>F2 B(K,I1,V1) k:N+1-K-KI<F1 B(N+1-K,I2,V2) ;XLPZL(4,"<"): is KI+ to the left of
s V1=$p(VV,",",2),I1=D(V1),V2=$p(VV,",",3),I2=D(V2),KI=$p(VV,",",4),(F1,F2)=0 f K=1:1:N s:$d(B(K,I1,V1))&'F1 F1=K s:$d(B(N+1-K,I2,V2))&'F2 F2=N+1-K ;XLPZL(4,"<",1)
s V0=VV,VV="+-=,"_$p(V0,",",2)_","_$p(V0,",",4)_",2" x XLPZL(4,0) s V2=$p(V0,",",3),I2=D(V2) f K=2:1:N-1 s V1=$p(V0,",",2),I1=D(V1),V3=$p(V0,",",4),I3=D(V3) x XLPZL(4,"'B",1) s V1=V3,I1=I3,V3=$p(V0,",",2),I3=D(V3) x XLPZL(4,"'B",1) ;XLPZL(4,"'B"): V2 isn't between V1 & V3
i $o(B(K-1,I1,""))=V1,$o(B(K-1,I1,V1))="",$o(B(K+1,I3,""))=V3,$o(B(K+1,I3,V3))="" k B(K,I2,V2) ;XLPZL(4,"'B",1)
s V0=VV,V1=$p(V0,",",2),I1=D(V1),V2=$p(V0,",",3),I2=D(V2),V3=$p(V0,",",4),I3=D(V3),VV="+-=,"_V1_","_V2_",1" x XLPZL(4,0) s VV="+-=,"_V1_","_V3_",2" x XLPZL(4,0) s VV="+-=,"_V2_","_V3_",1" x XLPZL(4,0) f K=1:1:N k:'$s($d(B(K-1,I1,V1)):$d(B(K+1,I3,V3)),$d(B(K-1,I3,V3)):$d(B(K+1,I1,V1)),1:0) B(K,I2,V2) ;XLPZL(4,"B"): V2 is between V1 & V3

The whole program, with the board and rules for “Sherlock 5x5 puzzle#1 by Everett Kaser (kaser.com)”, is:

n (XLPZL) m XWR=XLPZL(0,1) x XLPZL(8,0) f  x XLPZL(8),$g(XWR(7)):M>N q:$g(XWR(-1))  ;XLPZL: logic puzzle solver
x XLPZL(6) s XWR(0)=$g(XWR(0))+1 w XWR(0)," ",C r R,! W:S]"" XLPZL(3,S),! ;XLPZL(0,1): interactive display
s XWR(0)=$g(XWR(0))+1 i '$g(XWR(4,-1)) x XLPZL(6) w XWR(0)," ",C r " Skip to solution? NO/ ",R,! s:$tr(R,"q","Q")?1(1".",1"^",1"Q",1"q").e (XWR(-1),XWR(4,-1))=1,R="" s:$tr(R,"yes","YES")?1"Y".1"ES" XWR(4,-1)=1,R="" x:R]"" XLPZL(0,1,4,"?") w:S]""&'$g(XWR(4,-1)) XLPZL(3,S),! ;XLPZL(0,1,4): step display
s R=0 f  s R=$o(XLPZL(0,1,4,"?",R)) q:'R  w $p(XLPZL(0,1,4,"?",R)," ;"),! ;XLPZL(0,1,4,"?")
Enter - Enter (nothing) to show each step of the process ;XLPZL(0,1,4,"?",1)
     - 'Q' to quit ;XLPZL(0,1,4,"?",2)
     - 'Y' to skip showing each step and display the next solution ;XLPZL(0,1,4,"?",3)
This program solves "logic puzzles. ;XLPZL(0,1,4,"?",11)
To change puzzles: quit, ;XLPZL(0,1,4,"?",21)
k XLPZL(2),XLPZL(3) x XRX  ;XLPZL(0,1,4,"?",23)
enter new pieces and rules, then restart  ;XLPZL(0,1,4,"?",24)
A library of puzzles may be loaded from ^XD("XLPZL",1) ;XLPZL(0,1,4,"?",31)
New rule types may be defined by adding of XLPZL(4,ruletype) xecute code nodes. ;XLPZL(0,1,4,"?",41)
x XLPZL(7) W XWR(0)," Continue? NO/ " r R,! s:R'?1"Y".1"ES" XWR(-1)=1 s XWR(4,-1)=0 ;XLPZL(0,1,7): solution display
k B,D,BD s N=5,I="" f  s I=$o(XLPZL(2,I)) q:I=""  f J=1:1:N f K=1:1:N s V=$p($p(XLPZL(2,I)," ;"),",",J),B(K,I,V)="",BD(I,V)="",D(V)=I ;XLPZL(1): init B()
Sherlock 5x5 puzzle#1 by Everett Kaser (kaser.com) ;XLPZL(2)
11,12,13,14,15 ;XLPZL(2,1)
21,22,23,24,25 ;XLPZL(2,2)
31,32,33,34,35 ;XLPZL(2,3)
41,42,43,44,45 ;XLPZL(2,4)
51,52,53,54,55 ;XLPZL(2,5)
=,12,24 ;XLPZL(3,-6)
=,35,42 ;XLPZL(3,-5)
==,13,35,53 ;XLPZL(3,-4)
=,34,43 ;XLPZL(3,-3)
==,23,31,52 ;XLPZL(3,-2)
==,32,44,55 ;XLPZL(3,-1)
+-=,44,23,1 ;XLPZL(3,1)
+-=,33,51,1 ;XLPZL(3,2)
+-=,31,25,1 ;XLPZL(3,3)
+-=,14,54,1 ;XLPZL(3,4)
'B,51,41,52 ;XLPZL(3,5)
'B,44,55,35 ;XLPZL(3,6)
<,55,53,1 ;XLPZL(3,7)
'B,13,43,22 ;XLPZL(3,8)
'B,21,51,11 ;XLPZL(3,9)
'B,41,52,53 ;XLPZL(3,10)
B,23,13,34 ;XLPZL(3,11)
n (XLPZL,B,D,BD,N,XWR,C) s (C0,S)="" f  s S=$o(XLPZL(3,S)) x XLPZL(5),$g(XWR(4)) q:S=""&(C=C0)!'C  s:S="" C0=C i S]"" s VV=$p(XLPZL(3,S)," ;") x XLPZL(4,0) ;XLPZL(4): solve
n (XLPZL,B,N,D,VV) x XLPZL(4,$p(VV,",")) ;XLPZL(4,0)
s V=$p(VV,",",2),I=D(V),K=$p(VV,",",3) zt:'$d(B(K,I,V))  k B(K,I) s B(K,I,V)="" ;XLPZL(4,1): is in house #
s V0=VV,VV="+-=,"_$p(V0,",",2)_","_$p(V0,",",4)_",2" x XLPZL(4,0) s V2=$p(V0,",",3),I2=D(V2) f K=2:1:N-1 s V1=$p(V0,",",2),I1=D(V1),V3=$p(V0,",",4),I3=D(V3) x XLPZL(4,"'B",1) s V1=V3,I1=I3,V3=$p(V0,",",2),I3=D(V3) x XLPZL(4,"'B",1) ;XLPZL(4,"'B")
i $o(B(K-1,I1,""))=V1,$o(B(K-1,I1,V1))="",$o(B(K+1,I3,""))=V3,$o(B(K+1,I3,V3))="" k B(K,I2,V2) ;XLPZL(4,"'B",1)
s V1=$p(VV,",",2),I1=D(V1),V2=$p(VV,",",3),I2=D(V2),KI=$p(VV,",",4) f K=1:1:N k:'$d(B(K-KI,I1,V1))&'$d(B(K+KI,I1,V1)) B(K,I2,V2) k:'$d(B(K-KI,I2,V2))&'$d(B(K+KI,I2,V2)) B(K,I1,V1) ;XLPZL(4,"+-="): is next to
x XLPZL(4,"<",1) f K=1:1:N k:K+KI>F2 B(K,I1,V1) k:N+1-K-KI<F1 B(N+1-K,I2,V2) ;XLPZL(4,"<"): is KI+ to the left of
s V1=$p(VV,",",2),I1=D(V1),V2=$p(VV,",",3),I2=D(V2),KI=$p(VV,",",4),(F1,F2)=0 f K=1:1:N s:$d(B(K,I1,V1))&'F1 F1=K s:$d(B(N+1-K,I2,V2))&'F2 F2=N+1-K ;XLPZL(4,"<",1)
s V1=$p(VV,",",2),I1=D(V1),V2=$p(VV,",",3),I2=D(V2),KI=$p(VV,",",4) f K=1:1:N k:'$d(B(K-KI,I1,V1)) B(K,I2,V2) k:'$d(B(K+KI,I2,V2)) B(K,I1,V1) ;XLPZL(4,"="): is/is to left or right of
s V0=VV f I=2:1:$l(V0,",")-1 f J=I:1:$l(V0,",") s VV="=,"_$p(V0,",",I)_","_$p(V0,",",J) x XLPZL(4,0) ;XLPZL(4,"=="): multiple is: "==a,b,c,..." -> "=,a,b", "=,a,c", "=,b,c", etc.
s V0=VV,V1=$p(V0,",",2),I1=D(V1),V2=$p(V0,",",3),I2=D(V2),V3=$p(V0,",",4),I3=D(V3),VV="+-=,"_V1_","_V2_",1" x XLPZL(4,0) s VV="+-=,"_V1_","_V3_",2" x XLPZL(4,0) s VV="+-=,"_V2_","_V3_",1" x XLPZL(4,0) f K=1:1:N k:'$s($d(B(K-1,I1,V1)):$d(B(K+1,I3,V3)),$d(B(K-1,I3,V3)):$d(B(K+1,I1,V1)),1:0) B(K,I2,V2) ;XLPZL(4,"B")
n (XLPZL,B,N,C) x XLPZL(5,1),XLPZL(5,2) s C=V]"" x XLPZL(5,3) i C s Q="B" f C=0:1 s Q=$q(@Q) q:Q="" ;XLPZL(5): check for uniques & clean
s (K,I,V)="" f  s K=$o(B(K)) q:'K  f  s I=$o(B(K,I)) q:I=""  f  s V=$o(B(K,I,V)) q:V=""  s (C1,B1(I,V))=$g(B1(I,V))+1,B1(I,V,K)="",B2(I,V)=K k:C1>1 B2(I,V) ;XLPZL(5,1)
s I="",V=1 f K=1:1:N q:V=""  f  s I=$o(XLPZL(2,I)) q:I=""  s V=$o(B(K,I,"")) q:V=""  i $o(B(K,I,V))="" k B2(I,V) f KK=1:1:N k:KK-K B(KK,I,V) ;XLPZL(5,2)
s (K,V)="" f  s I=$o(B2(I)) q:I=""  f  s V=$o(B2(I,V)) q:V=""  s K=B2(I,V) k B(K,I) s B(K,I,V)="" ;XLPZL(5,3)
n (XLPZL,B,BD,N) x XLPZL(6,0),XLPZL(6,1) w ! ;XLPZL(6): display B()
f K=1:1:N w ?N+2*(K+1),K ;XLPZL(6,0)
s (I,V)="" f  s I=$o(BD(I)) q:I=""  w !,$e(I,1,N+2*2-2) f K=1:1:N w ?N+2*(K+1) f  s V=$o(BD(I,V)) q:V=""  w $s($d(B(K,I,V)):$e(V),1:" ") ;XLPZL(6,1)
n (XLPZL,B,BD,N) x XLPZL(7,1),XLPZL(7,0),XLPZL(7,2) w ! ;XLPZL(7): final display B()
s C=L+2 f K=1:1:N w ?C,K s C=$g(L(K),$l(K))+2+C ;XLPZL(7,0)
s (I,V,L)="" f  s I=$o(BD(I)) q:I=""  s:$l(I)>L L=$l(I) f K=1:1:N s V=$o(B(K,I,"")),V=$S(V="":"!",$o(B(K,I,V))="":V,1:"?") s V(K,I)=V s:$l(V)>$g(L(K)) L(K)=$l(V) ;XLPZL(7,1)
f  s I=$o(BD(I)) q:I=""  s C=L+2 w !,I f K=1:1:N w ?C,$g(V(K,I)) s C=$g(L(K),$l(K))+2+C ;XLPZL(7,2)
n (XLPZL,XWR,N,BD,D,B,M,K1,I1,V1) x XLPZL(1),XLPZL(4),XLPZL(8,1),XLPZL(8,2):K1,XLPZL(8,3):'F  ;XLPZL(8): find next hypothetical board
s (K1,I1,V1)="" f  s I=$o(XLPZL(3,"")) q:I=""  q:XLPZL(3,I)[";"  k XLPZL(3,I) ;XLPZL(8,0): initialize
s F=0,M=N+1,(K,I,V,K1,I1)="" f K=1:1:N f  s I=$o(BD(I)) q:I=""  f C=0:1 s V=$o(B(K,I,V)) i V="" s:C-1&(C<M) M=C,K1=K,I1=I s:'M (K1,I1)="" q ;XLPZL(8,1): find first most known unknown node
s V1=$o(B(K1,I1,V1)) i V1]"" s S=$o(XLPZL(3,""))-1,XLPZL(3,S)="1,"_V1_","_K1,V1="",F=1 ;XLPZL(8,2): make hypothesis
s S=$o(XLPZL(3,"")),F=$s(S="":1,1:XLPZL(3,S)[";")  s:F M=N+2 q:F  s V1=$p(XLPZL(3,S),",",2) k XLPZL(3,S) ;XLPZL(8,3): discard hypothesis

Now that I’ve gotten the code down, I need some help from somebody who’s actually good at these puzzles, like belovelife, to answer some questions about them.

 

A brief description of how the XLPZL program solves logic puzzles: It applies, in whatever order they’re defined, each given rule (AKA clue) to the “what’s known” diagram (the board with its colorful cards in the Sherlock game), removing cards until the board is unchanged after a round of applying all of the rules. If the board is solved - one card in each square - it shows the solution and lets you quit. Otherwise, it adds a “hypothesis” rule consisting of a guess of the first card in the first square with the fewest but more than 1 cards, reinitializes the board, and trys again. If the hypothesis rule yields a contradiction (a square on the board with zero cards in it), it’s replace with a guess of the next card in the first square with the fewest but more than 1 cards. This is repeated until either a solution is found, or there are no more guesses left, in which case the given clues are contradictory, and there’s no solution.

 

When I have XLPZL play 5x5 puzzle #1 (0 handicap) of Kaser’s Sherlock game, it’s necessary to make one correct guess between 2 possible cards (person #2 or person #5 in square #1, the correct guess being person #5). The way Kaser’s game scores a player, this means there’s an element of luck in whether you’ll win the game with 0 or 1 “notify” penalties for incorrect clicks.

 

My question: is there some subtle rule XLPZL is missing that allows a solution with no guessing?

 

The need to guess and number of correct guesses for a program like XLPZL varies from among logic puzzles. For example, the Zebra puzzle requires 2 successful guesses (and can have 3 unsuccessful leading to a contradiction), the Fish puzzle needs no guesses, and, the Sherlock puzzle above, 1 guess.

 

Another question:

With XLPZL, I just add rule types as needed to solve new puzzles. The Zebra and Fish puzzles needed 2 rule types: “X is in position A” (XLPZL(4,"1")); “X and Y are N positions apart” (XLPZL(4,"+-=")). XLPZL has an additional “X and Y are N positions to the left/right of one another” rule type (XLPZL(4,"=")), but doesn’t need it for these puzzles. Sherlock puzzles need 3 additional rules: “X is to the left or Y” (XLPZL(4,"<")), “Z is between X and Y” (XLPZL(4,"B")), and “1 square is between X and Y, and Z’s not in it” (XLPZL(4,"'B")). XLPZL has an unnecessary “X and Y and … are 0 positions apart” (XLPZL(4,"==")) which expands into multiple applications of XLPZL(4,"="), and allows entering Sherlock rules exactly as they’re given.

 

My question: is there some collection of rule types that any collection of logic puzzle rules can be written in?

 

Given the decades that people have been writing programs, both computer and human, to solve logic puzzles, I suspect questions like these have been rigorously answered, but haven’t come across any such literature.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...

×
×
  • Create New...