(71B) PUZZLER - The Program that Thinx

[Joe Horn]

[Copied and de-typo'd from HPX Exchange, V1 N4 (Jul 87 - Mar 88), page 6. -jkh-]

According to INSIGHT magazine, the only way we can program artificial intelligence is with a parallel-processing mainframe like The Connection Machine. Not even a Cray can hack it, they said. What would they say about a handheld that thinx? Imagine your HP-71 solving the following puzzler, given only the English clues:

Billy, Willy, Gerald and Oliver live (not respectively) in a Blue house, White house, Green house and Orange house, and have as pets (not respectively) a Bear, Walrus, Giraffe and Orangutan.

The Clues:
(1) Nobody's name, house color, or pet, begin with the same letter.
(2) Billy never saw the walrus that lives in the green house.
(3) Gerald never saw the bear.

Who lives where with what pet?

This type of "logic puzzle" is designed to exercise the mind and be a pleasant way to kill some time. Solving them on a machine that does all the thinking for you is certainly missing the point! But then, many crossword puzzle addicts use electronic dictionaries to help with their puzzles. So why not?

The program listed below, called PUZZLER, solves any logic puzzle similar to the Billy, Willy, Gerald and Oliver puzzle above. It even solves the famous "Who Owns the Zebra?" puzzle.

PUZZLER — HP-71B BASIC — 1768 bytes

Code:

1 ! PUZZLER ! The Program that Thinx ! Joseph K. Horn ! Oct 1987
2 ! Solves "Who Owns the Zebra"-type logic puzzles ! Uses no lexfiles
10 CALL PUZZLER @ SUB PUZZLER @ OPTION BASE 1 @ STD 
20 INPUT "How many groups? ";A
30 INPUT "Items per group? ";B
40 C=A*B @ D=C*(A-1)/2 @ INTEGER M(C,C),Q(D),R(D) @ DIM N$(C)[20],A$[96]
50 FOR J=1 TO C STEP B @ FOR K=J TO J+B-1 @ FOR L=J TO J+B-1
60 M(K,L)=-1 @ NEXT L @ M(K,K)=1 @ NEXT K @ NEXT J
70 INPUT "Auto/Quick? ","A";A$ @ X=FLAG(3,UPRC$(A$)[1,1]="A")
80 FOR J=1 TO A @ FOR K=1 TO B @ DISP "Group";J;"item ";STR$(K);
90 INPUT ": ",CHR$(64+J)&STR$(K);A$ @ N$((J-1)*B+K)=UPRC$(A$) @ NEXT K @ NEXT J
100 INPUT "Clue? ";A$ @ A$=" "&UPRC$(A$)&" "
110 IF POS(A$,"THINK") THEN 260
120 K=0 @ L=0 @ FOR N=1 TO C
130 V=POS(A$," "&N$(N)&" ")+POS(A$," "&N$(N)&" 'S ")+POS(A$," "&N$(N)&"S ")
140 IF NOT V THEN 150 ELSE A$[V,V+LEN(N$(N))]="" @ IF K THEN L=N ELSE K=N
150 NEXT N @ T=1 @ IF POS(A$," NOT ") OR POS(A$,"N'T ") THEN T=-1
160 IF POS(A$," NEVER ") OR POS(A$," - ") OR POS(A$," NO ") THEN T=-1
170 IF NOT (K AND L) THEN DISP "What???" @ BEEP @ BEEP @ WAIT 2 @ GOTO 100
180 IF POS(A$,"?") THEN 490
190 IF NOT M(K,L) THEN 220
200 IF M(K,L)=T THEN DISP "Right!" ELSE DISP "Wrong!"
210 BEEP @ BEEP @ WAIT 2 @ GOTO 100
220 M(K,L)=T @ M(L,K)=T
230 IF T=1 THEN P=P+1 @ Q(P)=K @ R(P)=L
240 IF P=D THEN 450
250 IF NOT FLAG(3) THEN 100
260 CFLAG 1 @ IF P=0 THEN 350
270 FOR J=P TO 1 STEP -1 @ FOR K=1 TO C
280 IF M(K,Q(J))=M(K,R(J)) THEN 340
290 U=Q(J) @ V=R(J) @ SFLAG 1 @ IF M(K,U) THEN U=V @ V=Q(J)
300 T=M(K,V) @ IF T=1 THEN P=P+1 @ Q(P)=K @ R(P)=U
310 M(K,U)=T @ M(U,K)=T
320 DISP N$(K); @ IF T=1 THEN DISP " + "; ELSE DISP " - ";
330 DISP N$(U) @ BEEP @ IF P=D THEN 450
340 NEXT K @ NEXT J @ IF FLAG(1) THEN 260
350 FOR J=1 TO C STEP B @ FOR K=1 TO C STEP B @ IF J=K THEN 430
360 FOR L=J TO J+B-1 @ T=B @ FOR N=K TO K+B-1 @ T=T+M(L,N)
370 NEXT N @ IF T>1 THEN 420 ELSE SFLAG 1
380 FOR N=K TO C @ IF NOT M(L,N) THEN 400
390 NEXT N
400 M(L,N)=T @ M(N,L)=T @ DISP N$(L);" + ";N$(N) @ BEEP 
410 P=P+1 @ Q(P)=L @ R(P)=N @ IF P=D THEN 450
420 NEXT L
430 NEXT K @ NEXT J
440 IF FLAG(1) THEN 260 ELSE 100
450 DISP "THE PUZZLE IS SOLVED!" @ BEEP 800,.5 @ WAIT 2
460 FOR J=1 TO B @ DISP N$(J);
470 FOR K=B+1 TO C @ IF M(J,K)=1 THEN DISP " + ";N$(K);
480 NEXT K @ DISP @ NEXT J @ CFLAG 1,3,4 @ END 
490 FOR K=K-RMD(K-1,B) TO K+B-1 @ DISP N$(K);
500 FOR L1=L-RMD(L-1,B) TO L1+B-1 @ IF NOT M(K,L1) THEN 530
510 IF M(K,L1)=1 THEN DISP " + "; ELSE DISP " - ";
520 DISP N$(L1);
530 NEXT L1 @ DISP @ NEXT K @ GOTO 100

RUN PUZZLER and input the number of groups and the number of items per group. In the Billy, Willy, Gerald and Oliver puzzle, there are three groups (men, houses, pets) and four items per group (B, W, G, O).

PUZZLER will ask if you prefer Auto or Quick processing. Auto mode means that PUZZLER thinks about every input after each one is typed in. This mode gives the impression of artificial intelligence the best; it seems to be thinking all the time. Quick mode means that PUZZLER lets you input the clues quickly, and then type THINK to force it to "think" about the clues. This mode is practical when there is a large number of groups and items.

Then input names for every item, as indicated. If you wish, you may use the spreadsheet-style names that are automatically supplied; or type your own names over them. We'll use BILLY, WILLY, GERALD, OLIVER, BLUE, WHITE, GREEN, ORANGE, BEAR, WALRUS, GIRAFFE and ORANGUTAN as our inputs for the sample puzzle.

Then input the clues. You can usually type the clues in English directly, but sometimes you must do a little simplification so that PUZZLER won't get puzzled. You must use the names that you supplied. PUZZLER looks for only logical "connections" or "disconnections". The following are all equivalent statements:

BILLY NEVER SAW THE WALRUS
BILLY DOESN'T OWN THE WALRUS
BILLY DOES NOT OWN THE WALRUS
BILLY NOT WALRUS
BILLY - WALRUS

And these are all equivalent:

THE WALRUS LIVES IN THE GREEN HOUSE
THE WALRUS IS IN THE GREEN HOUSE
WALRUS IS GREEN
WALRUS + GREEN
WALRUS GREEN

Of course, we must input the "not respectively" clues: BILLY - BLUE, BILLY - BEAR, BEAR - BLUE, WILLY - WHITE, etc. Keep inputting clues until PUZZLER discovers the answer and prints it out.

Whenever PUZZLER discovers a logical connection or disconnection on its own, it prints it. If you don't have a video connected, or a printer acting as a video (DISPLAY IS PRINTER), then you'd better set the DELAY to something long enough to be useful, or change the program to pause after each display.

If you wish to examine the known relationships between two items, input them with a "?" between, like this:

BILLY ? BEAR

This will result in all the relations between all the items in those two groups to be listed. This is useful when you are solving a puzzle with clues like "The Englishman lives next door to the man who smokes Chesterfields."

The answer to the Billy puzzle is... well, I'll let you and your HP-71 figure it out.

Artificial intelligence? No, not really, but it IS intriguing.

For your entertainment, here's the puzzle that started this craze.

Quote:Who Owns The Zebra?

1. There are five houses.
2. The Englishman lives in the red house.
3. The Spaniard owns the dog.
4. Coffee is drunk in the green house.
5. The Ukrainian drinks tea.
6. The green house is immediately to the right of the ivory house.
7. The Old Gold smoker owns snails.
8. Kools are smoked in the yellow house.
9. Milk is drunk in the middle house.
10. The Norwegian lives in the first house.
11. The man who smokes Chesterfields lives in the house next to the man with the fox.
12. Kools are smoked in the house next to the house where the horse is kept.
13. The Lucky Strike smoker drinks orange juice.
14. The Japanese smokes Parliaments.
15. The Norwegian lives next to the blue house.

Now, who drinks water? And who owns the zebra?

In the interest of clarity, it must be added that each of the five houses is painted a different color, and their inhabitants are of different national extractions, own different pets, drink different beverages and smoke different brands of American cigarets [sic]. One other thing: in statement 6, right means your right.

The "Who Owns the Zebra?" puzzle was first published in Life International Magazine on December 17, 1962. The version above is the original version.

[Jim Horn]

Good Heavens, Joe, does that bring back memories - of a fairly newly minted USAF Second Lieutenant visiting his high-school brother in the exotic and far away lands of Orange County in 1976... I'm still amazed at how you immediately understood my poorly-illustrated description of how to solve problems like these using a matrix drawn on paper. That you had a program to do it so well in BASIC in short order - well, no wonder you ended up hearing from as far away as Australia about it.

Great work!