Population

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.

    B.The problem

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.

C.The idea of program

    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.

    D.The major functions

    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

กก