marcel@uiucdcs.UUCP (marcel ) (02/18/84)
#N:uiucdcs:29700020:000:3720
uiucdcs!marcel Feb 17 11:09:00 1984
Here's another solution to the two-lamps puzzle. (I cooked this one up last
night, and find it more intuitive than the gyrations necessary to get a good
solution out of Prolog).
The problem again:
1. either "a" is on or "b" is on;
2. when "a" is on, "b" is off;
3. "a" and "b" are either on or off.
Find all possible solutions WITHOUT doing an exhaustive
generate-and-test.
There have been a couple of good solutions in Prolog, esp those by Debray (on
net.ai) and that by Naish (above). They both ran roughly as follows:
axiom1(1,_).
axiom1(_,1).
axiom2(1,0).
axiom2(0,_).
axiom3(1).
axiom3(0).
go(A,B) :- axiom1(A,B),
axiom2(A,B),
axiom3(A),
axiom3(B).
You can check that the potential solutions (1,1) and (0,0) are never generated.
The code blurs the distinction between generator and filter so that the
generator need not be exhaustive, without risking loss of actual solutions.
Now that I've got a solution I like, I can afford to air my intuitive
objections to the above solution:
- the axioms must be applied in fixed order (1-2-3), when other orders
are useful and other solution methods are possible;
- I'd rather not specify the default case of axiom 2;
- all the axioms are brought to bear when only two would be sufficient
(1 & 2, or 3 & 2, see below);
- you have to reduce the lamps to elements of a relation, though they
are unrelated except by the axioms (ie the logical problem statement
contains more solution info than necessary);
- I think of the axioms as rules to be executed, not data to be matched.
Here's a solution using a modified version of S.A.Vere's relational production
interpreter. The modifications are:
- an atom in a rule cannot match a variable in the database;
- the interpreter can't use a rule on a term if that rule was used to
produce the term;
- the arrow is implication, ie if the consequent is false we get the
contrapositive (antecedent must also be false);
- if a rule matches, and then fails, the state must be abandoned.
The problem axioms become:
1. lamp(a,X), lamp(b,Y) -> X=on ; Y=on.
2. lamp(a,on), lamp(b,Y) -> Y=off.
3. lamp(_,X) -> X=on ; X=off.
We now pose the question "lamp(a,X), lamp(b,Y)" and get the following
solution process:
lamp(a,on) lamp(a,on) SOLUTION
lamp(b,Y) -<rule2> lamp(b,off)
lamp(a,X) /
lamp(b,Y) --<rule1>
\ lamp(a,on) -<rule2> FAIL
lamp(a,Y) / lamp(b,on)
lamp(b,on) -<rule3>
\ lamp(a,off)
lamp(b,on) SOLUTION
Note that this doesn't use any more rules than necessary to generate each
solution, and that the rules are not constrained as to usage order.
Here we used rules 1 & 3 as generators, and rule 2 in both deductive and
checking modes. Just for interest's sake, here's another solution:
lamp(a,on) -<rule2> lamp(a,on) SOLUTION
lamp(b,Y) lamp(b,off)
lamp(a,X) /
lamp(b,Y) --<rule3>
\ lamp(a,off) SOLUTION
lamp(a,off) / lamp(b,on)
lamp(b,Y) -<rule3>
\ lamp(a,off)
lamp(b,off) -<rule1> FAIL
This time we used only rule 3 as a generator, rule 2 in deductive mode,
and rule 1 as a filter. Now THAT's using knowledge to good effect!
Marcel Schoppers
U of Illinois @ Urbana-Champaign
{ihnp4 | pur-ee} ! uiucdcs ! marcelmarcel@uiucdcs.UUCP (marcel ) (02/18/84)
#R:uiucdcs:29700020:uiucdcs:29700021:000:329
uiucdcs!marcel Feb 17 20:03:00 1984
Here's a simpler solution yet:
lamp(a,on) -<rule2> lamp(a,on) SOLUTION
lamp(b,Y) lamp(b,off)
lamp(a,X) /
lamp(b,Y) --<rule3>
\
lamp(a,off) lamp(a,off) SOLUTION
lamp(b,Y) -<rule1> lamp(b,on)