//  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;
}