# 326 logic/dell.p

How can I solve logic puzzles (e.g., as published by Dell) automatically?

logic/dell.s

#include	<setjmp.h>

#define	EITHER		if (S[1] = S[0], ! setjmp((S++)->jb)) {
#define	OR		} else EITHER
#define	REJECT		longjmp((--S)->jb, 1)
#define	END_EITHER	} else REJECT;

/* values in tmat: */
#define	T_UNK	0
#define	T_YES	1
#define	T_NO	2

#define	Val(t1,t2)	(S->tmat[t1][t2])
#define	CLASS(x)		\
(((x) / NUM_ITEM) * NUM_ITEM)
#define	EVERY_TOKEN(x)		\
(x = 0; x < TOT_TOKEN; x++)
#define	EVERY_ITEM(x, class)	\
(x = CLASS(class); x < CLASS(class) + NUM_ITEM; x++)

#define	BEGIN						\
struct state {						\
char	tmat[TOT_TOKEN][TOT_TOKEN];		\
jmp_buf jb;					\
} States[100], *S = States;				\
\
main()							\
{							\
int	token;					\
\
for EVERY_TOKEN(token)				\
yes(token, token);			\
EITHER

/* Here is the problem-specific data */
#define	NUM_ITEM	5
#define	NUM_CLASS	6
#define	TOT_TOKEN	(NUM_ITEM * NUM_CLASS)

#define	HOUSE_0		0
#define	HOUSE_1		1
#define	HOUSE_2		2
#define	HOUSE_3		3
#define	HOUSE_4		4

#define	ENGLISH		5
#define	SPANISH		6
#define	NORWEG		7
#define	UKRAIN		8
#define	JAPAN		9

#define	GREEN		10
#define	RED		11
#define	IVORY		12
#define	YELLOW		13
#define	BLUE		14

#define	COFFEE		15
#define	TEA		16
#define	MILK		17
#define	OJUICE		18
#define	WATER		19

#define	DOG		20
#define	SNAIL		21
#define	FOX		22
#define	HORSE		23
#define	ZEBRA		24

#define	OGOLD		25
#define	PLAYER		26
#define	CHESTER		27
#define	LSTRIKE		28
#define	PARLIA		29

char *names[] = {
"HOUSE_0", "HOUSE_1", "HOUSE_2", "HOUSE_3", "HOUSE_4",
"ENGLISH", "SPANISH", "NORWEG", "UKRAIN", "JAPAN",
"GREEN", "RED", "IVORY", "YELLOW", "BLUE",
"COFFEE", "TEA", "MILK", "OJUICE", "WATER",
"DOG", "SNAIL", "FOX", "HORSE", "ZEBRA",
"OGOLD", "PLAYER", "CHESTER", "LSTRIKE", "PARLIA",
};

BEGIN

yes(ENGLISH, RED);	/* Clue 1 */
yes(SPANISH, DOG);	/* Clue 2 */
yes(COFFEE, GREEN);	/* Clue 3 */
yes(UKRAIN, TEA);	/* Clue 4 */

EITHER			/* Clue 5 */
yes(IVORY, HOUSE_0);
yes(GREEN, HOUSE_1);
OR
yes(IVORY, HOUSE_1);
yes(GREEN, HOUSE_2);
OR
yes(IVORY, HOUSE_2);
yes(GREEN, HOUSE_3);
OR
yes(IVORY, HOUSE_3);
yes(GREEN, HOUSE_4);
END_EITHER

yes(OGOLD, SNAIL);	/* Clue 6 */
yes(PLAYER, YELLOW);	/* Clue 7 */
yes(MILK, HOUSE_2);	/* Clue 8 */
yes(NORWEG, HOUSE_0);	/* Clue 9 */

EITHER			/* Clue 10 */
yes(CHESTER, HOUSE_0);
yes(FOX, HOUSE_1);
OR
yes(CHESTER, HOUSE_4);
yes(FOX, HOUSE_3);
OR
yes(CHESTER, HOUSE_1);
EITHER	yes(FOX, HOUSE_0);
OR	yes(FOX, HOUSE_2);
END_EITHER
OR
yes(CHESTER, HOUSE_2);
EITHER	yes(FOX, HOUSE_1);
OR	yes(FOX, HOUSE_3);
END_EITHER
OR
yes(CHESTER, HOUSE_3);
EITHER	yes(FOX, HOUSE_2);
OR	yes(FOX, HOUSE_4);
END_EITHER
END_EITHER

EITHER			/* Clue 11 */
yes(PLAYER, HOUSE_0);
yes(HORSE, HOUSE_1);
OR
yes(PLAYER, HOUSE_4);
yes(HORSE, HOUSE_3);
OR
yes(PLAYER, HOUSE_1);
EITHER	yes(HORSE, HOUSE_0);
OR	yes(HORSE, HOUSE_2);
END_EITHER
OR
yes(PLAYER, HOUSE_2);
EITHER	yes(HORSE, HOUSE_1);
OR	yes(HORSE, HOUSE_3);
END_EITHER
OR
yes(PLAYER, HOUSE_3);
EITHER	yes(HORSE, HOUSE_2);
OR	yes(HORSE, HOUSE_4);
END_EITHER
END_EITHER

yes(LSTRIKE, OJUICE);	/* Clue 12 */
yes(JAPAN, PARLIA);	/* Clue 13 */

EITHER			/* Clue 14 */
yes(NORWEG, HOUSE_0);
yes(BLUE, HOUSE_1);
OR
yes(NORWEG, HOUSE_4);
yes(BLUE, HOUSE_3);
OR
yes(NORWEG, HOUSE_1);
EITHER	yes(BLUE, HOUSE_0);
OR	yes(BLUE, HOUSE_2);
END_EITHER
OR
yes(NORWEG, HOUSE_2);
EITHER	yes(BLUE, HOUSE_1);
OR	yes(BLUE, HOUSE_3);
END_EITHER
OR
yes(NORWEG, HOUSE_3);
EITHER	yes(BLUE, HOUSE_2);
OR	yes(BLUE, HOUSE_4);
END_EITHER
END_EITHER

/* End of problem-specific data */

solveit();
OR
printf("All solutions found\n");
exit(0);
END_EITHER
}

