Einstein's question, the following is the problem prompt and C solution (old writer) for everyone to learn ing, I believe that many people have heard: 1 House of five colors 2 Every house owner Different nationalities 3 These five people only drink a drink, only a brand of cigarettes, only to raise a pet 4 No one has the same pet, take the same brand's cigarette, drink the same beverage Tip: 1, British live in the red house 2, Swedes raise a dog 3, Danish drink tea 4, green house on the left side of the white house 5, green house owner drink coffee 6, people picking the Pall Mall smoke to raise a bird 7 The owner of the Huang House smokes Dunhill to smoke 8, people living in the middle of the house drink milk 9, Norwegia people live in the first house 10, the people who smoke smoke live next to the fish people 11, Tao people live in Dunhill Next to the smoke 12, people smoking the Blue Master smoke drink beer 13, Germans smoke Prince Smoke 14, Norwegians live next to the blue house 15, the neighbors of the smoke, the mineral water problem is: Who is fish? #include "einstein.h" #include
#define count_search_searches 1 # Define Fill_in 1
Chouse chint :: house [count_houses]; chouse * chint :: propowner [count_categories * count_exted_catid]; int Csolver :: count_nodes = 0; int chint :: count_solutions = 0;
// array of pointers to chint Objects, IE a list of hints./// i Just Keep the hint list in Einstein's Order.//HOULD you not want to be fooled by his // tricky Order, You Could Move THE SMIPLEST // hints, hint 8 and hint 9 for example, to the program. // chint * csolver :: hint [] = {// 1. The Brit Lives in The Red House New CsingleHouseHint (BRIT, RED),
// 2. The Swede Keeps Dogs as Pets New CsingleHousehint (Swede, Dog),
// 3. The Dane Drinks Tea New CsingleHousehint (Dane, TEA),
// 4. The Green House Is on The Immediate Left of The White House New CorderedNeighborshint (Green, White), // 5. The Green House's Owner Drinks Coffee New CsingleHOrth (Green, Coffee),
// 6. The Person WHO Smoke Mall Mall Rears Birds New CsingleHousehint (Pallmall, Bird),
// 7. The Owner of the Yellow House Smokes Dunhill New CsingleHousehint (YELLOW, DUNHILL),
// 8. The Man Living in The Center House Drinks Milk New CknownHousehint (House2, Milk),
// 9. The Norwegian Lives in The First House New Cknownhousehint (House0, Norwegian), // 10. The Man Who Smokeles Blends Lives New CNeighborshint (Blends, Cat),
// 11. The Man Who Keeps Horses Lives Next To The Man Who Smokehill New CNeighboShint (Horse, Dunhill),
// 12. The Owner Who SmokeS Bluemaster Drinks Beer New CsingleHousehint (Bluemaster, Beer),
// 13. The German Smokes Prince New CsingleHousehint (German, Prince),
// 14. The Norwegian Lives Next To The Blue House New CNeighborshint (Norwegian, Blue),
// 15. The Man Who Smokeles Blends Has A Neighbor Who Drinks Water New CNEighborshint (Blends, Water)}
INT __CDECL Main (int Argc, char * argv []) {csolver :: dothework (); printf ("press any key to end the program ...); getCh (); return 0;}
Void Csol :: Dothework () {__INT64 Start, Finish, FREQ;
PrintEinsteinRiddleDescription (); QueryPerformanceFrequency ((LARGE_INTEGER *) & freq); QueryPerformanceCounter ((LARGE_INTEGER *) & start); for (int i = 0; i void CSolver :: PrintEinsteinRiddleDescription () {// this is the problem decription static const char sRiddle [] [75] = { "Einstein wrote a riddle last century. He said that 98% of the world could", "not solve it. "," "", "Einstein's Riddle", "There Area 5 Houses in Five Different Colors in A Row.", "The 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 There "," Same Beverage "," "" "The Question IS: Who Owns the fish? "," "" "" Einstein's Hints: "," 1. 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 CEN Ter House Drinks Milk "," 9. The Norwegian Lives in The First House "," 10. The Man Who Smokeles Bles "," 11. The Man Who Keeps Horses Lives Next to the One Who Smokes Dunhill, "12. The Owner Who Smokemaster Drinks Beer", "13. The German Smokes Prince", "14. The Norwegian Lives Next To the Blue House", "15. The Man Who Smokeles Blends Has A Neighbor WHO DRINKS WATER "}; For (int i = 0; I While (pchint-> assignproptonexteligibles ()) // seek and assign each eligibles {// with proties. if (ppchint! = & hint [sizeof (hint) / sizeof (chint *) - 1]) // is not the last search (PPCHINT 1); // Search with next hint else // all hill Hort else // all haster (); // a Solution Has Been Found PCHINT-> RemovePropFromPrevelIgibles (); // undo the assign Operations}} // remove property from the new owner if it exists // inline void CHint :: RemoveProperty () {if (m_pNewOwner0) {m_pNewOwner0-> ClearProperty (m_pid0); RegisterOwnership (m_pid0, NULL); // nobody owns m_pid0 now}} __forceinline int CHint :: AssignPropertySetNextPos (CHouse * p0, CHouse * pNext) {m_pNext = pNext; // set next start for next seek if (p0 == NULL) // m_pid0 has a owner alread m_pNewOwner0 = NULL; // set no new owner flag else {m_pNewOwner0 = p0; // keep the new owner for later recall p0-> SetProperty (m_pid0); RegisterOwnership (m_pid0, p0); // p0 now has the title for m_pid0} return -1;} void CMultiPropertiesHint :: removePropFromPrevelIgibles () {transoveproperty (); if (m_pnewource1) {m_pnewowner1-> ClearProperty (m_pid1); Registerownership (m_pid1, null); // Nobody Owns m_pid1 now}}}}} __forceinline int CMultiPropertiesHint :: AssignPropertiesSetNextPos (CHouse * p0, CHouse * p1, CHouse * pNext) {AssignPropertySetNextPos (p0, pNext); if (p1 == NULL) // m_pid1 has a owner alread m_pNewOwner1 = NULL; // set no new owner flag else {m_pNewOwner1 = p1; // keep the new owner for later recall p1-> SetProperty (m_pid1); RegisterOwnership (m_pid1, p1); // p1 now has the title for m_pid1} return -1;} int CKnownHouseHint: : Assignproptonexteligibles () {if (m_pnext == null) // null is the stop signal return 0; CHOUSE * POWNER = GetPropertyOwner (m_pid0); if (pOwner) // property m_pid0 has a owner already {if (pOwner == m_pKnownHouse) // is it the required owner return AssignPropertySetNextPos (NULL, NULL);? return 0;} else if (m_pKnownHouse-> IsEmpty (m_pid0) Return AssignPropertySetNextPos (M_PKNWNHOUSE, NULL); else returnography;} INT CORDEREDNEIGHBORSHINT :: AssignProptonexteligibles () {i (m_pnext> = & house [House4]) // & House [House4] ACTS AS A Stop Sign :) Return 0; CHOUSE * POWNER0 = getPropertyowner (m_pid0); chouse * Powner1 = getPropertyowner (m_pid1); if (pOwner0 && pOwner1) // both m_pid0 and m_pid1 have owners already {if (pOwner1 == pOwner0 1) // pOwner0 is on the immmeadiate left of pOwner1 return AssignPropertiesSetNextPos (NULL, NULL, & house [HOUSE4]); return 0 ;} else if (pOwner0) // pOwner1 == NULL; nobody owns m_pid1 {if (pOwner0 <& house [HOUSE4] && (pOwner0 1) -> IsEmpty (m_pid1)) return AssignPropertiesSetNextPos (NULL, pOwner0 1, & house [ HOUSE4]); return 0;} else if (pOwner1) // pOwner0 == NULL; nobody owns m_pid0 {if (pOwner1> & house [HOUSE0] && (pOwner1 - 1) -> IsEmpty (m_pid0)) return AssignPropertiesSetNextPos (pOwner1 - 1, null, & house [House4]); Return 0;} else // Powner0 == NULL && POWNER1 == NULL; Nobody OWNS M_PID0 or M_PID1 {CHOUSE * P = M_PNext; While (P <& House [House4]) {IF (P-> ISempty (M_PID0) && (p 1) -> ISEMPTY (M_PID1)) Return AssignPropertiesSetNextPos (P, P 1, P 1); P ;} return 0;}} int CSINGLEHOUSEHINT :: AssignproptoneXteligibles () {IF (m_pnext> = & house [count _HOUSES]) // & house [count_houses] ACTS AS STOP SIGN RETURN 0; CHOUSE * POWNER0 = getPropertyowner (m_pid0); chouse * Powner1 = getPropertyowner (m_pid1); if (pOwner0 && pOwner1) {if (pOwner0 == pOwner1) return AssignPropertiesSetNextPos (NULL, NULL, & house [COUNT_HOUSES]); return 0;} else if (pOwner0) // pOwner1 == NULL; nobody owns m_pid1 {if (pOwner0 -> IsEmpty (m_pid1)) return AssignPropertiesSetNextPos (NULL, pOwner0, & house [COUNT_HOUSES]); return 0; // failed} else if (pOwner1) // pOwner0 == NULL; nobody owns m_pid0 {if (pOwner1-> IsEmpty ( m_pid0)) return AssignPropertiesSetNextPos (pOwner1, NULL, & house [COUNT_HOUSES]); return 0;} else // pOwner0 == NULL && pOwner1 == NULL; nobody owns m_pid0 or m_pid1 {cHouse * p = m_pNext; while (p <& house [COUNT_HOUSES]) {if (p-> IsEmpty (m_pid0) && p-> IsEmpty (m_pid1)) return AssignPropertiesSetNextPos (p, p, p 1); p ;} return 0;}} int CNeighborsHint :: AssignPropToNextEligibles () {IF (m_pnext> = & house [House4]) // & house [House4] ACTS AS STOP SIGN RETURN 0; CHOUSE * POWNER0 = getPropertyowner (m_pid0); chouse * Powner1 = getPropertyowner (m_pid1); IF (POWNER0 && POWNER1) {IF (Powner0 - Powner1 == 1 || Powner0 - Powner1 == -1) Return AssignPropertiessetNextPos (Null, Null, & House [House4]); Return 0;} else if (Powner0) // Powner1 == NULL; nobody owns m_pid1 {if (! m_NextReverse && pOwner0 <& house [HOUSE4] && (pOwner0 1) -> IsEmpty (m_pid1)) {m_NextReverse = -1; return AssignPropertiesSetNextPos (NULL, pOwner0 1, pOwner0); } IF (Powner0> & House [House0] && (POWNER0 - 1) -> ISEMPTY (m_pid1)) Return AssignPropertiessetNextPos (NULL, POWNER0 - 1, & House [House4]); Return 0; Else IF (Powner1) // Powner0 = = NULL; nobody owns m_pid0 {if (m_NextReverse && pOwner1 <& house [HOUSE4] && (pOwner1 1) -> IsEmpty (m_pid0)!) {m_NextReverse = -1; return AssignPropertiesSetNextPos (pOwner1 1, NULL, pOwner1);} if (pOwner1> & house [HOUSE0] && (pOwner1 - 1) -> IsEmpty (m_pid0)) return AssignPropertiesSetNextPos (pOwner1 - 1, NULL, & house [HOUSE4]); return 0;} else // pOwner0 == NULL && pOwner1 = = Null {chou E * p = m_pnext; while (p <& house [house4]) {if (! m_nextreverse && p-> iSempty (m_pid0) && (p 1) -> iSempty (m_pid1)) {m_nextreverse = -1; Return AssignPropertiessetNextPos P, P 1, P);} IF (p-> ISEMPTY (M_PID1) && (p 1) -> ISEMPTY (M_PID0)) {m_nextreverse = 0; Return AssignPropertiessetNextPos (P 1, P, P 2) } P = 2;} return 0;}}} // this function is to verify current solution and is to be called. // Return: // Null: failed for search error (s) .// Nonzero: Poin To the Owner of the Fish // chouse * chint :: verifycurrentsolution () {chouse * pfishowner = null; for (int i = 0; i IF (House [i] .Isempty (PET)) IF (Pfishowner) Return Null; Else Pfishowner = & House [i];} Return Pfishowner; // This interface function verifies and prints out the current solution // void CHint :: PrintOut () {IncSolutionCount (); // the solution is valid # if FILL_IN> 0 CHouse * pFishOwner = VerifyCurrentSolution (); IF (pfishowner == null) {PUTS ("Found A Search Error./N"); Return;} // WE Have Also To Fill in The Fish Before Sending a Solution Solution To // The Screen Because Einstein Did Not Mention IT In his hints. // pfishowner-> setproperty (fish); # Endif PrintOut (); #if Fill_in> 0 Pfishowner-> ClearProperty (Fish); // restore the world for further search # endif} // Print A Solution On Console Screen // Some of the Drawing Code in this function is borrowed from manfred becker's .// Void chint :: Print () {static const char scolor [] [7 1] = {"blue" , "Green", "Red", "White", "Yellow"}; static const char snationality [] [9 1] = {"BRIT", "Dane", "German", "Norwegian", "Swede" }; Static const char SBAVERAGE [] [7 1] = {"beer", "coffee", "milk", "tea", "water"}; static const char scigar [] [9 1] = {" Blends "," Bluemastr "," Dunhill "," Pall Mall "," Prince "}; static const char spet [] [7 1] = {" Bird "," CAT "," DOG "," FISH ", "Horse"}; static const char swild7 [] = "*"; static const char swild9 [] = "*"; Static char SLN [] [79] = {"/ / / / / / / / / / / / / / / / / / / / /" / 1 / / / / 5 ///// /// / 5 /// / / / / / / / / / / / / / / / / / / / // "," / ___________ // / ___________ // // / ___________ // / ___________ // "," | | | | | | | | | | | "" | | | | | | | | | | | | | | | | | | | | | | | | | | | |, | | | | | | | | | ___________ | ___________ | | ___________ | | ___________ | "}; //print houses ... in Ti; for (i = 0; i For (i = 0; i #include 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 IdeNum Catid {Color, Nationality, Baverage, Cigar, PET} // Property IdentificationSenum 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 indeicate a null property of any category. // ITS Value Must NOTBE Equal to any real property = (0 << bits_catid) | PET 1}; PropID M_Property [count_categories]; // constructorpublic: chouse () {for (int i = 0; i // operationspublic: 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) {m_property [getcatid (pid)] = pid;} Void ClearProperty (PropID PID) {m_property [getcatid (pid)] = (prop) Empty;} Private: Catid getcatid (propid pid) {return (pid & (count_exted_catid - 1));} int getIndex (propid) {Return PID >> bits_catid;}}; 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 housesprivate: // 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 // constructorProtace: chint: 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; virtual void RemovePropFromPrevEligibles () = 0; // undo AssignPropToNextEligibles virtual void ResetSeekPosition () = 0; // reset the seek to start position static void PrintOut (); // print out a solution // helpersprotected: void removeProperty ( ); // Remove Property from New Owner int assignpropertysetnextPos (CHOUSE * P0, CHOUSE * PNEX); // property register operationsprotected: static CHouse * GetPropertyOwner (PropID pid) {return propowner [pid];} static void RegisterOwnership (PropID pid, CHouse * pOwner) {propowner [pid] = pOwner;} // counterpublic: static int getSolutioncount () {return count_solutions;}; private: static void incsolutioncount () {count_solutions ; // Helper Static CHOUSE * VERIFYCURRENTSOLUTION (); // verify a solution and check for errors static void printout (); // Class for any hint of known house number // CKNWNWNHOUSEHINT: PUBLIC chint {private: chouse * const m_pknown; 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 ();}}; // class for any hint that involves Multiple properties // class CMultiPropertiesHint: public CHint {protected: const PropID m_pid1; // a property in the hint CHouse * m_pNewOwner1; // ptr to a would-be owner of the property to meet the Hint // ImplementationsProtace: Virtual Void RemovePropFromPreveligibles (); // ConstructorProtace: CMULTIPROPERTISHINT (PROPID PID0, PROPID PID1): chint (PID0), M_PID1 (PID1) {} // Helpersprotected: void resetseekpositionTofirsthouse () {m_pnext = & house [House0];} int assignpropertiessetnextpos (chouse * p0, chouse * p1, chouse * pnext); // class for the any hint that only involves a Single houseowner // class CSingleHouseHint: public CMultiPropertiesHint {// constructorpublic: CSingleHouseHint (PropID pid0, PropID pid1): CMultiPropertiesHint (pid0, pid1) {} // ImplementationsPrivate: Virtual Int assignproptonexteligibles (); Virtual void resetseekPosition () {resetseekpositionTofirsthouse ();}}; // class for any hint that involves 2 Neighbors Ordered by direction // class COrderedNeighborsHint: public CMultiPropertiesHint {// constructorpublic: COrderedNeighborsHint (PropID pid0, PropID pid1): CMultiPropertiesHint (pid0, pid1) {} // ImplementationsPrivate: Virtual Int assignproptonexteligibles (); Virtual void resetseekPosition () {resetseekpositionTofirsthouse ();}}; // 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? // Constructorpublic: CNeighBorshint (PropID PID0, PropID PID1): CMULTIPROPERTIESHINT (PID0, PID1) {} // ImplementationsPrivate: Virtual Int assignproptonexteligibles (); Virtual void resetseekposition () {resetseekpositionTofirsthouse (); m_nextreverse = 0;}} // class for finding the solutions // class CSolver {private: static CHint * hint []; // array of pointers to CHint objects static int count_nodes; // count of nodes searched // operationspublic: static void DoTheWork (); / / Search Driver // helpersprivate: static void Search (CHint ** ppCHint); // search engine static void PrintEinsteinRiddleDescription (); static void IncNodeCount () {count_nodes ;}; static int GetNodeCount () {return count_nodes;};};
