home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / CLIPPER / MISC / SOLVLOG.ZIP / SOLVLOG.PRO next >
Encoding:
Text File  |  1987-02-25  |  10.6 KB  |  267 lines
  1. /*
  2.         USING TURBO PROLOG TO SOLVE LOGIC PROBLEMS
  3.             BY:  GARRY J. VASS  (72307,3311)
  4.             
  5.     INTRODUCTION
  6.     ------------
  7.     A "logic problem" is a type of exercise wherein a solution is
  8.     arrived at through a process of deduction and elimination.  Most
  9.     commonly, logic problems appear as a brief statement (used to
  10.     identify the dimensions and boundaries) followed by a set of
  11.     clues.  The clues usually fall into four major categories:
  12.     
  13.         1.  Dead giveaways, for example, Mary rode the red horse;
  14.         2.  Eliminations, for example, Sally did not ride the 
  15.             red horse, both Phillipe and Jones rode the 9:45 train, etc.;
  16.         3.  Upper/lower boundaries (actually a type of elimination),
  17.             for example, John was not the first to arrive, 
  18.             Bill paid more than Jack, etc.; and
  19.         4.  "Sneakies" (a more subtle elimination), for example, 
  20.             the person who ate veal dropped her purse, the person
  21.             who drank white wine said he never ate radishes, etc.
  22.                             
  23.     Using clues such as these, it is possible to arrive at a unique
  24.     solution.  
  25.     
  26.     I find that these problems have been somewhat helpful in learning
  27.     TURBO PROLOG (and believe me, I openly concede that I am a mere
  28.     beginner), and the purpose of this file is to share my findings
  29.     with other beginners and to solicit tutelage from the more advanced
  30.     PROLOG wizards.
  31.     
  32.     I am most interested in hearing from both sides.  I can be reached
  33.     via message at box 72307,3311 on Compuserve, at the Omegammon BBS
  34.     (201 - 653 - 3893), or the Police Station BBS (which supports
  35.     a TURBO PROLOG SIG at 201 - 963 - 3115).
  36.     
  37.     NOTES
  38.     -----
  39.     Try the problem using pencil and paper first.  It makes the ANALYSIS
  40.     discussion more lucid.
  41.     
  42.     In interactive mode, use the "final" goal.  This takes an astounding
  43.      amount of time to unify (2 - 3 minutes).  My TURBO PASCAL logic problem
  44.     solver (which uses boolean arrays and recursion and is infinitely 
  45.     more generalized) zips out this solution in about 5 seconds.
  46.     
  47.     I originally started using list structures, but threw those
  48.     overboard because I was unable to program the "deduction through
  49.     elimination" that was needed.
  50.     
  51.     If you are really into it, play with the compiler options.
  52.     
  53.     STATEMENT OF THE PROBLEM
  54.     ------------------------
  55.     Three friends went to a flea market together,
  56.     Ron, Garry, and John (whose last names are Vass, Ross, 
  57.     and Clark - but not in that order).  They returned with
  58.     a monitor, a modem, and a keyboard having paid $150, $200, 
  59.     and $250 (again, no special order).  Using the clues below,
  60.     please provide the correct name, item, and cost relationships.
  61.  
  62.     NOTE:  These were highly specialized items, so any pre-assumptions
  63.            regarding for example, a monitor being more expensive than
  64.            a keyboard, are unwarranted.
  65.     
  66.     CLUES
  67.     -----
  68.     1.  The monitor was the cheapest item.
  69.     
  70.     2.  ron did not purchase the modem.
  71.     
  72.     3.  garry spent less than ross (who did not purchase
  73.         the keyboard).
  74.         
  75.     4.  clark paid $250.    
  76.     
  77.     ANALYSIS
  78.     --------
  79.     There are four dimensions:  first name, last name, item, and cost.
  80.     These appear in the DOMAIN section as firstname, lastname, itemname,
  81.     and costname respectively.  The first three are nominal symbols.  Cost
  82.     has comparison and boundary aspects (less than, greater than, etc.), 
  83.     so it is defined as an integer.
  84.     
  85.     We are given explicit information about    
  86.     
  87.         1.  item and cost (clue 1);
  88.         2.  first name and item (clue 2);
  89.         3.  first name and last name, rather that
  90.             garry is not ross (clue 3);
  91.         4.  last name and item (clue 3);
  92.         5.  first name and cost (clue 3); and
  93.         6.  last name and cost(clue 3 and clue 4).
  94.     
  95.     These readily translate into six rules, which are 
  96.     listed in the PREDICATES section as rule1, rule2, 
  97.     rule3, rule4, rule5, and rule6 respectively.
  98.     
  99.     A valid first name/last name/item/cost combination (or SET) must
  100.     satisfy all of the following conditions simultaneously:
  101.         
  102.         1.  the first name must be valid (e.i. within those
  103.             known to the problem - no marvins or henrys for example);
  104.         2.  the last name must be valid;
  105.         3.  the item name must be valid;
  106.         4.  the cost must be valid; and
  107.         5.  none of the six rules are violated.
  108.     
  109.     The predicate for accomplishing this is the SET predicate.
  110.     
  111.     The problem is now reduced to finding three valid sets at one
  112.     time in such a way that the contents of each set are unique.    
  113.     In other words, we want three valid sets wherein the monitor
  114.     appears only once, the modem appears only once, the keyboard
  115.     appears only once, ron appears only once, and so on.  To help
  116.     get us there, the "alldifferent" and "allsets" predicates are used.
  117.     Use "TRACE" to follow why the "alldifferent" predicates are needed.
  118.     
  119.     The "final" predicate simply formats the program's conclusions.
  120. */
  121. /* ---------- mydirs.inc ------------- */
  122. /* nowarnings   */
  123. /* trace        */
  124. /* check_determ */
  125. /* check_cmpio  */
  126. /*----------- end of mydirs.inc -------*/
  127. domains
  128.     firstname = symbol
  129.     lastname = symbol
  130.     itemname = symbol
  131.     costname = integer
  132. predicates    
  133.     first(firstname)
  134.     last(lastname)
  135.     item(itemname)
  136.     cost(costname)
  137.     rule1(itemname, costname)
  138.     rule2(firstname, itemname)
  139.     rule3(firstname, lastname)
  140.     rule4(lastname, itemname)
  141.     rule5(firstname, costname)
  142.     rule6(lastname, costname)
  143.     set(firstname, lastname, itemname, costname)
  144.     alldifferentfirst(firstname, firstname, firstname)
  145.     alldifferentlast(lastname, lastname, lastname)
  146.     alldifferentitem(itemname, itemname, itemname)
  147.     allsets(firstname,firstname,firstname,
  148.         lastname, lastname, lastname,
  149.         itemname, itemname, itemname,
  150.         costname, costname, costname)
  151.     final    
  152. clauses
  153.     first(X) if            /* The first, last, item, and cost    */
  154.         X = "garry" or         /* predicates are used to initialize  */
  155.         X = "john" or            /* the symbols and to prevent unbound */
  156.         X = "ron".        /* variables in the other clauses.    */ 
  157.     last(X) if
  158.         X = "clark" or
  159.         X = "ross" or
  160.         X = "vass".
  161.     item(X) if
  162.         X = "modem" or
  163.         X = "monitor" or
  164.         X = "keyboard".
  165.     cost(X) if
  166.         X = 150 or
  167.         X = 200 or
  168.         X = 250.            
  169.     alldifferentfirst(A,B,C) if     /* The alldifferent predicates guard    */
  170.         A <> B and        /* against getting non-unique solutions */
  171.         A <> C and        /*                                      */
  172.         B <> C.            /* Try "commenting them out" to see     */
  173.     alldifferentlast(A,B,C) if     /* what I mean by "non-uniqueness"      */
  174.         A <> B and        
  175.         A <> C and        /* A deterministic condition is achieved by */
  176.         B <> C.            /* using alldifferent for any three of the  */
  177.     alldifferentitem(A,B,C) if      /* four dimensions.  So there is no need for*/
  178.         A <> B and              /* an "alldifferentcost" predicate          */
  179.         A <> C and
  180.         B <> C.    
  181.  
  182.     allsets(F1,F2,F3,L1,L2,L3,R1,R2,R3,C1,C2,C3) if
  183.         first(F1) and        
  184.         first(F2) and    /* The allsets predicate is used as a mechanism */
  185.         first(F3) and    /* to provide the "elimination trick" and   */
  186.         last(L1)  and    /* to arrive at a simultaneous, nonredundant*/
  187.         last(L2)  and    /* solution.                                */
  188.         last(L3)  and
  189.         item(R1)  and    /* It succeeds if three sets can be derived */
  190.         item(R2)  and    /* at once.                    */    
  191.         item(R3)  and
  192.         cost(C1)  and
  193.         cost(C2)  and
  194.         cost(C3)  and  
  195.         alldifferentfirst(F1,F2,F3) and 
  196.         alldifferentlast(L1,L2,L3)  and 
  197.         alldifferentitem(R1,R2,R3)  and 
  198.         set(F1,L1,R1,C1) and
  199.         set(F2,L2,R2,C2) and
  200.         set(F3,L3,R3,C3).             
  201.  
  202.       set(First, Last, Item, Cost) if /* The set predicate is used to     */
  203.         first(First) and    /* collect a set of discrete first  */
  204.         last(Last)   and    /* name/last name/item/cost combina-*/
  205.         item(Item)   and    /* tions according to the seven     */
  206.         cost(Cost)   and    /* rules inferred in the problem    */
  207.         rule1(Item,Cost) and    /* statement.                       */
  208.         rule2(First,Item) and    /*                                  */
  209.         rule3(First,Last) and    /*                                  */
  210.         rule4(Last,Item) and     /*                                  */
  211.         rule6(Last,Cost) and    /*                                  */
  212.         rule5(First,Cost).      /*                                  */
  213.     
  214.     rule1(monitor,150) if !.  /* Rule 1 represents everything               */
  215.     rule1(modem,_).              /* known about what an item costs, namely     */
  216.     rule1(keyboard,_).      /* that the monitor costs 150 and other items */
  217.                   /* cost something.                    */
  218.  
  219.     rule2(ron,Item) if               /* Rule 2 represents everything known    */ 
  220.         Item <> "modem" and !.   /* about a combination of first names    */
  221.     rule2(garry,_).                  /* and items:  ron did not take the      */
  222.     rule2(john,_).                   /* modem and the others took something.  */
  223.  
  224.     rule3(garry,X) if          /* Rule 3 represents everything known about */
  225.         X <> "ross" and !. /* a full name:  garry's surname is not ross*/
  226.     rule3(john,_).             /* and the others have a surname.           */      
  227.     rule3(ron,_).               /*                                          */
  228.     
  229.     rule4(ross,Item) if               /* Rule 4 represents everything known about  */
  230.         Item <> "keyboard" and !. /* a last name/item combination:  ross did   */ 
  231.     rule4(clark,_).                   /* not take the keyboard, and the others took*/ 
  232.     rule4(vass,_).                  /* something.                                */              
  233.  
  234.     rule5(garry,X) if          /* Rule 5 represents what is known about  */    
  235.         rule6(ross,Y) and  /* first name/cost combinations:  garry   */
  236.         Y > 150 and        /* paid less than ross (hence less than   */ 
  237.         X < 250 and        /* the maximum), and the others paid      */  
  238.         X < Y  and         /* something.                             */
  239.          !.
  240.     rule5(john,_).
  241.     rule5(ron,_).    
  242.  
  243.     rule6(clark,250) if !.         /* Rule 6 represents what is known about  */
  244.     rule6(ross,Cost) if            /* last name/cost combinations:  clark    */
  245.         cost(Cost) and           /* paid 250, ross paid more than 150, and */ 
  246.         Cost > 150 and !.      /* vass paid something.                   */
  247.     rule6(vass,_).                 /* NOTE:  poor vass is unbound here       */
  248.  
  249.     
  250.     final if
  251.         time(Starthours, Startminutes, Startseconds,Starthundreds) and
  252.         nl and
  253.         write("Beginning at ",Starthours,":",Startminutes,":",Startseconds,":",Starthundreds) and
  254.         nl and
  255.         allsets(F1,F2,F3,L1,L2,L3,R1,R2,R3,C1,C2,C3) and
  256.         write(F1," ",L1," purchased a ",R1," for  $",C1) and nl and
  257.         write(F2," ",L2," purchased a ",R2," for  $",C2) and nl and
  258.         write(F3," ",L3," purchased a ",R3," for  $",C3) and nl and
  259.         time(Endhours,Endminutes,Endseconds,Endhundreds) and
  260.         write("Ending at ",Endhours,":",Endminutes,":",Endseconds,":",Endhundreds) and
  261.         nl.
  262.         
  263.         
  264. /*
  265. goal
  266.     final.
  267. */