Zebra --- An application of DFS
A.Second Edition
This is third edition of my DFS base class. Like BFS, I standardized all virtual method and correct a couple of
small mistakes. And this is considered to be an application of my DFS. What's more, it is at least my second
approach for this famous puzzle given by Eistein. The first solution is long time ago and it is a fake which
I now regard as a shame and lesson.
Zebra Puzzle:
Five men with different nationalities and with different jobs live in consecutive houses on a street. These houses are painted different colors. The men have different pets and have different favorite drinks. Determine who owns a zebra and whose favorite drinks is mineral water (which is one of the favorite drinks) given these clues: The Englishman lives in the red house. The Spanish owns a dog. The Japanese man is a painter. The Italian drinks tea. The Norwegian lives in the first house on the left. The green house is on the right of white one. The photographer breeds snails. The diplomat lives in the yellow house. Milk is drunk in the middle house. The owner of the green house drinks coffee. The Norwegian's house is next to the blue one. The violinist drinks orange juice. The fox is in a house next to that of the diplomat.
No matter how complicated a problem may become, we can divide and conquer it by counting! And depth-first-search
is one of the simplest way to do it.
1. I defined a series of enumerates for better readability.
2. The question is considered to a 25 level of searching problem. Each level is an option, say color white, red...
It is reasonable since that the five category property is like five functions with same range---The Nationality.
(Understand? No matter what property is says, dog as pet, red for house, diplomat as occupation, it all mean a
same person or represented by the nationality. So only after 25 different properties are all assigned to five
nationalities, the problem is then solved.
3. Most constrains can be enforced at stage of "validateOption" except those involved with position of houses
which I place them at last stage--"evaluate". Because positions of houses involves more than two categories,
like "the fox is in a house next to that of the diplomat" --- it uses pet, occupation and position three
categories.
1. bool Zebra::uniqueChecking(int sonData)
This is written a little bit tricky! And it is no good. To keep it unique in each category, you only need to
check from the first element till this element if there is repeat.
2. bool Zebra::seriesChecking()
This includes a series of checking functions. But at last I put many of these checking functions into constrains
at "validateOption" so that the size of total searching tree is smaller. For the checking of positions like "the
Norwegian's house is next to the blue one", we need to search five positions and see which we encounter first,
then the next must be the other one. Please note here I deliberately ignore the normal induction role in this
particular condition:
a) The Norwegian lives in the first house on the left.
b)The Norwegian's house is next to the blue one.
conclusion: Norwegian is living in second house on the left.
However, do we need to do this induction or can machine figure out this automatically? No. We don't have to, and
we should not do it. Because it is not necessary for us to use this short cut.
So I keep it like all other conditions and put it at last stage checking---evaluate.
E.Further improvement
1. This program exposes some problem of my DFS base class and I have to make some changes in future. Like the
solutionCounter, if collectResult method is overrided then the counter doesn't count correctly and no result
will be given. I have to put it some other places. This is typically an example that base class doesn't expect
what derived class is going to do.
กก
กก
กก
#include <iostream>
#include <iomanip>
using namespace std;
const int MaxSonCount=8;
const int MaxLevel =100;
const int MaxOptions = 10;
const NationNum =5;
const OccupationNum = 5;
const ColorNum =5;
const PetNum = 5;
const DrinkNum =5;
const FunNum =5;
char *strCol[NationNum*5] = {"Diplomat", "Photographer", "Painter", "Violinist",
"Physician", "Red", "Yellow", "White", "Green", "Blue",
"Dog", "Snail", "Horse", "Zebra", "Fox", "Coffee", "Juice", "Tea",
"Milk", "Water", "First", "Second","Third","Fourth","Fifth"};
char *strRow[NationNum] = {"English", "Spanish", "Japanese", "Norwegian", "Italian"};
enum National
{English, Spanish, Japanese, Norwegian, Italian};
enum Occupation
{Diplomat, Photographer, Painter, Violinist, Physician};
enum Color
{Red, Yellow, White, Green, Blue};
enum Pet
{Dog, Snail, Horse, ZZebra, Fox};
enum Drink
{Coffee, Juice, Tea, Milk, Water};
enum Position
{First, Second, Third, Fourth, Fifth};
enum LevelName
{OccupationLevel, ColorLevel, PetLevel, DrinkLevel, PositionLevel};
int choiceArray[5] = {English, Spanish, Japanese, Norwegian, Italian};
class DFS
{
private:
static DFS* root;
static bool findAll;
static int level;
static int optionArray[MaxOptions];
static int optionCount;
static int maxLevel;
DFS* parent;
DFS* sonArray[MaxSonCount];
int data;
int sonCount;
int sonIndex;
void addSon(int sonData);
DFS* findBrother();
DFS* findUncle();
bool hasBrother();
DFS* nextBrother();
void initialize(DFS* now);
bool touchDown();
DFS* generate();
void setMaxLevel(int max) { maxLevel = max;}
bool doGenerate();
protected:
int depth;
static int solutionCount;
static char** nameString;
static int trackRecord[MaxLevel];
void trackBack();
virtual DFS* createSon();
virtual bool validateOption(int sonData);
virtual void onLeave();
virtual bool evaluate();
virtual void collectResult();
public:
int getSolutionCount(){ return solutionCount;}
void setOptions(int* array, int size);
void setNameStr(char** str) {nameString = str;}
void beginCount(int max, bool findall=false);
};
class Zebra : public DFS
{
private:
bool uniqueChecking(int sonData);
bool seriesChecking();
bool check0();
bool check1();
bool check2();
bool check3();
bool check4();
bool check5();
bool check6();
bool check7();
bool check8();
bool check9();
int getData(int whichLevel);
bool samePerson(int firstPos, int secondPos);
protected:
virtual DFS* createSon();
virtual bool validateOption(int sonData);
virtual bool evaluate();
virtual void collectResult();
};
bool DFS::findAll = false;
int DFS::maxLevel = 0;
int DFS::optionCount = 0;
int DFS::optionArray[MaxOptions] = {0};
int DFS::level = 0;
DFS* DFS::root = NULL;
char** DFS::nameString=NULL;
int DFS::solutionCount = 0;
int DFS::trackRecord[MaxLevel]={0};
int main()
{
Zebra R;
R.setOptions(choiceArray, 5);
R.beginCount(25, true);
cout<<"Total number is "<<R.getSolutionCount()<<endl;
return 0;
}
bool Zebra::samePerson(int firstPos, int secondPos)
{
return trackRecord[firstPos]==trackRecord[secondPos];
}
void Zebra::collectResult()
{
cout<<endl;
for (int l=0; l<5; l++)
{
for (int i=0; i<5; i++)
{
cout<<setw(15)<<strCol[l*5+i];
}
cout<<endl;
for (i=0; i<5; i++)
{
cout<<setw(15)<<strRow[trackRecord[l*5+i]];
}
cout<<endl;
}
cout<<"It is number:"<<solutionCount++;
cout<<endl;
}
bool Zebra::check0()
{
int first, second;
first = trackRecord[ColorLevel*5+Green];
second = trackRecord[ColorLevel*5+ White];
for (int i=PositionLevel*5+First; i<=PositionLevel*5+Fifth; i++)
{
if (trackRecord[i]==first)
{
return false;
}
else
{
if (trackRecord[i]==second)
{
return true; //white must be encountered first
}
}
}
return false;
}
bool Zebra::check1()
{
int man = trackRecord[OccupationLevel*5+Photographer];
return trackRecord[PetLevel*5+Snail]==man;
}
bool Zebra::check2()
{
int man= trackRecord[OccupationLevel*5+Diplomat];
return trackRecord[ColorLevel*5+Yellow]==man;
}
bool Zebra::check3()
{
int man=trackRecord[DrinkLevel*5+Milk];
return trackRecord[PositionLevel*5+Third]==man;
}
bool Zebra::check4()
{
int man = trackRecord[ColorLevel*5+Green];
return trackRecord[DrinkLevel*5+Coffee]==man;
}
bool Zebra::check5()
{
int man= trackRecord[ColorLevel*5+Blue];
for (int i=First; i<=Fifth; i++)
{
if (trackRecord[PositionLevel*5+i]==man)
{
return trackRecord[PositionLevel*5+i+1]==Norwegian;
}
if (trackRecord[PositionLevel*5+i]==Norwegian)
{
return trackRecord[PositionLevel*5+i+1]==man;
}
}
return false;
}
bool Zebra::check6()
{
int man=trackRecord[OccupationLevel*5+Violinist];
return trackRecord[DrinkLevel*5+Juice]==man;
}
bool Zebra::check7()
{
int first= trackRecord[PetLevel*5+Fox];
int second = trackRecord[OccupationLevel*5+Physician];
for (int i=First; i<=Fifth; i++)
{
if (trackRecord[PositionLevel*5+i]==first)
{
return trackRecord[PositionLevel*5+i+1]==second;
}
if (trackRecord[PositionLevel*5+i]==second)
{
return trackRecord[PositionLevel*5+i+1]==first;
}
}
return false;
}
bool Zebra::check8()
{
int first = trackRecord[PetLevel*5+Horse];
int second = trackRecord[OccupationLevel*5+Diplomat];
for (int i=First; i<=Fifth; i++)
{
if (trackRecord[PositionLevel*5+i]==first)
{
return trackRecord[PositionLevel*5+i+1]==second;
}
if (trackRecord[PositionLevel*5+i]==second)
{
return trackRecord[PositionLevel*5+i+1]==first;
}
}
return false;
}
bool Zebra::check9()
{
int first= trackRecord[ColorLevel*5+Green];
int second=trackRecord[ColorLevel*5+White];
for (int i= First; i<=Fifth; i++)
{
if (trackRecord[PositionLevel*5+i]==first)
{
return false;
}
if (trackRecord[PositionLevel*5+i]==second)
{
return trackRecord[PositionLevel*5+i+1]==first;
}
}
return false;
}
bool Zebra::seriesChecking()
{
bool result = true;
//this is a lazy style!!!won't be allowed for other cases
// result = result&&check0()&&check1()&&check2();
// result = result&&check3()&&check4()&&check5()&&check6()&&check7();
result = result&&check5()&&check7()&&check8()&&check9();
return result;
}
bool Zebra::evaluate()
{
trackBack();
return seriesChecking();
}
bool Zebra::uniqueChecking(int sonData)
{
bool choice[5]={false};
int number = depth%5;
for (int i=depth-number; i<depth; i++)
{
choice[trackRecord[i]] = true;
}
return choice[sonData]==false;
}
DFS* Zebra::createSon()
{
DFS* ptr = new Zebra;
return ptr;
}
int Zebra::getData(int whichLevel)
{
trackBack();
return trackRecord[whichLevel];
}
bool Zebra::validateOption(int sonData)
{
bool result=true;
switch (depth)//parent depth
{
case ColorLevel*5+Red:
result = sonData == English;
break;
case PetLevel*5 + Dog:
result = sonData==Spanish;
break;
case OccupationLevel*5+Painter:
result= sonData==Japanese;
break;
case DrinkLevel*5+Tea:
result = sonData==Italian;
break;
case PetLevel*5+Snail:
result = sonData== getData(OccupationLevel*5+Photographer);
break;
case ColorLevel*5+Yellow:
result = sonData == getData(OccupationLevel*5+Diplomat);
break;
case PositionLevel*5+Third:
result = sonData==getData(DrinkLevel*5+Milk);
break;
case DrinkLevel*5+Coffee:
result = sonData==getData(ColorLevel*5+Green);
break;
case ColorLevel*5+Blue:
result = sonData!=Norwegian;
break;
case DrinkLevel*5+Juice:
result = sonData==getData(OccupationLevel*5+Violinist);
break;
case PositionLevel*5+First:
result = sonData==Norwegian;
break;
/*this is by induction, so, generally it should be in evaluate. do it!
case PositionLevel*5+Second:
result= sonData==getData(ColorLevel*5+Blue);
break;
*/
}
if (!result)
{
return result;
}
trackBack();
return uniqueChecking(sonData);
}
//I don't know what extra work to be for the time being
bool DFS::evaluate()
{
return depth == 9;
}
bool DFS::touchDown()
{
return depth==maxLevel;
}
void DFS::onLeave()
{
DFS* ptr =this;
delete ptr;
}
void DFS::trackBack()
{
DFS* ptr = this;
while (ptr->parent!=NULL)
{
trackRecord[ptr->depth-1] = ptr->data;
ptr = ptr->parent;
}
}
//a stack
void DFS::collectResult()
{
trackBack();
cout<<"The route is:";
for (int i=0; i<depth; i++)
{
cout<<nameString[trackRecord[i]]<<", ";
}
cout<<"It is number:"<<solutionCount++;
cout<<endl;
}
void DFS::setOptions(int *array, int size)
{
optionCount = size;
for (int i=0; i<size; i++)
{
optionArray[i] = *(array+i);
}
}
bool DFS::doGenerate()
{
bool result = false;
if (touchDown())
{
return false;
}
for (int i=0; i< optionCount; i++)
{
if (validateOption(optionArray[i]))
{
addSon(optionArray[i]);
result = true;
}
}
if (result)
{
level++;
}
return result;
}
bool DFS::validateOption(int sonData)
{
return true;
}
DFS* DFS::findBrother()
{
DFS* ptr= this;
DFS* dummy=ptr;
while (!(ptr->hasBrother()))
{
dummy = ptr; //keep the clue
ptr = ptr->parent;
level--; //???
if (dummy!=root)
{
dummy->onLeave(); //clear
}
if (ptr==NULL)
{
return NULL;
}
}
dummy = ptr; //keep clue
ptr = ptr->nextBrother();
dummy->onLeave(); //clear
return ptr;
}
void DFS::beginCount(int max, bool findall)
{
DFS* ptr = this;
setMaxLevel(max);
findAll = findall; //setup if want all result
initialize(this);
while (true)
{
ptr = ptr->generate();
if (ptr==NULL)
{
if (solutionCount==0)
{
cout<<"No solution!";
}
break;
}
if (ptr->evaluate())
{
ptr->collectResult();
if (!findAll)
{
break;
}
}
ptr = ptr->findBrother();
if (ptr==NULL)
{
if (solutionCount==0)
{
cout<<"No solution!";
}
break;
}
}
}
DFS* DFS::generate()
{
DFS* ptr= this;
while (!ptr->touchDown())
//while (!ptr->evaluate())
{
if (!ptr->doGenerate())
{
ptr=ptr->findBrother();
if (ptr==NULL)
{
break;
}
}
else
{
ptr = ptr->sonArray[0];
}
}
return ptr;
}
DFS* DFS::createSon()
{
DFS* ptr = new DFS;
return ptr;
}
void DFS::addSon(int sonData)
{
if (sonCount+1<MaxSonCount)
{
DFS* ptr = createSon();
ptr->data = sonData;
ptr->sonCount = 0;
ptr->parent = this;
ptr->depth = depth+1;
sonArray[sonCount] = ptr;
ptr->sonIndex = sonCount;
sonCount++;
}
else
{
cout<<"Exceed max of sons!";
}
}
void DFS::initialize(DFS* now)
{
root = now;
root->depth = 0;
root->sonCount = 0;
root->sonIndex = -1;
root->parent = NULL;
root->data = 0;
level = 0;
}
bool DFS::hasBrother()
{
if (parent!=NULL)
{
if (parent->sonCount > sonIndex+1)//has little brother
{
return true;
}
}
return false;
}
DFS* DFS::nextBrother()
{
if (parent!=NULL)
{
if (parent->sonCount > sonIndex+1)//has little brother
{
return parent->sonArray[sonIndex+1]; //next little brother
}
}
return NULL;
}
And here is the result:
Diplomat Photographer Painter Violinist Physician
Norwegian English Japanese Spanish Italian
Red Yellow White Green Blue
English Norwegian Spanish Japanese Italian
Dog Snail Horse Zebra Fox
Spanish English Italian Japanese Norwegian
Coffee Juice Tea Milk Water
Japanese Spanish Italian English Norwegian
First Second Third Fourth Fifth
Norwegian Italian English Spanish Japanese
It is number:0
Total number is 1
Press any key to continue
กก