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:

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:

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 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! 

Running/Exploring the Program 

Suggestions for Further Explorations