Предупреждение: Я не уверен, что это то, что вы ищете, потому что я не читал Искусственный интеллект: современный подход , но я думаю, что интересно тем не менее.
У Эди Вейц есть интересная страница об этой загадке с объясненным источником в Common Lisp и других источниках в C ++ и Common Lisp без подробных комментариев. Я нашел источник C ++ Клауса Бетцлера особенно интересным (немного переформатированный для большей ясности):
// einstein.cpp (c) Klaus Betzler 20011218
// Klaus.Betzler@uos.de
// `Einstein's Riddle´, the rules:
// 1 The Brit lives in the red house
// 2 The Swede keeps dogs as pets
// 3 The Dane drinks tea
// 4 The green house is on the left of the white house
// 5 The green house's owner drinks coffee
// 6 The person who smokes Pall Mall rears birds
// 7 The owner of the yellow house smokes Dunhill
// 8 The man living in the centre house drinks milk
// 9 The Norwegian lives in the first house
// 10 The person who smokes Marlboro lives next to the one who keeps cats
// 11 The person who keeps horses lives next to the person who smokes Dunhill
// 12 The person who smokes Winfield drinks beer
// 13 The German smokes Rothmans
// 14 The Norwegian lives next to the blue house
// 15 The person who smokes Marlboro has a neigbor who drinks water
#undef WIN32 // #undef for Linux
#include <stdio.h>
#ifdef WIN32
#include <windows.h>
#endif
inline unsigned long BIT(unsigned n) {return 1<<n;}
const unsigned long
yellow = BIT( 0),
blue = BIT( 1),
red = BIT( 2),
green = BIT( 3),
white = BIT( 4),
norwegian = BIT( 5),
dane = BIT( 6),
brit = BIT( 7),
german = BIT( 8),
swede = BIT( 9),
water = BIT(10),
tea = BIT(11),
milk = BIT(12),
coffee = BIT(13),
beer = BIT(14),
dunhill = BIT(15),
marlboro = BIT(16),
pallmall = BIT(17),
rothmans = BIT(18),
winfield = BIT(19),
cat = BIT(20),
horse = BIT(21),
bird = BIT(22),
fish = BIT(23),
dog = BIT(24);
const char * Label[] = {
"Yellow", "Blue", "Red", "Green", "White",
"Norwegian","Dane", "Brit", "German", "Swede",
"Water", "Tea", "Milk", "Coffee", "Beer",
"Dunhill", "Marlboro","Pallmall","Rothmans","Winfield",
"Cat", "Horse", "Bird", "Fish", "Dog"
};
const unsigned long color = yellow +blue +red +green +white;
const unsigned long country = norwegian+dane +brit +german +swede;
const unsigned long drink = water +tea +milk +coffee +beer;
const unsigned long cigar = dunhill +marlboro+pallmall+rothmans+winfield;
const unsigned long animal = cat +horse +bird +fish +dog;
unsigned long house [5] = {norwegian, blue, milk, 0, 0}; // rules 8,9,14
unsigned long result[5];
const unsigned long comb[] = { // simple rules
brit+red, // 1
swede+dog, // 2
dane+tea, // 3
green+coffee, // 5
pallmall+bird, // 6
yellow+dunhill, // 7
winfield+beer, // 12
german+rothmans // 13
};
const unsigned long combmask[] = { // corresponding selection masks
country+color,
country+animal,
country+drink,
color+drink,
cigar+animal,
color+cigar,
cigar+drink,
country+cigar
};
inline bool SimpleRule(unsigned nr, unsigned which)
{
if (which<8) {
if ((house[nr]&combmask[which])>0)
return false;
else {
house[nr]|=comb[which];
return true;
}
}
else { // rule 4
if ((nr==4)||((house[nr]&green)==0))
return false;
else
if ((house[nr+1]&color)>0)
return false;
else {
house[nr+1]|=white;
return true;
}
}
}
inline void RemoveSimple(unsigned nr, unsigned which)
{
if (which<8)
house[nr]&=~comb[which];
else
house[nr+1]&=~white;
}
inline bool DunhillRule(unsigned nr, int side) // 11
{
if (((side==1)&&(nr==4))||((side==-1)&&(nr==0))||((house[nr]&dunhill)==0))
return false;
if ((house[nr+side]&animal)>0)
return false;
house[nr+side]|=horse;
return true;
}
inline void RemoveDunhill(unsigned nr, unsigned side)
{
house[nr+side]&=~horse;
}
inline bool MarlboroRule(unsigned nr) // 10 + 15
{
if ((house[nr]&cigar)>0)
return false;
house[nr]|=marlboro;
if (nr==0) {
if ((house[1]&(animal+drink))>0)
return false;
else {
house[1]|=(cat+water);
return true;
}
}
if (nr==4) {
if ((house[3]&(animal+drink))>0)
return false;
else {
house[3]|=(cat+water);
return true;
}
}
int i,k;
for (i=-1; i<2; i+=2) {
if ((house[nr+i]&animal)==0) {
house[nr+i]|=cat;
for (k=-1; k<2; k+=2) {
if ((house[nr+k]&drink)==0) {
house[nr+k]|=water;
return true;
}
}
}
}
return false;
}
void RemoveMarlboro(unsigned m)
{
house[m]&=~marlboro;
if (m>0)
house[m-1]&=~(cat+water);
if (m<4)
house[m+1]&=~(cat+water);
}
void Recurse(unsigned recdepth)
{
unsigned n, m;
for (n=0; n<5; n++) {
if (recdepth<9) { // simple rules
if (SimpleRule(n, recdepth)) {
Recurse(recdepth+1);
RemoveSimple(n, recdepth);
}
}
else { // Dunhill and Marlboro
for (int side=-1; side<2; side+=2)
if (DunhillRule(n, side)) {
for (m=0; m<5; m++)
if (MarlboroRule(m))
for (int r=0; r<5; r++)
result[r] = house[r];
else
RemoveMarlboro(m);
RemoveDunhill(n, side);
}
}
}
}
int main()
{
int index, i;
#ifdef WIN32
LARGE_INTEGER time0, time1, freq;
QueryPerformanceCounter(&time0);
#endif
Recurse(0);
#ifdef WIN32
QueryPerformanceCounter(&time1);
QueryPerformanceFrequency(&freq);
printf("\nComputation Time: %ld microsec\n\n",
(time1.QuadPart-time0.QuadPart)*1000000/freq.QuadPart);
#endif
if (result[0]==0) {
printf("No solution found !?!\n");
return 1;
}
for (i=0; i<5; i++)
if ((result[i]&animal)==0)
for (index=0; index<25; index++)
if (((result[i]&country)>>index)==1)
printf("Fish Owner is the %s !!!\n\n", Label[index]);
for (i=0; i<5; i++) {
printf("%d: ",i+1);
for (index=0; index<25; index++)
if (((result[i]>>index)&1)==1)
printf("%-12s",Label[index]);
printf("\n\n");
}
return 0;
}