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

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. 

May 2, 2014:  Another "geocacher" sent me a problem that my program is not solving so far,  yet several other Geocaching heavy-weights have apparently solved it.  The problem (in German) can be found at  http://coord.info/GC3NRMZ.  The current Logic Solver update to Version 5.3 has minor updates in rule numbering and a larger font when printing truth tables.  The primary reason for the update however is to get more eyes to look at the problem to see of there are facts and rules in the description which I haven't picked up on or which the program fails to derive.  A translation of the problem conditions is included in the download source or executable files as GrillEvent_Translated.prb.  

July 23, 2014: Feedback from the May posting led to Logic Version 5.4 posted today.  Bug fixes include:

1. The "Edit" feature to change variable value names lost rules and facts from the save cases file if they had not been viewed before the changes were made.
2. Rules generated by "Order" rules were not displayed in the  Generated Rules display form.
3. Some text of the Reasons for assigned values to truth truth table entries had column and row references reversed.
4. The big one that took a week to find:  The program implements a syllogism called "Disjunction Elimination" which says that if A implies B,  and B implies C,  and we know than A and C cannot both be true then we can conclude that A is not True.   applied to "If" statements generated by "Order" and "If"  rules generated a bad fact if the "If" was assign a False value (i.e. "If A then Not B" instead of  "If A then B").    

The GrillEvent problem is still not solvable without manually assigning some Vehicle position facts on a trial and error basis.  

February 1, 2015: Small change posted updating  (to V5.5) to fix a problem user was having saving a new logic case.  Making a backup copy of the existing file failed under some conditions.  The new strategy just deletes an existing backup file and then changes the existing version file extension from .PRB to .BAK.     

September 8, 2016:   I should rename this project to "The_Program_That_Wouldn't_Die" thanks to  "geocacher" logic puzzles.   This week week's problem is called "Misadventures on Goose Island"; a large puzzle with 5 variables and 8 values per variable.   The size means lots of facts and rules to solve it (on the order of 150 so far).   I alternated between trying to solve it and fixing/enhancing the program with more success on the fixing than on the solving.  I'll leave the final solution to the cacher who reported it to me and just post Logic Version 5.6 for now.   Here's summary of the changes:

As usual, let me know if you find bugs and, especially, if you solve that dang puzzle!

December 21, 2016:  A recent "simple" logic problem from my trusty Mensa Puzzle calendar caused me fits and led to version 5.7 posted today.  The problem "Thanksgiving.prb", contains the clue "Chris ate more turkey than the person who ate the slowest".   In my transcription from the calendar, I typed "fastest" instead of "slowest" which made the problem unsolvable.  After many hours of looking for the non-existent program bug, I finally went back to the original and discovered the real problem (me!).  In the the meantime though I discovered an number ways that invalid rules could go undetected and this version does a better job of gracefully diagnosing them.    The revised program and the new problem are included in the  source and executable downloads below.    

Running/Exploring the Program 

Suggestions for Further Explorations