Posts: 1,439
Threads: 15
Joined: Apr 2003
I tried solving that problem by hand once too, and it drove me nuts; maybe I'll have time to code up a solver...
Posts: 484
Threads: 14
Joined: Apr 2005
Sorry i've been too busy to post, or work on my solver. You code looks interesting though aga, i will take the time to look at it properly when i can.
Also i've lost the short one i downloaded, but heres another one i dug up. A lot larger but less obfuscated than the other one i lost.
Code: // 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;
}
EVEN MEN OF STEEL RUST.
Posts: 3,368
Threads: 195
Joined: Jan 2003
Ah, a recursive depth-first search using the rules to backtrack. Maybe I could try it in QB.
But, what is the computation time in C?
Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."
Visit www.neobasic.net to see rubbish in all its finest.
Posts: 484
Threads: 14
Joined: Apr 2005
~ 45 microseconds.
EVEN MEN OF STEEL RUST.
|