If you shop at Amazon anyway, consider using this
link. We receive a few cents from each purchase. Thanks.
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.
Send an e-mail with your
comments about this program (or anything else).
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.
youngest has blonde hair.
2. John is
older than Pete.
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,
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.
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
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.".
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
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
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
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"
- "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:
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:
|If A is x then B is y|
|If B is y then C is x|
|A and C cannot have the same value |
|We can conclude:|
|A 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.
Running/Exploring the 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
December 19, 2012