[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math Topics]   [Library]   [Utilities]

 

Search

 

Search DelphiForFun.org only

Support DFF

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

In Association with Amazon.com

 

Support DFF

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

 

 

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

 

Search DelphiForFun.org only

 

 

 

 

 

Problem Description

This is a program that can help solve many logic problems commonly found in puzzle magazines and books.  Here is a simple example: 

Mary, John and Pete have red, brown, and blonde hair, and are 13, 14, and 15 years old .  Using the following clues determine the hair color, and age of each child.

1. The youngest has blonde hair.

2. John is older than Pete.

3. John does not have red hair and Pete does not have blonde hair.

 

This problem is included as problem "#00 Sample Problem.prb" with the downloads.  Ten more challenging problems are also included.

Background & Techniques

To be solvable by this program, there must be an equal number of possible values for each variable and each value applies to exactly one entity, usually a person.   In the example above we have  variables Name, Hair,  and Age with three values of each.  The one-to-one requirement means there  there cannot be two 13 year olds, none of the kids can be bald, etc.     Nearly all logic puzzles that I have run across meet this condition. 

The program operates by taking user supplied facts and rules and building a truth table for each pair of variables with one row for each  possible value for variable 1 and one column for each possible value for variable 2.  The cells at intersections contain "T" if the relationship (e.g. the 13 year old has red hair) is true, "F" if the relationship is false ("the 13 year old does not have red hair") and "U" if the truth of the relationship is unknown.  Rules of logic are used to fill in the tables.  If we reached a state where all "U"s have been replaced, the problem is solved.   For information about the logic rules used to convert facts and rules into truth table values, see this Logic Techniques page. 

User Input

Six tab sheets are used to describe the problem.  Three of these (Facts, Order Rules, and If Rules) are filled in by the user as his contribution to solving the problem.  The challenge is to extract enough information from the text  in a form that the program can understand and use to successfully solve the problem.  

 The other three tab sheets (Description, Variables, and Connecting Words) may be changed only when operating in "Author" mode.  Author mode is also used to define a "Solution" set of facts and rules which the user may optionally load to view the solution.   There is a radio button at the bottom of the form  which  allows the user to view these predefined solution rules and facts.  The tab sheets are:

bullet Description: Text describing the problem. You'll commonly find numbered paragraphs at the bottom of the description pages. These may be used as reference numbers while defining facts and rules. (Note to authors - reference paragraphs must begin with a number and be preceded by a blank line.)
bulletVariables: Defines the variables based on information in the description.  Each variable definition consists of the variable name followed by variable values, all separated by commas.  (Authors note - each variable must have the same number of values.)
bullet Facts: Use this page to define the known facts. Facts are true statements may be of positive form "John has red hair" or negative form "Mary is not the one who is 13."  When generating rules, it is helpful to select a reference number from the dropdown list at the top of the page.  The text of that paragraph will be displayed as you extract facts.
bulletOrder Rules: Information is sometimes given about the ordering of values with respect to some variable. These may be of two forms: Order rules; "John is older than Mary" or "Pete is one year younger than John.". The other variety is a Separation rule. Here we know the "distance" between two values but not the direction: "Mary and John were born two years apart".
bullet If Rules: These are rules that specify relationships that are conditionally true (or false) based on the truth (or falsity) of some other relationship. "If the 13 year old has red hair then John is the oldest child"  
bullet Connecting Words: When truth table are generated, you can click on any cell to see the reasoning that assigned the value. By default, the text describing relationships between values uses the verb "is" and the negation by "isn't". "John is 13" reads OK, but "John is red hair" doesn't. The author (anyone who selects Author mode from the Options menu) can use the Connecting Words grid to provide alternative verbs so that the text would read "John has red hair" or "John doesn't have red hair".

You can click the "Solve" menu item to process the current set of facts and rules. A screen with resulting value  assignments will be displayed. The "Display Truth Tables" button there displays all truth tables.  Clicking on any truth table cells on that screen will display the reasoning that led to that value assignment.  

You can use the "Options" menu item to make yourself an Author New problems can be defined and  Description/Variables/Connecting Word information can be modified only in Author mode

Ten starter problems are included here - play with them, then try authoring you own. 

Non-programmers are welcome to read on, but may want to skip to the bottom of this page to download an executable version of the program.

Notes for Programmers

