Can a computer solve a logic word puzzle?
If you are asking whether you can feed the text in, click 'solve it', and out pops the solution -- no. But if you are asking whether there are tools at your disposal to encode the clues of the puzzle -- the answer is YES!
The tools are contained in the field of constraint logic programming in finite domains, CLP(fd). These tools allow you to 'tell' the computer things, such as that a particular number of people (for example, 6 people) each has a last name (which may be different from each other, or maybe not), and the domain of last names to pick from (Smith, Jones, Ford, Adams, Brown, Winters).
The information about the variables is stored in a way which allows the program to interact with the domain of each variable to narrow the possibilities as more and more information is taken into account. The narrowing is either algebraic (X is less than 7, so X cannot be 8, 9, 10, etc) or involves set theory (X reads three magazines of 10, Y reads three magazines of 10, and X and Y share no magazines in common). In solving the puzzles, the domain of each variable reduces to one possibility. When all the variables reduce to one possibility, the puzzle has been solved.
The more you use the tools, the more you will see how they can be used.
My examples can only introduce you to the process. The real proof of your skills will be when you get yourself a Logic Puzzle Magazine and code your own solutions.
How This Site Is Organized
The puzzles are listed under the Puzzle Index. For example, the entry for Arch Friends looks like this:
| Stars |
Title |
Clues |
Answers |
Solutions |
Comments |
Analysis |
| 1 |
Arch Friends |
Clues |
Answer |
Solution |
Hint for newbies: the Analysis explains how to approach this puzzle |
Analysis |
The solutions are written in ECLiPSe, and will work under both version 4.2 and 5.0. If you don't have ECLiPSe, click on the Credits
section and follow the link to their website.
Some Tips:
1. The key is finding a structure for the solution, something that will hold all the clues.
2. Writing solutions is trial and error. If you get multiple answers (i.e., MORE? produces different results), it means you missed a clue. Read each of your answers against all the clues, to see if it fits all the clues. If you swear that more than one answer is right, email me, and I will dig out more info about that puzzle, as my time allows.
I don't have time to figure out why your code doesn't work, though. Post those kinds of questions on
the ECLiPSe user group mail server or comp.lang.constraints for help.
3. If ECLiPSe says there is no solution ("No"), try to isolate what causes it. Typographical errors can cause this, as well as incorrectly coding the clue.
4. If ECLiPSe doesn't find an answer (goes on and on), try to figure out what
triggers the problem by commenting out sections, changing the order of clues, etc.
How long is too long? You decide.
5. If you are new to logic puzzles, get a puzzle magazine, look at the
sample puzzles, read some of the solutions, and try some easy ones, using pencil
and paper. Sometimes clues are stated indirectly. Instead of saying outright "Jones is a woman", the puzzle may say "Ms. Jones wore the red hat".
A general note: Sometimes you have to decide whether
a clue is "given" or whether you should make ECLiPSe figure out that "clue"
from other information. Be fair. When in doubt, put the burden on ECLiPSe to make the
inference.
For example: "1. Josh smokes cigars. 2. The man with the red hat doesn't smoke."
Should you code "Josh ## Red_hat?" Probably not -- let ECLiPSe infer it.
Why ECLiPSe?
Simple: ECLiPSe can solve these puzzles.
Many computer languages can solve a basic "Who owns the zebra?" type of puzzle, but will not be able to handle these puzzles. If
your favorite language will solve these puzzles, let me know.
An email received, 8 Aug 2006:
... there is a programming language F1 (Formula One)
(see www.f1compiler.com),
which is constraint based, with backtracking etc. so it is more than
suitable to solve word puzzles.
I have actually taken some of the puzzles posted on your page and
rewrote them using F1 syntax.
If you are interested, I can provide source code for all of the puzzles,
so you can have sources in ECLIPSE, Prolog and F1.
Thanks (and keep up the good work)
Juro Bystricky
K2 Software Corp.
k2software AT f1compiler.com
Feedback, please! Any suggestions and comments, positive or negative, will be greatly appreciated.