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:

• 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.)
• Variables: 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.)
• 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.
• Order 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".
• 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"  
• 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:

• Common description data and variable definitions (DESCRIPTION section); 
• Original solution facts and rules  written by the one who entered the problem ( ORIG section) and 
• User 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.          

Running/Exploring the Program 

• Download  executable (with sample problems)
• Download source (includes sample problems)
• Download current DFF Library file ,DFFLibV13 , (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.