Zebra Puzzle (again)
A.Second Edition
This is my fourth try for this famous puzzle. 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.The third try is
by "scheme" which is functional programming language.
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.
This is just an improved edition of brute-force search.
1. Using lots of enum.
2. Using STL "algorithm" "next_permutation" because I am lazy to write permutation.
3. Using function pointer array.
4. Improved search by reducing "nationality" from permutation.
E.Further improvement
/**********************************************************************
1. The Englishmean lives in the red house.
2. The Spanish owns a dog.
3. The Japanese man is a painter.
4. The Italian drinks tea.
5. The Norwegian lives in the first house on the left.
6. The green house is on the right of white one.
7. The photographer breeds snails.
8. The diplomat lives in the yellow house.
9. Milk is drunk in the middle house.
10. The owner of the green house drinks coffee.
11. The Norwegian's house is next to the blue one.
12. The violinist drinks orange juice.
13. The fox is in a house next to that of the diplomat.
***********************************************************************/
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int ItemNumber=5;
const int CategoryNumber=5;
char *occupationStr[ItemNumber] =
{
"Diplomat", "Photogra", "Painter", "Violinist", "Physician"
};
char* colorStr[ItemNumber]=
{
"Red ", "Yellow ", "White ", "Green ", "Blue "
};
char* petStr[ItemNumber]=
{
"Dog ", "Snail ", "Horse ", "Zebra ", "Fox "
};
char* drinkStr[ItemNumber]=
{
"Coffee ", "Juice ", "Tea ", "Milk ", "Water "
};
char *nationalStr[ItemNumber] =
{
"English", "Spanish ", "Japanese", "Norwegian", "Italian "
};
char* positionStr[ItemNumber]=
{
"First ", "Second ", "Third ", "Fourth ", "Fifth "
};
char* categoryName[CategoryNumber]=
{
"occupati", "drink ", "pet ", "color ", "national"
};
enum Category
{
OccupationCat, DrinkCat, PetCat, ColorCat,NationalCat
};
char** categoryStr[CategoryNumber]=
{
occupationStr, drinkStr, petStr, colorStr, nationalStr
};
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, Zebra, Fox
};
enum Drink
{
Coffee, Juice, Tea, Milk, Water
};
enum Position
{
First, Second, Third, Fourth, Fifth
};
//typedef vector<int*, IntPtrPred> PermVector;
typedef vector<int> PermVector;
/*
National national;
Occupation occupation;
Color color;
Pet pet;
Drink drink;
Position position;
*/
struct Person
{
int values[CategoryNumber];
};
Person persons[ItemNumber];
PermVector permVector[CategoryNumber];
void display();
bool check0();
bool check1();
bool check2();
bool check3();
bool check4();
bool check5();
bool check6();
bool check7();
bool check8();
bool check9();
bool check10();
bool check11();
bool check12();
bool check13();
const int CheckFuncNumber=9;
bool (*pfun[CheckFuncNumber])() =
{
check0, check11, check9, check6,check7,check8, check10, check12, check13
};
bool next();
void initialize();
int main()
{
bool noError;
initialize();
display();
int i=0, counter=0;
while (next())
{
noError=true;
for (i=0; i<CheckFuncNumber; i++)
{
if (!pfun[i]())
{
noError=false;
break;
}
}
if (noError)
{
printf("find it!!\n");
display();
}
//printf("permutation %d\n", i++);
counter++;
if (counter%20000==0)
{
//display();
printf("\n===============%d======================\n", counter);
}
}
printf("no solution\n");
return 0;
}
bool next()
{
int category=0, i;
bool result;
while (category<CategoryNumber-1)
{
result=next_permutation(permVector[category].begin(), permVector[category].end());
for (i=0; i<ItemNumber; i++)
{
persons[i].values[category]=permVector[category][i];
}
if (result)
{
return true;
}
else
{
category++;
}
}
return false;
}
void display()
{
int i, j;
for (i=0; i<CategoryNumber; i++)
{
printf("%12d", i+1);
}
printf("\n==============================================================\n");
for (i=0; i<CategoryNumber; i++)
{
printf("%9s:", categoryName[i]);
for (j=0; j<ItemNumber; j++)
{
printf("%12s", categoryStr[i][persons[j].values[i]]);
}
printf("\n");
}
printf("\n");
}
void initialize()
{
for (int i=0; i<CategoryNumber; i++)
{
for (int j=0; j<ItemNumber; j++)
{
//they are synchronized at beginning.
if (i==NationalCat)
{
continue;
}
permVector[i].push_back(j);
persons[j].values[i]=j;
}
}
}
bool check0()
{
bool filled[ItemNumber]={false, false, false, false, false};
filled[0]=true;
persons[0].values[NationalCat]=Norwegian;
for (int i=0; i<CategoryNumber-1; i++)
{
for (int j=0; j<ItemNumber; j++)
{
switch(i)
{
case ColorCat:
if (permVector[i][j]==Red)
{
if (filled[j])
{
return false;
}
persons[j].values[NationalCat]=English;
filled[j]=true;
}
break;
case PetCat:
if (permVector[i][j]==Dog)
{
if (filled[j])
{
return false;
}
persons[j].values[NationalCat]=Spanish;
filled[j]=true;
}
break;
case OccupationCat:
if (permVector[i][j]==Painter)
{
if (filled[j])
{
return false;
}
persons[j].values[NationalCat]=Japanese;
filled[j]=true;
}
break;
case DrinkCat:
if (permVector[i][j]==Tea)
{
if (filled[j])
{
return false;
}
persons[j].values[NationalCat]=Italian;
filled[j]=true;
}
break;
}
}
}
return true;
}
//The Englishman lives in the red house.
bool check1()
{
for (int i=0; i<ItemNumber; i++)
{
if (persons[i].values[NationalCat]==English)
{
return persons[i].values[ColorCat]==Red;
}
}
return false;
}
//The Spanish owns a dog.
bool check2()
{
for (int i=0; i<ItemNumber; i++)
{
if (persons[i].values[NationalCat]==Spanish)
{
return persons[i].values[PetCat]==Dog;
}
}
return false;
}
//The Japanese man is a painter.
bool check3()
{
for (int i=0; i<ItemNumber; i++)
{
if (persons[i].values[NationalCat]==Japanese)
{
return persons[i].values[OccupationCat]==Painter;
}
}
return false;
}
// The Italian drinks tea.
bool check4()
{
for (int i=0; i<ItemNumber; i++)
{
if (persons[i].values[NationalCat]==Italian)
{
return persons[i].values[DrinkCat]==Tea;
}
}
return false;
}
//The Norwegian lives in the first house on the left.
bool check5()
{
return persons[0].values[NationalCat]==Norwegian;
}
//The green house is on the right of white one.
bool check6()
{
int greenIndex=-1, whiteIndex=-1;
for (int i=0; i<ItemNumber; i++)
{
if (persons[i].values[ColorCat]==Green)
{
greenIndex=i;
}
if (persons[i].values[ColorCat]==White)
{
whiteIndex=i;
}
}
return greenIndex==whiteIndex+1;
}
//The photographer breeds snails.
bool check7()
{
for (int i=0; i<ItemNumber; i++)
{
if (persons[i].values[OccupationCat]==Photographer)
{
return persons[i].values[PetCat]==Snail;
}
}
return false;
}
//The diplomat lives in the yellow house.
bool check8()
{
for (int i=0; i<ItemNumber; i++)
{
if (persons[i].values[OccupationCat]==Diplomat)
{
return persons[i].values[ColorCat]==Yellow;
}
}
return false;
}
//Milk is drunk in the middle house.
bool check9()
{
return persons[2].values[DrinkCat]==Milk;
}
//The owner of the green house drinks coffee.
bool check10()
{
for (int i=0; i<ItemNumber; i++)
{
if (persons[i].values[ColorCat]==Green)
{
return persons[i].values[DrinkCat]==Coffee;
}
}
return false;
}
//The Norwegian's house is next to the blue one.
bool check11()
{
return persons[1].values[ColorCat]==Blue;
}
//The violinist drinks orange juice.
bool check12()
{
int violinistIndex=-1, orangeIndex=-1;
for (int i=0; i<ItemNumber; i++)
{
if (persons[i].values[OccupationCat]==Violinist)
{
return persons[i].values[DrinkCat]==Juice;
}
}
return false;
}
//The fox is in a house next to that of the diplomat.
bool check13()
{
int foxIndex=-1, diplomatIndex=-1;
for (int i=0; i<ItemNumber; i++)
{
if (persons[i].values[OccupationCat]==Diplomat)
{
diplomatIndex=i;
}
if (persons[i].values[PetCat]==Fox)
{
foxIndex=i;
}
}
return foxIndex==diplomatIndex+1||foxIndex==diplomatIndex-1;
}
And here is the result:
...
===============73560000======================
find it
1 2 3 4 5
==============================================================
occupati: Diplomat Physician Photogra Violinist Painter
drink : Water Tea Milk Juice Coffee
pet : Horse Fox Snail Dog Zebra
color : Yellow Blue Red White Green
national: Norwegian Italian English Spanish Japanese
...
===============73900000======================
find it!!
1 2 3 4 5
==============================================================
occupati: Diplomat Physician Photogra Violinist Painter
drink : Water Tea Milk Juice Coffee
pet : Zebra Fox Snail Dog Horse
color : Yellow Blue Red White Green
national: Norwegian Italian English Spanish Japanese