326 logic/dell.p
Description
This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.
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:
My Books
