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:
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
- "Ages are 20, 22, 24, 26, 28, and 30"
- "Bob is younger than Charlie"
and
- "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.
Running/Exploring the Program