no(a1, a2)
{
int	non1, non2, token;

if (Val(a1, a2) == T_YES)
REJECT;
else if (Val(a1, a2) == T_UNK) {
Val(a1, a2) = T_NO;
no(a2, a1);
non1 = non2 = -1;

for EVERY_ITEM(token, a1)
if (Val(token, a2) != T_NO)
if (non1 == -1)
non1 = token;
else
break;
if (non1 == -1)
REJECT;
else if (token == CLASS(a1) + NUM_ITEM)
yes(non1, a2);

for EVERY_TOKEN(token)
if (Val(token, a1) == T_YES)
no(a2, token);
}
}

yes(a1, a2)
{
int	token;

if (Val(a1, a2) == T_NO)
REJECT;
else if (Val(a1, a2) == T_UNK) {
Val(a1, a2) = T_YES;
yes(a2, a1);
for EVERY_ITEM(token, a1)
if (token != a1)
no(token, a2);
for EVERY_TOKEN(token)
if (Val(token, a1) == T_YES)
yes(a2, token);
else if (Val(token, a1) == T_NO)
no(a2, token);
}
}

solveit()
{
int	token, tok2;

for EVERY_TOKEN(token)
for (tok2 = token; tok2 < TOT_TOKEN; tok2++)
if (Val(token, tok2) == T_UNK) {
EITHER
yes(token, tok2);
OR
no(token, tok2);
END_EITHER;
return solveit();
}
printf("Solution:\n");
for EVERY_ITEM(token, 0) {
for (tok2 = NUM_ITEM; tok2 < TOT_TOKEN; tok2++)
if (Val(token, tok2) == T_YES)
printf("\t%s %s\n",names[token],names[tok2]);
printf("\n");
}
REJECT;
}

---
james@crc.ricoh.com (James Allen)

Continue to: