13,090,299 members (75,767 online)
alternative version

#### Stats

112K views
53 bookmarked
Posted 13 Dec 2003

# Machine Solution to Einstein's Riddle Revisited

, 29 Oct 2013
 Rate this:
This article shows a fast solution to Einstein's Riddle by using brutal search.

## Introduction

I found this interesting puzzle in Manfred Becker's article Einstein's riddle solved in C++. So I rushed to run his code for an easy answer. However several minutes had passed without a solution on the screen before I had to quit it, and went back to the source code for a clue. And I found a time table that states it takes 2 days 19 hours 24 minutes on a 700MHz Pentium III!

Although I understand that Becker's solution is just to demonstrate object oriented design, I think it would be better to have a fast solution for our impatient guys.

Here is a copy of the problem for easy reference and for the sake of completeness:

### Einstein's riddle

• There are 5 houses in five different colors in a row.
• In each house lives a person with a different nationality.
• These five owners drink a certain type of beverage, smoke a certain brand of cigar and keep a certain pet.
• No owners have the same pet, smoke the same brand of cigar or drink the same beverage.

### Einstein's hints

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 immediate 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 center house drinks milk.
9. The Norwegian lives in the first house.
10. The man who smokes Blends lives next to the one who keeps cats.
11. The man who keeps horses lives next to the man who smokes Dunhill.
12. The owner who smokes BlueMaster drinks beer.
13. The German smokes Prince.
14. The Norwegian lives next to the blue house.
15. The man who smokes Blends has a neighbor who drinks water.

## Class Design Considerations

Einstein spoke of houses and persons. It seems natural that we need a class of houses (`CHouse`) and a class of persons (`CPerson`) as Becker did it this way. However, if you think a little more about the relationship between these classes, you will notice that they have a one to one relationship. People often talk about homeowners. So why don't we just have one class for them? Sure, we can do it by viewing a person as a owner of a house and treating a person as a property in a house as well :)

```enum Problem_Constants
{
COUNT_HOUSES = 5,
COUNT_CATEGORIES = 5,
COUNT_HINTS = 15,
BITS_CatID = 3,
COUNT_EXTENDED_CatID = 1 << BITS_CatID  //  COUNT_EXTENDED_CatID = 8
};

// Property Category ID
enum CatID
{
COLOR,
NATIONALITY,
BAVERAGE,
CIGAR,
PET
};

// Property Identifications
enum PropID
{
BLUE       = (0 << BITS_CatID) | COLOR,
GREEN      = (1 << BITS_CatID) | COLOR,
RED        = (2 << BITS_CatID) | COLOR,
WHITE      = (3 << BITS_CatID) | COLOR,
YELLOW     = (4 << BITS_CatID) | COLOR,

BRIT       = (0 << BITS_CatID) | NATIONALITY,
DANE       = (1 << BITS_CatID) | NATIONALITY,
GERMAN     = (2 << BITS_CatID) | NATIONALITY,
NORWEGIAN  = (3 << BITS_CatID) | NATIONALITY,
SWEDE      = (4 << BITS_CatID) | NATIONALITY,

BEER       = (0 << BITS_CatID) | BAVERAGE,
COFFEE     = (1 << BITS_CatID) | BAVERAGE,
MILK       = (2 << BITS_CatID) | BAVERAGE,
TEA        = (3 << BITS_CatID) | BAVERAGE,
WATER      = (4 << BITS_CatID) | BAVERAGE,

BLENDS     = (0 << BITS_CatID) | CIGAR,
BLUEMASTER = (1 << BITS_CatID) | CIGAR,
DUNHILL    = (2 << BITS_CatID) | CIGAR,
PALLMALL   = (3 << BITS_CatID) | CIGAR,
PRINCE     = (4 << BITS_CatID) | CIGAR,

BIRD       = (0 << BITS_CatID) | PET,
CAT        = (1 << BITS_CatID) | PET,
DOG        = (2 << BITS_CatID) | PET,
FISH       = (3 << BITS_CatID) | PET,
HORSE      = (4 << BITS_CatID) | PET
};

enum HouseID
{
HOUSE0, HOUSE1, HOUSE2, HOUSE3, HOUSE4
};

class CHouse
{
private:
enum
{
// EMPTY is a flag to indicate a null property of any category.
// Its value must not be equal to any
// real property (any element of PropID).
EMPTY  = (0 << BITS_CatID) | PET + 1
};

PropID m_property[COUNT_CATEGORIES];

// constructor
public:
CHouse()
{
for (int i = 0; i < COUNT_CATEGORIES; i++)
m_property[i] = EMPTY;
}

// operations
public:
int IsEmpty(CatID cid)          { return m_property[cid] == EMPTY; }
int IsEmpty(PropID pid)         { return IsEmpty(GetCatID(pid)); }
int GetPropIndex(CatID cid)     { return GetIndex(m_property[cid]); }
void SetProperty(PropID pid)    { m_property[GetCatID(pid)] = pid; }
void ClearProperty(PropID pid)  { m_property[GetCatID(pid)] = EMPTY;}

private:
CatID GetCatID(PropID pid)
{ return (CatID) (pid & (COUNT_EXTENDED_CatID - 1)); }
int GetIndex(PropID pid)    { return pid >> BITS_CatID; }
};```

Simple as it is, isn't? `CHouse` has only one data member `m_property` that is an array indexed by category (`CatID`) and used to hold the 5 properties. A `CHouse` object is self-contained, which knows nothing about its neighbors. We all know that a dog is a pet and beer is beverage. To please its users, `CHouse` understands this type-of relation by means of its member function `GetCatID(PropID pid)` and the composite definition of `PropID`.

Let's move to the other part of the problem, the hints, which describe the associations of properties and owners. We need a class to represent the hints. I bet, you will notice that the hints vary considerably at a glance. It is obvious that we will not end up with a simple uniform class like `CHouse`. Well, we will attack these variations by abstraction and derivation.

So what are in common, in all the hints? They all have to do with at least one property and one possible owner of the property. Therefore we name a base class `CHint` for the hints, and make it have two data members `m_pid0` and `m_pNewOwner`, to represent the property and the possible owner. A `CHint` object also needs access to any `CHouse` object because the property (`m_pid0`) in it can be owned by any house owner that meets the hint. We put an array of 5 `CHouse` objects in `CHint` as a static data member. Before we continue with `CHint` method members, take a look at its blue print:

```class CHint
{
protected:
const PropID m_pid0;  // a property in the hint
CHouse* m_pNewOwner0; // ptr to a would-be owner
// of the property to meet the hint
CHouse* m_pNext;      // the next house to be checked and filled

static CHouse house[COUNT_HOUSES]; // array of the houses
private:
// array of pointers to house owners indexed by PropID
static CHouse* propowner[COUNT_CATEGORIES*COUNT_EXTENDED_CatID];
static int count_solutions; // count of solutions found

// constructor
protected:
CHint(PropID pid0) : m_pid0(pid0) {}

public:
// starting from house specified by m_pNext, seek and assign the
// first eligible houseowner(s) with properties.
//
// return value:
//       0 : failed
// nonzero : successful
//
virtual int AssignPropToNextEligibles() = 0;

// undo AssignPropToNextEligibles
virtual void RemovePropFromPrevEligibles() = 0;
// reset the seek to start position
virtual void ResetSeekPosition() = 0;
// print out a solution
static  void PrintOut();

// helpers
protected:
void RemoveProperty();   // remove property from new owner
int AssignPropertySetNextPos(CHouse* p0, CHouse* pNext);

// property register operations
protected:
static CHouse* GetPropertyOwner(PropID pid)
{ return propowner[pid]; }
static void RegisterOwnership(PropID pid, CHouse* pOwner)
{
propowner[pid] = pOwner;
}

// counter
public:
static int GetSolutionCount()  { return count_solutions; };
private:
static void IncSolutionCount() { count_solutions++; };

// helper
// verify a solution and check for errors
static CHouse* VerifyCurrentSolution();
};```

There are three pure virtual functions in it, that make `CHint` an abstract class. Just as a `CHouse` object knows nothing about its neighbors, a `CHint` object should know nothing about other `CHint` objects, in order to keep things simple. But a `CHint` object should have a method of finding all possible houses that meet the requirements of the hint. It is not necessary that the method returns a list of all possible house owners at a time. Instead, we want it find one house owner (`m_pNewOwner`) for its property (`m_pid0`) at a time, in an order. This can deliver better overall efficiency due to less memory traffic. These three virtual functions come in to fill the bill.

• `AssignPropToNextEligibles()` finds the next matching house owner and assigns the property to him. Data member `m_pNext` is used to keep `AssignPropToNextEligibles()` knowing where to resume its work.
• `RemovePropFromPrevEligibles()` is used to undo the property assignments made by `AssignPropToNextEligibles()` so that we can call `AssignPropToNextEligibles()` again to find yet another owner.
• The last virtual function `ResetSeekPosition()` is an interface to reset the seek to its start position.

Those pure virtual functions can be viewed as place holders and specifications. Any class derived from `CHint` still has to implement these three functions.

The static data member `propowner` and its functions `GetPropertyOwner` and `RegisterOwnership` are included in `CHint` for easy access to the owner of any property. The data member and these 2 functions are an implementation of a property ledger so that we can avoid doing a linear search every time we need to know who owns a specific property.

The static functions `VerifyCurrentSolution` and `PrintOut` that verifies and prints out a solution respectively, are quite foreign to the `CHint` class from a concept point of view. I include them here simply because they also need access to the 5 houses. If I were a fundamentalist in OOP design, I would probably kick them out and give them a read only service instead.

Now we can derive classes from `CHint`. Hint 8 and 9 deal with only one property that the base class already provides. But each of them has a known house number. So we define the class this way:

```// class for any hint of Known house number
//
class CKnownHouseHint : public CHint
{
private:
CHouse* const m_pKnownHouse;

public:
CKnownHouseHint(HouseID i, PropID pid) :
CHint(pid), m_pKnownHouse(&house[i]) {}

private:
virtual int AssignPropToNextEligibles();
virtual void ResetSeekPosition()           { m_pNext = m_pKnownHouse; }
virtual void RemovePropFromPrevEligibles() { RemoveProperty(); }
};```

The rest of the hints involve two properties that can be owned by different owners. We reflect this difference by deriving a `CMultiPropertiesHint` class:

```// class for any hint that involves Multiple properties
//
class CMultiPropertiesHint : public CHint
{
protected:
// a property in the hint
const PropID m_pid1;
// ptr to a would-be owner of the property to meet the hint
CHouse* m_pNewOwner1;

// implementations
protected:
virtual void RemovePropFromPrevEligibles();

// constructor
protected:
CMultiPropertiesHint(PropID pid0,
PropID pid1) : CHint(pid0), m_pid1(pid1) { }

// helpers
protected:
void ResetSeekPositionToFirstHouse() { m_pNext = &house[HOUSE0]; }
int AssignPropertiesSetNextPos(CHouse* p0, CHouse* p1, CHouse* pNext);
};```

`CMultiPropertiesHint` is still an abstract base class for further derivations, though it provides some useful services.

Some hints only deal with a single house owner, hint 1 for example. `CSingleHouseHint` is derived from `CMultiPropertiesHint` for those hints:

```// class for the any hint that only involves a Single houseowner
//
class CSingleHouseHint : public CMultiPropertiesHint
{
// constructor
public:
CSingleHouseHint(PropID pid0,
PropID pid1) : CMultiPropertiesHint(pid0, pid1) { }

// implementations
private:
virtual int AssignPropToNextEligibles();
virtual void ResetSeekPosition() { ResetSeekPositionToFirstHouse(); }
};```

Some hints deal with two house owners, hint 15 for instance. `CNeighborsHint` is derived from `CMultiPropertiesHint` for those hints:

```// class for any hint that involves
// 2 Neighbors without a directional restriction
//
class CNeighborsHint : public CMultiPropertiesHint
{
private:
int m_NextReverse; // are the properties to be filled in reverse order?

// constructor
public:
CNeighborsHint(PropID pid0,
PropID pid1) : CMultiPropertiesHint(pid0, pid1) { }

// implementations
private:
virtual int AssignPropToNextEligibles();
virtual void ResetSeekPosition()
{
ResetSeekPositionToFirstHouse();
m_NextReverse = 0;
}
};```

Hint 4 also talks about two houses. But the houses should be in a sequential order. We have only one instance of this kind, yet we have to derive a class for it to complete `CHint` class family:

```// class for any hint that involves
// 2 Neighbors Ordered by direction
//
class COrderedNeighborsHint : public CMultiPropertiesHint
{
// constructor
public:
COrderedNeighborsHint(PropID pid0,
PropID pid1) : CMultiPropertiesHint(pid0, pid1) {}

// implementations
private:
virtual int AssignPropToNextEligibles();
virtual void ResetSeekPosition() { ResetSeekPositionToFirstHouse(); }
};```

I skip the implementations of these classes here. You can find them in the source file.

Since the riddle now can be well represented by a set of `CHint` objects and a set of `CHouse` objects, let's start to crack the puzzle by defining a class `CSolver`:

```// class for finding the solutions
//
class CSolver
{
private:
static CHint* hint[COUNT_HINTS]; // array of pointers to CHint objects
static int count_nodes; // count of nodes searched

// operations
public:
static void DoTheWork(); // search driver

// helpers
private:
static void Search(CHint** ppCHint); // search engine
static void PrintEinsteinRiddleDescription();
static void IncNodeCount() { count_nodes++; };
static int GetNodeCount() { return count_nodes; };
};```

`CSolver` encapsulates those 15 hints in a static array of pointers to `CHint` objects. In the implementation file, we simply create these objects and initialize the array in a single step:

```// Array of pointers to CHint objects, i.e. a list of hints.
//
CHint* CSolver::hint[COUNT_HINTS] =
{
new CSingleHouseHint(BRIT, RED),                // Hint 1
new CSingleHouseHint(SWEDE, DOG),               // Hint 2
new CSingleHouseHint(DANE, TEA),                // Hint 3
new COrderedNeighborsHint(GREEN, WHITE),        // Hint 4
new CSingleHouseHint(GREEN, COFFEE),            // Hint 5
new CSingleHouseHint(PALLMALL, BIRD),           // Hint 6
new CSingleHouseHint(YELLOW, DUNHILL),          // Hint 7
new CKnownHouseHint(HOUSE2, MILK),              // Hint 8
new CKnownHouseHint(HOUSE0, NORWEGIAN),         // Hint 9
new CNeighborsHint(BLENDS, CAT),                // Hint 10
new CNeighborsHint(HORSE, DUNHILL),             // Hint 11
new CSingleHouseHint(BLUEMASTER, BEER),         // Hint 12
new CSingleHouseHint(GERMAN, PRINCE),           // Hint 13
new CNeighborsHint(NORWEGIAN, BLUE),            // Hint 14
new CNeighborsHint(BLENDS, WATER)               // Hint 15
};```

Now `CSolver` can work with pointers to `CHint` objects and forget about the differences among those objects. `CSolver` has a single public interface function `DoTheWork()`, which will be called by the `main()` function. `DoTheWork()` will delegate the real work to the `Search` function.

## Brutal Search

Here is a simplified version of the exhaustive `Search` function:

```void CSolver::Search(int index_of_hint)
{

hint[index_of_hint]->ResetSeekPosition(); // reset to start position.

// seek each set of eligibles & assign
// properties to them if needed.
while (hint[index_of_hint]->AssignPropToNextEligibles())
{

if (index_of_hint != 15 - 1) // if the hint is not the last one.
Search(index_of_hint + 1); // search with next hint.
else  // all hints have been met.
CHint::PrintOut(); // a solution has been found.
// undo the assign operations.
hint[index_of_hint]->RemovePropFromPrevEligibles();
}
}```

As you see, `Search` is a recursive function. It tries to find a match for the current hint. If it has found one, it then calls itself with the next hint, provided that the current hint is not the last one where it prints a solution, and continues the search. If it has finished finding all possible matches or it has failed finding any match for the current hint, it returns the control to the previous hint.

`DoTheWork()` will make the first call with `index_of_hint` = 0.

## Performance

It takes 0.016 seconds on a 1.6GHz P4 and 0.056 seconds on a 166Mhz Pentium MMX, when the standard `clock()` were used to do the timing in a previous version.

The current version uses high resolution performance counters to get more accurate results. However, different runtime sessions still showed quiet big variations of time. A little profiling work indicated, the program spends more than 80% of its time in printing out a solution! I had to optimize the drawing code a little bit in order to reduce the variations. After these tweaks, it takes only 0.0014 seconds on a 2.60GHz P4.

It is much faster than I had expected anyways. Now I think an old 8086 can easily crack the riddle too. Unfortunately, I could not find one.

## Update

It would be interesting if we could gain some insight into the puzzle by playing with the program. Here are some:

Hint 15 is proved to be redundant because exactly the same solution is produced after it is commented out in the hint list. We can also leave out Hint 5 to make it more challenging for those who prefer pencils and papers.

Some tweaks in Version 1.04 (12/23/2003) makes it easier to add or delete hints in the list.

Version 1.05 (10/25/2013) adds UNICODE support;  C# port source is also released along with updated C++ code.

## Share

 United States
No Biography provided

## You may also be interested in...

 Pro Pro

 First Prev Next
 My rating of 5. Bill_Hallahan31-Oct-13 17:34 Bill_Hallahan 31-Oct-13 17:34
 Re: My rating of 5. Dezhi Zhao1-Nov-13 5:52 Dezhi Zhao 1-Nov-13 5:52
 Hint 5 (Solution to Einstein's Riddle Revisited) duarte_borba23-Nov-04 10:03 duarte_borba 23-Nov-04 10:03
 Re: Hint 5 (Solution to Einstein's Riddle Revisited) Dezhi Zhao23-Nov-04 10:13 Dezhi Zhao 23-Nov-04 10:13
 Re: Hint 5 (Solution to Einstein's Riddle Revisited) duarte borba25-Nov-04 1:12 duarte borba 25-Nov-04 1:12
 Increase further Anthony_Yio20-Apr-04 21:33 Anthony_Yio 20-Apr-04 21:33
 Re: Increase further Dezhi Zhao21-Apr-04 10:44 Dezhi Zhao 21-Apr-04 10:44
 more proof that amd is better :P (Steven Hicks)n+124-Jan-04 11:39 (Steven Hicks)n+1 24-Jan-04 11:39
 more proof that amd is better :P (Steven Hicks)n+124-Jan-04 11:39 (Steven Hicks)n+1 24-Jan-04 11:39
 What about Pencil Power? Miguel Lopes22-Dec-03 8:29 Miguel Lopes 22-Dec-03 8:29
 Re: What about Pencil Power? Dezhi Zhao22-Dec-03 8:45 Dezhi Zhao 22-Dec-03 8:45
 Re: What about Pencil Power? mystro_AKA_kokie24-Dec-03 6:07 mystro_AKA_kokie 24-Dec-03 6:07
 Re: What about Pencil Power? oneway18-Apr-04 7:01 oneway 18-Apr-04 7:01
 Re: What about Pencil Power? Miguel Lopes18-Apr-04 8:21 Miguel Lopes 18-Apr-04 8:21
 Re: What about Pencil Power? Anonymous2-May-04 13:11 Anonymous 2-May-04 13:11
 Re: What about Pencil Power? Miguel Lopes3-May-04 0:06 Miguel Lopes 3-May-04 0:06
 Excellent, but... des griffiths21-Dec-03 5:07 des griffiths 21-Dec-03 5:07
 Re: Excellent, but... Dezhi Zhao21-Dec-03 6:18 Dezhi Zhao 21-Dec-03 6:18
 Nice speed Lars [Large] Werner20-Dec-03 14:05 Lars [Large] Werner 20-Dec-03 14:05
 I like! John R. Shaw19-Dec-03 13:36 John R. Shaw 19-Dec-03 13:36
 Re: I like! Dezhi Zhao19-Dec-03 15:31 Dezhi Zhao 19-Dec-03 15:31
 Re: I like! Dezhi Zhao20-Dec-03 10:11 Dezhi Zhao 20-Dec-03 10:11
 Re: I like! John R. Shaw20-Dec-03 14:10 John R. Shaw 20-Dec-03 14:10
 Re: I like! zichun20-Dec-03 16:49 zichun 20-Dec-03 16:49
 Amazing! ManiB17-Dec-03 20:56 ManiB 17-Dec-03 20:56
 Re: Amazing! Dezhi Zhao18-Dec-03 5:16 Dezhi Zhao 18-Dec-03 5:16
 Last Visit: 31-Dec-99 18:00     Last Update: 19-Aug-17 11:49 Refresh 1