Ernest J. Friedman-Hill
(The first in an occasional series of articles)
The following puzzle was posted to the "Programming Diversions" forum by Stevie Kaligis on February 17, 2002.
Three men, A, B, C and their respective wives, Aw, Bw and Cw, were hunting in deepest Peru, when they came across a large river. Luckily there was one boat, however, it could only carry two people at the same time. Due to bitter jealousy, no woman could be left with another man unless her husband was present. How did they manage to cross the river?
A lively discussion ensued, in which some people actually tried to solve the problem.
Think for a minute about how you might solve this puzzle with a computer. Computers are good at brute force search, and so that's probably how you'd want to do it. Coding something like this in Java could be tricky and hard to understand; a rule-based language like Jess (See "http://herzberg.ca.sandia.gov/jess") would be better suited. Java is a rule engine and scripting environment written in Java; it complements, and integrates nicely with, existing Java software.
In this article, I'll show how to solve a logic puzzle like this one in Jess. We will indeed use search, but it will be a heuristically guided search, meaning that irrelevant parts of the search space will be cheaply pruned off and never explored -- making this far more efficient than a true brute-force search using a nested set of for loops.
Rule-based programming is declarative, meaning that you don't write down a precise list of instructions for the computer to follow, but rather concentrate on describing the problem, and allowing the computer to come up with the solution. The description in a rule-based language takes the form of rules; basically, things for the computer to do in a specific situation. The language runtime, called a rule engine, takes all the rules, all the data you supply, and applies the rules to the data according to the semantics of the language. It's a perfect arrangement for non-algorithmic problems -- problems you don't consciously know how to solve.
Declarative programming is powerful, but it's still uncommon enough that many people aren't familiar with it. Furthermore, the concepts that you need to express in declarative programming are different from those you deal with in everyday procedural programming, and this means that the language has to be rather different from Java. This has led to a widespread belief that they're difficult to learn or use, which really isn't true.
What it boils down to is that there are two kinds of rule-based languges in common use: powerful ones, and simple ones. The powerful ones tend to have more difficult syntax, and that scares some people off. Jess is one of the powerful ones, and so its syntax requires a bit of learning. I won't have enough space here to teach you everything about the Jess language, although I'll try to hit the high points. See the Jess web site or the book Jess in Action for more details. I will take the opportunity, though, to try to debunk the myth that the rule syntax is gratuitously hard to understand.
It turns out that this "Jealous husband problem" is not especially easy to solve in Jess. Here, by "not easy" I mean that the solution isn't very short -- it's about 300 well-commented lines of code. This will give us an opportunity to explore what's possible in Jess.
Like any program, ours will need data structures. Since we're Java programmers, we'll use inheritance to express the idea that men and women are categories of person:
(deftemplate person "One of the people who is travelling." (slot name)) (deftemplate man extends person "A male person" (slot wife)) (deftemplate woman extends person "A female person" (slot husband))
Jess templates are very much like Java classes, and slots are like JavaBeans properties -- member variables with getX() and setX() methods. Since we're going to do a search of possible solutions, we'll also need a template to represent one individual node in the search tree. A "state" will represent a moment in time where the boat is on one shore or another, and all the people are out of the boat.
(deftemplate state "One step along the path to the solution." (slot search-depth) (slot parent) (slot locations) (slot last-move))
The "locations" slot will hold a Java HashMap with people's names as the keys, and their locations as the values, so that we know where everybody is at each point in the search tree. The "search-depth" and "parent" slots will keep track of the tree structured relationships between the states, and the "last-move" slot will record which of our intrepid travellers were in the boat in the time leading up to this state.
Then we just define all the people:
(deffacts MAIN::people "All the people involved in the problem." (man (name A) (wife Aw)) (man (name B) (wife Bw)) (man (name C) (wife Cw)) (woman (name Aw) (husband A)) (woman (name Bw) (husband B)) (woman (name Cw) (husband C)))
This construct creates a bunch of objects, or as they're called in Jess, facts. A fact is an instantiation of a template, just as an object is an instantiation of a class. There's one fact for each person mentioned in the problem statement.
Here's how we're going to solve this problem: we'll start from an initial state with all the people on one side of the river. Then we'll create new "state" facts to represent a superset of the legal moves from that state. We'll refine the superset until only legal moves are left. Then we'll repeat the process starting from the new set of states. When a state is created where all the people are on the other side of the river, that's a solution to the problem. We'll print it out along with all the states that led to it, then delete this whole branch of the search tree.
Jess is a rule-based language, so we'll generate the valid moves with rules based on the problem statement. All these rules will make heavy use of utility functions specific to this problem, which we'll look at a little later on.
The complete solution is available here. You'll need to download the trial version of Jess from the web site to run the problem.
A rule consists of two main parts, basically an "if" part and a "then" part. The "if" part comes first and consists of a list of patterns. Each pattern is used to select matching facts from the collection of available facts. A pattern
(man (name ?n))
means this rule should apply to all men, and furthermore, we want to use the variable ?n to mean this man's name (variables in Jess start with a '?'.) If you were reading the rule out loud, you'd say "There's a man, let his name be ?n".
Patterns that start with test are Boolean function calls that can further qualify where the rule applies.
The second main part of each rule is the "then" part; there's an arrow => in between the two parts. The "then" part can contain arbitrary Jess code -- the Jess language includes a complete procedural language as well, and it can work with Java objects and call Java methods, too.
The first rule, move-alone, says that at any time, a person who, in some given state along the search tree, is on the same side of the river as the boat can take the boat and move across the river, creating a new state. Note that a "person" pattern can match either a man or a woman fact, because of their inheritance relationship, just like passing arguments to a method in Java.
(defrule MAIN::move-alone "Any person on the same shore as the boat can move alone across the river." ;; If there is a person named ?n (person (name ?n)) ;; And there is a state ?state <- (state) ;; And in that state, the person is on the same shore ;; as the boat (test (same-shore-as-boat ?n ?state)) => ;; then generate a new state where they've moved ;; across the river (move-alone ?n ?state))
The next rule says that two people of the same gender, who again, are in the same location as the boat, can use it to cross. The "~" symbol means negation, and the "&" symbol means logical "and," so "?n2&~?n1" means "this person's name, let's call it ?n, is different from ?n1." If these person facts were Java objects, the same code might look something like
Person p1 = getOnePerson(); Person p2 = getOnePerson(); String n1; String n2; if (p1 != null && p2 != null && !(n1 = p1.getName()).equals((n2 = p2.getName()))) ... }The "?" and "~" and "&" and "<-" may look strange to you, but note that Java uses just as many odd punctuation marks (and a whole lot of other characters besides!) to express the same concept! In any case, here's the rule:
(defrule MAIN::move-together-same-gender "Any two people of the same gender, both on the same shore as the boat, can move across the river." ;; Given one person ?p1 <- (person (name ?n1)) ;; and another person with a different name... ?p2 <- (person (name ?n2&~?n1)) ;; but the same gender (test (same-gender ?p1 ?p2)) ;; (considering their names in alphabetical order) (test (alphabetical-order ?n1 ?n2)) ;; and in some state ?state <- (state) ;; one is on the same shore as the boat (test (same-shore-as-boat ?n1 ?state)) ;; and the other is on the same shore as the first (test (same-shore ?n1 ?n2 ?state)) => ;; then make a new state where they have crossed together. (move-together ?n1 ?n2 ?state))
The next rule says that a woman and her husband can cross together. I'm not going to comment this one as heavily -- I think you get the idea by now:
(defrule MAIN::move-together-married-couple "Any married couple, both on the same shore as the boat, can move across the river." (man (name ?n1)) (woman (name ?n2) (husband ?n1)) ?state <- (state) (test (same-shore-as-boat ?n1 ?state)) (test (same-shore ?n1 ?n2 ?state)) => (move-together ?n1 ?n2 ?state))
There are two more path-generation rules. They're in a different Jess module, and it's an auto-focus rule. Together, this makes each one something like a background thread: it jumps in and does its business whenever it's needed, but otherwise it stays out of the way.
This rule enforces the "bitter jealousy" constraint by retracting states where a husband and wife are separated, but the wife and another man are on the same shore:
(defrule CONSTRAINTS::unmarried
"A woman and a man not her husband cannot both be
on the same shore, unless the husband is also present."
(declare (auto-focus TRUE))
(woman (name ?wife) (husband ?husband))
(man (name ?husband))
(man (name ?other-guy&~?husband))
?state <- (state)
;; The husband and wife are not on the same shore,
;; but the wife and the other guy are.
(test (and (not (same-shore ?husband ?wife ?state))
(same-shore ?other-guy ?wife ?state)))
=>
;; Delete this state
(retract ?state))
The final move-generating rule looks for circular paths -- states that lead from an identical state earlier in the tree -- and deletes them. This rule uses the "search-depth" and "locations" slots of the state facts directly. The ":" syntax introduces a Boolean function call that constrains that value of a variable -- i.e., "?sd2&:(< ?sd1 ?sd2)" means to assign the value of this slot to the variable ?sd2, but only if it's greater than ?sd1.
(defrule CONSTRAINTS::circular-path
"If a path contains a duplicate state, it is cyclical,
and should be discarded."
(declare (auto-focus TRUE))
(state (search-depth ?sd1) (locations ?map1))
?state <- (state (search-depth ?sd2&:(< ?sd1 ?sd2))
(locations ?map2&:(?map1 equals ?map2)))
=>
(retract ?state))
That's it! The preceding rules will generate all the possible solutions to the problem. Note that these rules are much more general than they could be, so they can actually solve many related problems: for example, they would still work with a different number of couples, and they'd even work if the list included unmarried people. Although there may not always actually be a solution for every set of initial conditions, if a solution exists, these rules will find it.
All that's left is to recognize solutions and print them out. Because a solution is actually a list of states, we need a data structure to represent one. This template holds a pointer to the latest state in the solution, and a list of moves. Each move in the list is just the names of the people who moved at that step. The moves list will be updated as the solution rules walk through the list of states, which are chained together by their "parent" slots.
(deftemplate SOLUTION::moves "A holder for a list of moves (i.e., a solution.)" (slot last-state) (multislot moves-list))
The first solution rule recognizes that a solution exists using the utility function all-across, which returns true when all the people in that state are on the other side; it then creates a "moves" fact to represent this solution.
(defrule SOLUTION::recognize-solution
"If, in a particular state, all
the people are on shore-2, then that
state is the last move in a solution."
(declare (auto-focus TRUE))
?state <- (state (parent ?parent)
(locations ?map&:(all-across ?map))
(last-move ?move))
=>
;; Remove the state
(retract ?state)
;; Create a "moves" fact to describe this solution
(assert (moves (last-state ?parent) (moves-list ?move))))
The next rule iteratively updates the "moves" fact by adding new moves (the modify function updates the values in the individual slots of a fact; it's similar to calling a setter method in Java)
(defrule SOLUTION::further-solution "Walk down the list of states representing a solution, and accumulate the moves." ;; If there's a state ?state <- (state (parent ?parent) (last-move ?move)) ;; and a moves list that indicates this state is the next step ?mv <- (moves (last-state ?state) (moves-list $?rest)) => ;; Then modify the moves list to include this state. (modify ?mv (last-state ?parent) (moves-list ?move ?rest)))
The initial state's "last-move" slot contains no-move, and its parent slot is nil (the Jess equivalent of Java's null). This acts as a sentinel and terminates the search for moves.
To actually display the solution, we just need to walk the contents of moves-list in a particular moves fact and print each item, appropriately formatted. Note that the bind function is how you assign a value to a variable in Jess.
(defrule SOLUTION::print-solution
"A 'moves' fact representing a solution starts with 'no-move'.
When we see one, print the whole thing out as a solution."
?mv <- (moves (last-state no-parent) (moves-list no-move $?moves))
=>
(retract ?mv)
(bind ?i 1)
(bind ?shore "shore-2")
(printout t crlf "Solution found: " crlf crlf)
(foreach ?move ?moves
(printout t ?move
(if (> (?thing indexOf " ") -1) then
" move to "
else
" moves to ")
?shore crlf)
(bind ?shore (opposite-of ?shore))
(bind ?i (+ 1 ?i))))
These are all the utility functions we used in writing our rules. Some of them provide an interesting overview of how Jess code can interact with Java objects. Many of them work directly with the HashMap stored in the locations slot of each state fact. For example, the first function iterates though the map and returns true if all the people are located on the opposite shore. You can see the while loop is using a Java Iterator in the normal fashion.
(deffunction all-across (?map)
"If none of the people are on shore-1, we've found a solution."
(bind ?it ((?map values) iterator))
(while (?it hasNext)
(if (eq "shore-1" (?it next)) then
(return FALSE)))
(return TRUE))
Here are a few more simple functions. This one uses the compareTo method in the String class:
(deffunction alphabetical-order(?n1 ?n2) "Returns true if the two arguments are in alphabetical order." (> (?n1 compareTo ?n2) 0))
This one checks that the two given facts have the same "class name," indicating that the two people are of the same gender:
(deffunction same-gender(?p1 ?p2) (eq (?p1 getName) (?p2 getName)))
These Boolean functions check the contents of the HashMap in a given state to determine whether two people are on the same shore, or whether one person is on the same shore as the boat.
(deffunction same-shore-as-boat(?name ?state) (bind ?map (fact-slot-value ?state locations)) (bind ?num (fact-slot-value ?state search-depth)) (eq (?map get ?name) (boat-location ?num))) (deffunction same-shore(?name1 ?name2 ?state) (bind ?map (fact-slot-value ?state locations)) (eq (?map get ?name1) (?map get ?name2)))
These two functions actually create states. In both functions, the named people are moved to the other side of the river in the new state. Both use the Java clone method to make a copy of the previous state's HashMap and then change the appropriate entries.
(deffunction move-alone (?name ?state)
;; Get a copy of the locations map for the old state
(bind ?map ((fact-slot-value ?state locations) clone))
;; Get the old search depth
(bind ?num (fact-slot-value ?state search-depth))
;; Get the name of the new shore
(bind ?newshore (opposite-of (?map get ?name)))
;; Update the map for the person's new location
(?map put ?name ?newshore)
;; Create the new state fact
(assert (state (search-depth (+ 1 ?num))
(parent ?state)
(locations ?map)
(last-move ?name)))
(deffunction move-together (?name1 ?name2 ?state)
(bind ?map ((fact-slot-value ?state locations) clone))
(bind ?num (fact-slot-value ?state search-depth))
(bind ?newshore (opposite-of (?map get ?name1)))
(?map put ?name1 ?newshore)
(?map put ?name2 ?newshore)
(assert (state (search-depth (+ 1 ?num))
(parent ?state)
(locations ?map)
(last-move (str-cat ?name1 " and " ?name2))))
These last two functions provide nice labels for the two shores. The first one contains the nugget of information that shore-1 and shore-2 are opposite one another.
(deffunction opposite-of (?shore)
(if (eq ?shore "shore-1") then
"shore-2"
else
"shore-1"))
(deffunction boat-location (?num)
"The boat alternates between the two shores."
(if (evenp ?num) then
"shore-2"
else
"shore-1"))
We're almost ready to run our program. The only remaining thing that's necessary is to create the initial state fact. We could hard-code the information, but I'm going to adhere to the D.R.Y. (Don't Repeat Yourself) principle and create the initial state by querying Jess for the list of all person facts, then iterating over that list.
(import java.util.HashMap)
(defquery MAIN::all-people
"List all the person facts, so that we can set up the initial state."
(person))
(deffunction set-initial-state ()
"Set up the first state fact, in which all the people are on one
side of the river. All the other state facts will be created by
cloning this one."
(bind ?map (new HashMap))
;; Get the list of all the people
(bind ?it (run-query MAIN::all-people))
;; Populate the map
(while (?it hasNext)
(bind ?name (fact-slot-value ((?it next) fact 1) name))
(?map put ?name shore-1))
;; Create the state
(assert (state (search-depth 1)
(parent no-parent)
(locations ?map)
(last-move no-move))))
Now, we just execute the program:
;; Reset the engine, assert the deffacts (reset) ;; Call the function that creates the initial state (set-initial-state) ;; Finally, fire the rules! (run)
If you've got the Jess library available in the file jess.jar, and this code in the file wives.txt, then you can run the program using the command
java -classpath jess.jar jess.Main wives.txt
The program finds 8 solutions to the problem as given, taking about one second to run. Each solution looks like
Solution found: Cw and Bw move to shore-2 Cw moves to shore-1 Cw and Aw move to shore-2 Cw moves to shore-1 B and A move to shore-2 A and Aw move to shore-1 C and A move to shore-2 Bw moves to shore-1 Bw and Aw move to shore-2 Bw moves to shore-1 Cw and Bw move to shore-2
Rule-based programming is generally used in more serious pursuits than solving logic puzzles: in processing insurance applications, giving financial advice, making purchase recommendations, inventory control, implementing business rules in the enterprise, and more. Neverthess, the unique characteristics of rule engines make them an ideal way to attack this kind of problem as well. Solving puzzles with Jess is a good way to learn about declarative and rule-based programming. You can read more about Jess at "http://herzberg.ca.sandia.gov/jess"(free trial version available to download) or check out the book Jess in Action.