I wrote version 1 of this program  in 1988 using Turbo Pascal under DOS.  That explains some of the apparent inconsistencies.  For example, the original program had no interactive user interface, the program read a text file of facts and rules and printed truth tables as the solution to the problem.  So  lots of format error checking in the the solving unit, U_Solve is probably redundant.   Input data for U-Solve is  now generated by the user interface unit, U_Logic.    Problem files  with a .prb extension provide the interface.  These are  init files with separate sections for:

bulletCommon description data and variable definitions (DESCRIPTION section); 
bulletOriginal solution facts and rules  written by the one who entered the problem ( ORIG section) and 
bulletUser defined facts and rules entered by the program user as he tries to solve the problem ( USER section).  

The Logic techniques page provides more information about how facts and rules are processed.  Because the code is old, the data structure selected back then,  and perhaps because of inherent complexity,  tracking subscript usage down in the bowels of the code is a non-trivial exercise.  But the 5000+ lines of code do seem to be mostly working so, for now,  I've adopted the old "If it's not broke, don't fix it" policy.    Lot's of room for future work in this area though.  If only it paid better...

 

Addendum February 26, 2003:    Version 3 was posted today.  It includes a number of bug fixes and several enhancements.   Order rules now generate and additional fact that formerly had to be entered by the user.  (e.g. "John had class after the cat owner" now generates the fact  : "John is not the cat owner")  In author mode, variable values may now be changed and changes automatically reflected in existing fact and rules.   Many incorrect or missing explanations when clicking on truth table values now appear correctly.

Addendum May 11. 2010:  A minor update (Version 3.1) was posted today to clarify and correct some spelling errors in the descriptive text, enlarge text size for these old eyes , and convert references to DelphiForFun.org into live hyperlinks. 

June 4, 2010:  Version 3.2  fixes a program bug uncovered by viewer Erich and gave me a chance to dig into the code and appreciate how smart I used to be J.  Here's the deal.  One of the Rules of Inference is that  "If" statements are transitive, i.e. if we are given that  "A implies B" and "B implies C" then we can conclude that "A implies C".   If we are also given that A and C cannot both be true then we can conclude that A must be false (If A were true then C would have to be true, a contradiction.)  The problem was that my code concluded that A must be true.  

Fortunately the condition doesn't occur very often.  In Erich's case, 5 guys had 5 different ages and among other given propositions were

  1. "Ages are 20, 22, 24, 26, 28, and 30"
  2. "Bob is younger than Charlie" and
  3. "If Bob is 20 then Charlie is 24". 

Proposition 2 is redundant and could be eliminated but it should not do any harm to include it.  Within the program this is called an "Order Rule" and among other things, the program generates a valid rule saying that "if Charlie is 22 then Bob is 20" since that would be the only way that Bob could be younger.  So now, by this generated propositions and proposition 3 above (and the transitive property of conditional statements) , we can generate the proposition that  "If Charlie is 22 then Charlie is 24" which can never be satisfied .  Since this condition can never be met, we can conclude that Charlie is certainly not 22.  And now the program does that correctly.  

For programmers, a small change to adjust the results display  width for large problems uses the AdjustGridWidth procedure from our DFF Library.  As a result, a one time download of the library Zip file will be required to recompile the program.          

January 12, 2012:  A team of  7 puzzlists  recently wrote asking for an increase in the maximum problem size that our solver could handle  for an Internet puzzle they were working on.  Last week I posted Logic Solver Version 3.3 which  increases the maximum number of statement references from 25 to 50, the maximum number of variables from10 to 20, and the maximum number of facts from 100 to 300.  Yesterday I received this email:

 Hi Gary,
 I'd like to thank you so, so, so, so much for your help. I (being responsible for most of the IT stuff) and the team, a group of another six, have just solved the riddle.  An enormous beast: I've used 155 facts and just 7 order rules (tried to keep them to a minimum to reduce complexity). Now the outdoor part is to continue :-)  I've invested about 45 hours within the last 2 1/2 days, and two other people also about the same time. All this was only possible by using your program!  Thanks a lot.

I'm just hoping that they win  a large cash prize to supplement the satisfaction of solving, and that they decide to share a little of it with me! 

May 2, 2012:  It turned out that there was no prize for the January problem  - like me, they are willing to "work for fun".  A different kind of limit was exceeded this time by another avid logic problem solver.  He was tripped up by a problem which has 10 values for each variable.  It's a Geocaching setting  with 10 teams , from 10 towns, each with a different number of hidden geocaches which must be matched up based on given clues.  Previous program versions would handle 10 values per variable in theory but only 9 in practice.  Logic Solver Version 4 increases the limit to 15.   I also improved to Fact and Rule sorting so that items  are ordered more logically with like items appearing contiguously.  The font size for the truth table display and printing was increased since the 10 values at the previous size required a magnifying glass to read!    The problem is included with the downloads as "GeoCaching(Hard).prb".  It has several clues which suggest a new Rule type; a "Choices"  rule to handle a statements like "X is A or B".  Currently this must be handled by creating facts "X is not C", "X is not D", etc. for all  possible values which are not A or B.  The program should be able to generate these negative facts for us, and,  one of these days, it will.             

May 8, 2012:  The CHOICE statement type was added to generate Version 4.1 today.  For the GeoChaching  problem described above, it saves about 30 handwritten Fact statements which are now generated from 3 "Choice" rules.   Lots of hiding places for bugs in the 6000 or so lines of code in this program and adding a new statement type explore  many of them.  As usual,  please use the Feedback link to let me know if you find any I missed.

November 19, 2012:  Version 4.2 fixes posted today a minor logic bug which, in a "logic" program, is really not a good thing.  I call it minor because it involves a syllogism in the program which rarely occurs.  I'm sure it has a name, but I haven't been able to locate it online.  The syllogism says:

bulletGiven
bulletIf A is x then B is y
bulletIf B is y then C is x
bulletA and C cannot have the same value   
bulletWe can conclude:
bulletA is not x

After 10 years, someone finally tried a problem which uses it.  The fix was also minor, two lines of code, but finding the two lines that needed changing took about 20 hours of debugging over the course of a week.  One more example of the "never give up" attitude of successful problem solvers.  And oh so satisfying when you crack it! 

December 16, 2012:  I  love that the "Geocachers" are using this program to solve puzzles that are related to finding real hidden caches and the problems are hard!  This week's update to Version 5 is the result of problems uncovered by a problem (in German) submitted by "cacher" Martin.  He solved the problem with pencil and paper, but neither of has gotten this Logic program to resolve the complete solution.  Either an undiscovered program bug or one subtle condition hidden in the problem statement needs to be found.  After two weeks of working on it, I'm posting the updated version and the original problem for other brave souls to tackle.  The problem without rules but with the description (with English translations of clues)  and the Variable definitions is included in the downloads as
 "Mystery Könige_W_English_WO_Rules.prb"    The original  posting of the problem is at http://coord.info/GC2MGJE.   (Use your browser to translate it to English if you want some laughs.)  There may well be additional updates in January, but, for now, other more pressing items (like Christmas J) are demanding my time.  The current version adds a "Log" file to help track how the program is reaching it's conclusions and  fixes  some minor bugs.

December 19, 2012:  Martin jumped on the new log and pointed out  areas where the program was not reaching conclusions as it should.  The program uses a technique called (in English) "Reduce to absurdity" where we assume some unknown value is true and see if that leads to conflict with some other rule or fact.  The previous version only applied this check when there were 2 possible values for a variable with respect  (e.g. Ann is married to Bob or Charlie).  We now check all unknown pairings of every variable value with every other variable value. Runtime is increased by a few seconds but...   "Mystery Könige"  is now solvable with a dozen or so "Facts" and several "Order" and "If" rules.  Version 5.1 posted today implements this change as well as improved formatting of log and generated rules, and fixing  problems with "Save As" option when in User mode and overlapping Truth Table displays unless the form was maximized.  The program is much improved now thanks to  the hours that Martin, (aka xMRi  to the Geocaching world),  spent testing and reporting problems to me. 

June 25, 2013: Small change today as Version 5.2 so that the  New menu option now resets all fields from the previous case.  Previous versions, for example, retained the number of values per variable from the previous case when starting a new case. 

Running/Exploring the Program 

bulletDownload  executable (with sample problems)
bulletDownload source (includes sample problems)
bulletDownload current DFF Library file ,DFFLibV14_24Mar2014 , (required to recompile this program)

Suggestions for Further Explorations

Handling of "or" conditions is weak and could be improved.  "A or B" can currently only be handled in its conditional form: "If not A then B"
User interface in "Author" mode needs improvement.  And authors definitely need an "Author's Guide" that I'm too lazy to write.  
For extra credit: modify the program to take original problem text and extract variables, rules and facts without requiring human assistance.  Sigh..... just when we were starting to feel so smart. 

 

Original Date: August 5, 2002 

Modified: June 25, 2013

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright © 2000-2013, Gary Darby    All rights reserved.