[bb-puzzles] Solution of Minor League Baseball puzzle
Constraint Logic can solve word logic puzzles.
Brought to you by:
dougedmunds
Menu
▾
▴
[bb-puzzles] Solution of Minor League Baseball puzzle
|
From: Carl D. <de...@ma...> - 2001-03-18 19:45:19
|
Dr. Edmonds:
You say on your website that the solution (by Eclispe) of the minor league
baseball puzzle takes longer than the others. How much longer? I suspect
that the reason is that some of the constraints are disjunctive.
I have written a package in Maple6 to solve a special type of CSP. Those
would be CSPs that can be stated in terms of finding an equivalence
relation on a finite set given an initial partition of the set into
Systems of Distinct Representatives (SDRs) of the quivalence classes.
Most logic puzzles from magazines are of this type.
I had never even heard of CSP or Eclipse when I wrote this program. But
now I have been invited to present it at the Application of Computer
Algebra Conference in Albuquerque in June. So I have been doing some
research, which led me to your website, so that I could compare my work to
other work in the field.
Here is how the Minor League Baseball problem is encoded in my system:
(Lines that begin ">" are user input. Lines that begin "#" are comments.
Other lines are program output.
> restart;
# Load my program
> read "C:\\Windows\\Desktop\\LogicProblem.mpl";
# State the initial variables or SDRs.
> V:= ['Name','nick','pos','city','team']:
# Give all possible values for each SDR.
> Name:= [Aaron,Dave,Gary,Jon,Ray,Stan]:
> nick:= [Bigfoot,ChooChoo,Dizzy,Lefty,Stringbean,Tiny]:
> pos:= [center,first,pitcher,right,short,third]:
> city:= [BR, FW, Martin, North, Pensacola, Trenton]:
> team:= [Catfish,Eels,GreenSox,Navigators,Pumas,Tornados]:
# Initialize the problem in the program:
> Baseball:= LogicProblem(V):
> with(Baseball):
# Give the constraints using the notation I developed.
> Constraints:=
> [#Clue 1
> Stringbean<>FW
> ,Distinct([Stringbean, {op(team)} minus {Tornados, Navigators}])
> ,Distinct([FW, {op(team)} minus {Tornados, Navigators}])
> ,Rel(DifferentBlock, Stringbean, FW, team, [{Tornados}, {Navigators}])
> ,Rel(DifferentBlock, FW, Stringbean, Name, [{Aaron}, {op(Name)} minus {Aaron}])
>
> #Clue 2
> ,Dave<>first
> ,Rel(DifferentBlock, Dave, first, city, [{BR}, {op(city)} minus {BR}])
> ,BR=Catfish
>
> #Clue 3
> ,Distinct([Jon, Tiny, Eels, Martin])
>
> #Clue 4
> ,Distinct([Lefty, Tornados, North])
> ,OR([center=Lefty, center=Tornados, center=North])
>
> #Clue 5
> ,Bigfoot=Trenton
>
> #Clue 6
> ,Distinct([short, [Dave, Ray]])
> ,Distinct([short, [Eels, Pumas]])
>
> #Clue 7
> ,Distinct([pitcher, {op(Name)} minus {Aaron, Jon}])
>
> #Clue 8
> ,Dave<>right
>
> #Clue 9
> ,Dizzy=GreenSox
> ,GreenSox<>North
>
> #Clue 10
> ,Pumas<>North
> ,Rel(DifferentBlock, Pumas, North, nick, [{Tiny}, {op(nick)} minus {Tiny}])
>
> #Clue 11
> ,Ray<>Pensacola
>
> #Clue 12
> ,Stan=ChooChoo
> ]:
# Tell program that we want to collect efficiency information:
> CollectStats:= true:
# My program gives a wide amount of control over how much internal
# information is displayed for the user. I will set this at one of the
# medium settings, just to show you some of the info that my program can
# display. You may wish to scan right to the final solution.
> infolevel[all]:= 2:
# Start clock so we can see how much time this takes.
> st:= time():
# Run it!
> Satisfy(Constraints);
Backup: Guessing OR([1, center = Lefty, center = Tornados, center = North]) Depth= 1
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Satisfy: Attempting to fulfill unsatisfied constraints by guessing.
Backup: Guessing BR = center Depth= 2
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Satisfy: Attempting to fulfill unsatisfied constraints by guessing.
Backup: Guessing Eels = Stan Depth= 3
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
&<=>: Contradicts North <> Tiny
Satisfy: Attempting to fulfill unsatisfied constraints by guessing.
Backup: Guessing North = Stan Depth= 4
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Rel/Check: Constraint Rel(DifferentBlock,Pumas,North,2,[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}]) contradicted.
NegateLastGuess: Backing up to last guess. Level = 95
GoBack: Restoring saved state from before guess North = Stan Depth= 3
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Rel/Check: Constraint Rel(DifferentBlock,Stringbean,FW,5,[{Tornados}, {Navigators}]) satisfied.
Rel/Check: Constraint Rel(DifferentBlock,Pumas,North,2,[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}]) contradicted.
NegateLastGuess: Backing up to last guess. Level = 95
GoBack: Restoring saved state from before guess Eels = Stan Depth= 2
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Rel/Check: Constraint Rel(DifferentBlock,Stringbean,FW,5,[{Tornados}, {Navigators}]) satisfied.
Rel/Check: Constraint Rel(DifferentBlock,Pumas,North,2,[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}]) satisfied.
Rel/Check: Constraint Rel(DifferentBlock,FW,Stringbean,1,[{Aaron}, {Jon, Ray, Dave, Gary, Stan}]) contradicted.
NegateLastGuess: Backing up to last guess. Level = 95
GoBack: Restoring saved state from before guess BR = center Depth= 1
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Satisfy: Attempting to fulfill unsatisfied constraints by guessing.
Backup: Guessing Catfish = Stan Depth= 2
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Satisfy: Attempting to fulfill unsatisfied constraints by guessing.
Backup: Guessing Eels = center Depth= 3
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Rel/Check: Constraint Rel(DifferentBlock,Stringbean,FW,5,[{Tornados}, {Navigators}]) satisfied.
Rel/Check: Constraint Rel(DifferentBlock,Pumas,North,2,[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}]) contradicted.
NegateLastGuess: Backing up to last guess. Level = 95
GoBack: Restoring saved state from before guess Eels = center Depth= 2
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Rel/Check: Constraint Rel(DifferentBlock,Stringbean,FW,5,[{Tornados}, {Navigators}]) satisfied.
Rel/Check: Constraint Rel(DifferentBlock,Pumas,North,2,[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}]) contradicted.
NegateLastGuess: Backing up to last guess. Level = 95
GoBack: Restoring saved state from before guess Catfish = Stan Depth= 1
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
&<=>: Contradicts Pumas <> Tiny
NegateLastGuess: Backing up to last guess. Level = 95
GoBack: Restoring saved state from before guess OR([1, center = Lefty, center = Tornados, center = North]) Depth= 0
Backup: Guessing OR([2, center = Lefty, center = Tornados, center = North]) Depth= 1
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Satisfy: Attempting to fulfill unsatisfied constraints by guessing.
Backup: Guessing Trenton = center Depth= 2
&<=>: Contradicts Stringbean <> FW
NegateLastGuess: Backing up to last guess. Level = 90
GoBack: Restoring saved state from before guess Trenton = center Depth= 1
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Satisfy: Attempting to fulfill unsatisfied constraints by guessing.
Backup: Guessing Tornados = Stan Depth= 2
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Rel/Check: Constraint Rel(DifferentBlock,Stringbean,FW,5,[{Tornados}, {Navigators}]) satisfied.
Rel/Check: Constraint Rel(DifferentBlock,FW,Stringbean,1,[{Aaron}, {Jon, Ray, Dave, Gary, Stan}]) satisfied.
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])]]
Satisfy: Attempting to fulfill unsatisfied constraints by guessing.
Backup: Guessing North = Aaron Depth= 3
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])]]
Rel/Check: Constraint Rel(DifferentBlock,Pumas,North,2,[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}]) satisfied.
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])]]
Rel/Check: Constraint Rel(DifferentBlock,Dave,first,4,[{BR}, {Pensacola, FW, North, Martin, Trenton}]) satisfied.
Unsatisfied = []
Satisfy: Complete, consistent solution found. Attempting to prove unique\
ness.
GoBack: Restoring saved state from before guess North = Aaron Depth= 2
&<=>: Contradicts North <> Aaron
NegateLastGuess: Backing up to last guess. Level = 90
GoBack: Restoring saved state from before guess Tornados = Stan Depth= 1
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Satisfy: Attempting to fulfill unsatisfied constraints by guessing.
Backup: Guessing center = Stringbean Depth= 2
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Rel/Check: Constraint Rel(DifferentBlock,Stringbean,FW,5,[{Tornados}, {Navigators}]) satisfied.
Rel/Check: Constraint Rel(DifferentBlock,Pumas,North,2,[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}]) contradicted.
NegateLastGuess: Backing up to last guess. Level = 95
GoBack: Restoring saved state from before guess center = Stringbean Depth= 1
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Rel/Check: Constraint Rel(DifferentBlock,Stringbean,FW,5,[{Tornados}, {Navigators}]) satisfied.
&<=>: Contradicts Pumas <> Tiny
NegateLastGuess: Backing up to last guess. Level = 95
GoBack: Restoring saved state from before guess OR([2, center = Lefty, center = Tornados, center = North]) Depth= 0
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Satisfy: Attempting to fulfill unsatisfied constraints by guessing.
Backup: Guessing North = Stan Depth= 1
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Elim: Contradiction: Complete row eliminated in [Bigfoot, ChooChoo, Dizzy, Lefty, Stringbean, Tiny] x [BR, FW, Martin, North, Pensacola, Trenton]
Rel/Check: Constraint Rel(DifferentBlock,Pumas,North,2,[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}]) satisfied.
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Satisfy: Attempting to fulfill unsatisfied constraints by guessing.
Backup: Guessing Eels = center Depth= 2
Elim: Contradiction: Complete row eliminated in [BR, FW, Martin, North, Pensacola, Trenton] x [Bigfoot, ChooChoo, Dizzy, Lefty, Stringbean, Tiny]
NegateLastGuess: Backing up to last guess. Level = 90
GoBack: Restoring saved state from before guess Eels = center Depth= 1
Elim: Contradiction: Complete row eliminated in [BR, FW, Martin, North, Pensacola, Trenton] x [Bigfoot, ChooChoo, Dizzy, Lefty, Stringbean, Tiny]
NegateLastGuess: Backing up to last guess. Level = 90
GoBack: Restoring saved state from before guess North = Stan Depth= 0
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Satisfy: Attempting to fulfill unsatisfied constraints by guessing.
Backup: Guessing center = Stringbean Depth= 1
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])], [-10, Rel(
DifferentBlock, Stringbean, FW, 5, [{Tornados}, {Navigators}])
], [-10, Rel(DifferentBlock, Pumas, North, 2,
[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}])], [
-10, Rel(DifferentBlock, FW, Stringbean, 1,
[{Aaron}, {Jon, Ray, Dave, Gary, Stan}])]]
Rel/Check: Constraint Rel(DifferentBlock,Stringbean,FW,5,[{Tornados}, {Navigators}]) satisfied.
Rel/Check: Constraint Rel(DifferentBlock,Pumas,North,2,[{Tiny}, {Stringbean, ChooChoo, Dizzy, Lefty, Bigfoot}]) satisfied.
Rel/Check: Constraint Rel(DifferentBlock,FW,Stringbean,1,[{Aaron}, {Jon, Ray, Dave, Gary, Stan}]) satisfied.
Unsatisfied = [[-10, Rel(DifferentBlock, Dave, first, 4,
[{BR}, {Pensacola, FW, North, Martin, Trenton}])]]
&<=>: Contradicts Dave <> BR
NegateLastGuess: Backing up to last guess. Level = 95
GoBack: Restoring saved state from before guess center = Stringbean Depth= 0
&<=>: Contradicts FW <> Stringbean
NormalReturn: Conclusions: 1313
Unique solution:
[Aaron , Stringbean , pitcher , North , Navigators]
[ ]
[Dave , Tiny , third , Pensacola , Pumas]
[ ]
[Gary , Dizzy , short , Martin , GreenSox]
[ ]
[Jon , Lefty , first , BR , Catfish]
[ ]
[Ray , Bigfoot , right , Trenton , Eels]
[ ]
[Stan , ChooChoo , center , FW , Tornados]
> time()-st;
1.265
# The above time is in seconds.
> &? ShowStats;
Sets = 123, Unsets = 280, Elims = 1373, Transfers = 487,
MaxLevel = 1055, Guesses = 14, MaxDepth = 4
-------------------------- End of output
It is clear from the statement of the problem that what is meant by "or"
is really an exclusive or. I have not included an exclusive-or constraint
type in my package, but now I see that I should. That would make this run
faster. The handling of disjunctive constraints was one of the most
complicated parts to write into my program, especially when it is trying
to prove the uniqueness of the solutions. When you encoded this problem
into Eclipse, did you use "or" or "exclusive or"?
Let me know if you would like a copy of my program and several detailed
examples of its use. The examples include problems that are far more
complicated than this one.
Would you mind if I use the above example in the paper I am writing? It
would be especially useful to know how the efficiency of my techniques
compares to Eclipse.
Are you aware of any other work about solving CSPs that can be stated in
terms of finding an equivalence relation given an initial partition of the
set into SDRs of the equivalence classes? I would like to refer to it.
Could you give me an academic reference that uses the zebra puzzle as an
example, either for a CSP program or for a theorem-proving program?
Carl Devore
|
