Christmas gift to comp.lang.prolog

I recently went back to problem

NUT # 1 from the THE NUTCRACKER SUITE

once posted to comp.lang.prolog by D. Dudley - see
http://home.chello.no/~dudley/#section7 for the whole nut suite.

He also posted a solution program at some point: see
http://homepages.tesco.net/binding-time/nut1.html
(it has a text only version at the end).

The problem has a lot of symmetry and after breaking it, there remain
29870 solutions.
The program by D. Dudley takes about 470 seconds to compute them
(I used SWI Prolog)

My own program solving NUT # 1 is my Christmas gift to
comp.lang.prolog :-) You find it at the end.

A few comments first: the problem can be treated as a graph colouring
problem with a particular resource constraint, but to stay closer to
the problem statement, the program uses the terminology from the
problem statement. It lends itself also to a CLP(FD) formulation,
but it is fun to see how to do it in plain Prolog.

The program below finds also 29870 solutions, but in just 1.2 seconds,
yes you saw that right: about 400 times faster than the solution at
http://homepages.tesco.net/binding-time/nut1.html


My program is not "optimal": there is more checking than needed,
and a different order in the CheckList can further improve speed.
(this CheckList can be easily generated from a description of the
positions - in fact it was, and I copied the generated output into my
program - the generation is the less interesting part of the program -
and it takes up no time at all compared to the generation of the solutions)

A more important asset of my program is that can be modified very
easily to explore variations of the original problem, like a larger or
smaller set of languages, or changing the number of students that take
a particular exam ... (you need to read the problem statement to
appreciate that).

If you are curious about what causes that huge performance difference
... try first to find it first yourself, post your conclusions and we
can take it from there.


2004 was mostly a fun comp.lang.prolog year; I hope to see you again in
a more peaceful 2005.


Bart Demoen

/*
Original formulation by D. Dudley:
http://home.chello.no/~dudley/#section7

A
B C D E F
G H I J
K L M N
O P Q R S
T

Students need to be seated on the above positions: they will take an exam.

4 students take Norwegian (n)
4 students take German    (g)
4 students take English   (e)
4 students take French    (f)
4 students take Spanish   (s)

Studenst taking the same exam must be seated in such a way that they
are not "neighbours".

Two positions are neighbours if they are next to each other (in the
above picture) along a horizontal line, a vertical line or a diagonal:
e.g. M has neighbours H I J L N Q R S - see line with (*) in program

Top goal:

?- solve(P).

binds P to a list of languages, which can be mapped directly to the
positions A, B ... T

e.g. one of the solutions is:

P =  [e,n,g,n,g,n,e,f,e,f,g,s,n,s,s,f,e,f,g,s
]

meaning:

on position A put a student taking English
on position B put a student taking Norwegian
...
on position T put a student taking Spanish

*/

solve(Positions) :-
Positions =  [A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T
],
[B,C,G,H] = [n,g,e,f],  % this one breaks some symmetry
CheckList = [A \= [B,C],
B \= [A,C,G,H],
C \= [A,B,D,G,H,I],
D \= [C,E,H,I,J],
E \= [D,F,I,J],
F \= [E,J],
G \= [B,C,H,K,L],
H \= [B,C,D,G,I,K,L,M],
I \= [C,D,E,H,J,L,M,N],
J \= [D,E,F,I,M,N],
K \= [G,H,L,O,P,Q],
L \= [G,H,I,K,M,P,Q,R],
M \= [H,I,J,L,N,Q,R,S], % (*)
N \= [I,J,M,R,S],
O \= [K,P],
P \= [K,L,O,Q],
Q \= [K,L,M,P,R],
R \= [L,M,N,Q,S,T],
S \= [M,N,R,T],
T \= [R,S]
],
Languages =  [[n,n,n,n],[g,g,g,g],[e,e,e,e],[f,f,f,f]
,[s,s,s,s]],
seat_students(CheckList,Languages).


seat_students([],_).
seat_students([Pos \= Neighbours | ToCheck],Languages) :-
 pick_lang(Pos,Languages,RemainingLanguag
es),
all_diff_from(Neighbours,Pos),
 seat_students(ToCheck,RemainingLanguages
).

all_diff_from([],_).
all_diff_from([A|R],X) :-
A \== X,
all_diff_from(R,X).

pick_lang(X,[L|Ls],NLs) :-
L = [X|RL],
(RL == [] ->
NLs = Ls
;
NLs = [RL|Ls]
).
pick_lang(X,[L|Ls],[L|NLs]) :-
pick_lang(X,Ls,NLs).

"Bart Demoen" <bmd@cs.kuleuven.ac.be> wrote in message
news:1103898489.811324@seven.kulnet.kuleuven.ac.be...
> I recently went back to problem
>
>         NUT # 1 from the THE NUTCRACKER SUITE
>
> once posted to comp.lang.prolog by D. Dudley - see
> http://home.chello.no/~dudley/#section7 for the whole nut suite.
>
> He also posted a solution program at some point: see
> http://homepages.tesco.net/binding-time/nut1.html
> (it has a text only version at the end).
>
> The problem has a lot of symmetry and after breaking it, there remain
> 29870 solutions.
> The program by D. Dudley takes about 470 seconds to compute them
> (I used SWI Prolog)
>
<snipped>

Actually, that's my solution not his.

I posted on my site, a day or two after the problem was posted to the NG, in
April '98.

Regards

Bart Demoen <bmd@cs.kuleuven.ac.be> wrote:
...
| The program below finds also 29870 solutions, but in just 1.2 seconds,
| yes you saw that right: about 400 times faster than the solution at
| http://homepages.tesco.net/binding-time/nut1.html
...
| If you are curious about what causes that huge performance difference
| ... try first to find it first yourself, post your conclusions and we
| can take it from there.

I really should analyse properly but I'm gonna lay a bet instead. Your
var CheckList is effectively a global constraint store on the position
values since the "values" of unbound position names are unique "memory
addresses" which aren't renamed on pass-by-value. So the performance
gain is the usual constraint-solving one from being able to prune
whole branches of the search space tree, which is why particular
orderings of CheckList change how much of the tree is searched. The
original version has a ground "CheckList" so can't refer to sub-trees
of solutions.

--
Patrick Herring, http://www.anweald.co.uk/ph.html

John Fletcher wrote:
> "Bart Demoen" <bmd@cs.kuleuven.ac.be> wrote in message 
>
> <snipped>
>
> Actually, that's my solution not his.
>
> I posted on my site, a day or two after the problem was posted to the NG, 
in
> April '98.

My apologies - I don't know why I thought it was his, but it seems I was
mistaken.
I am actually happy you are the author: you are on speaking terms with
comp.lang.prolog, so we might get some insights in how you went about
constructing that program - that is, if you care to comment.

Regards

Bart Demoen

"Bart Demoen" <bmd@cs.kuleuven.ac.be> wrote in message
news:1104170053.100096@seven.kulnet.kuleuven.ac.be...
> John Fletcher wrote: 
NG, in 
>
> My apologies - I don't know why I thought it was his, but it seems I was
> mistaken.
> I am actually happy you are the author: you are on speaking terms with
> comp.lang.prolog, so we might get some insights in how you went about
> constructing that program - that is, if you care to comment.
>

Bart

I can't remember the thought processes of an afternoon in 1998 at this
remove, although it is clear that I was concentrating on eliminating
candidate and subject permutations, so I simply allocated them in order.
It's also clear that I was satisfied just to get a solution - I'm sure I
knew that generating successors naively would affect time-complexity.

However, having seen how well your program performs,  I've modified my
solution to traverse a list of location cells in the same way -
allocating candidates to locations, rather than locations to candidates.

It uses a variation of  your allocation strategy too, but modified to
eliminate subject permutations by restricting the subjects available for
allocation at each step.

The code is simpler than it was and, on Quintus 3.4, the execution
time is around 1.33 times that for your solution. You can find it at its new
home: http://www.zen37763.zen.co.uk/nut1.html .

A question though: in your solution, you use a "symmetry breaking"
assignment, which apparently eliminates subject permutations as well as
reducing the search space. Where does it come from?

Regards

John Fletcher wrote:
> However, having seen how well your program performs,  I've modified my
> solution to traverse a list of location cells in the same way -
> allocating candidates to locations, rather than locations to candidates.
>
> It uses a variation of  your allocation strategy too, but modified to
> eliminate subject permutations by restricting the subjects available for
> allocation at each step.
>
> The code is simpler than it was and, on Quintus 3.4, the execution
> time is around 1.33 times that for your solution. You can find it at its n
ew
> home: http://www.zen37763.zen.co.uk/nut1.html .

Thanks for replying.
I haven't had time to look at your new program, but I will.
The (biggest part of the) speed difference is definitely due to the
allocation strategy. I will come back to this later.
(also to you Patrick)


> A question though: in your solution, you use a "symmetry breaking"
> assignment, which apparently eliminates subject permutations as well as
> reducing the search space. Where does it come from?

There are two things in my program that break symmetry: subject
permutation is prevented by assigning fixed languages to locations
B,C,G,H - they must be different because they form a 4-clique.
And because they must be all different, you can use them for breaking
symmetry (using 5 would be too much, 3 too little).
That just came from my head :-)
Candidate permutation is prevented by never assigning another same
language to the same location - it is done by having these
language-available lists (which initially contain 4 or 5 times the same
language) and from which the program always takes the first, never the
second. I would say that this is folk-lore (details on how to do it can
differ - I could have choosen for a term 5*n to represent that fact that
I still have 5 times the language Norwegian, but I tend to avoid
arithmetic in my Prolog programs).

The reduction in search space does not come from my particular way of
breaking symmetry, it's all in the allocation strategy.

Cheers

Bart Demoen

Hi Bart,

your program can be changed to perform about half the number of
identity tests.  Since you allocate in the order A, B, C, ..., there is
no need to, say, test for C \== X where X in {D, E, F, ...} when you
allocate C because those tests are guaranteed to succeed.  This trick
allows you to make your program pure by using \= rather than \==.
-- Ralph

rafe@cs.mu.oz.au wrote:
> Hi Bart,
>
> your program can be changed to perform about half the number of
> identity tests.  Since you allocate in the order A, B, C, ..., there is
> no need to, say, test for C \== X where X in {D, E, F, ...} when you
> allocate C because those tests are guaranteed to succeed.

Hi Ralph,

I know - that's why my original post said:

> My program is not "optimal": there is more checking than needed,

My first version worked like you indicate, but I found it too difficult
to justify the more weird form of the CheckList from the beginning.


> This trick
> allows you to make your program pure by using \= rather than \==.
> -- Ralph
>

I would actually (almost) turn the argument around: with this trick, I
can keep using \== because the mode in which it is used makes it pure.
Is that ok ?

Cheers

Bart Demoen

"Bart Demoen" <bmd@cs.kuleuven.ac.be> wrote in message
news:1104213776.534346@seven.kulnet.kuleuven.ac.be...
> John Fletcher wrote:
<snipped>
> There are two things in my program that break symmetry: subject
> permutation is prevented by assigning fixed languages to locations
> B,C,G,H - they must be different because they form a 4-clique.
> And because they must be all different, you can use them for breaking
> symmetry (using 5 would be too much, 3 too little).
> That just came from my head :-)

I understand this now: the four locations must be "mutually interfering", to
require that they are all different in every solution. Three would not
eliminate all permutations without further checks, five would eliminate
valid solutions. It's neat, but not obvious.

<snipped>

> The reduction in search space does not come from my particular way of
> breaking symmetry, it's all in the allocation strategy.

Further to the above, any four locations in a square will break
symmetry but, at a wild guess, the ones you have chosen will give the
biggest search space reduction.

Regards

John Fletcher wrote:
> Further to the above, any four locations in a square will break
> symmetry

yes - not obvious, but you figured it out (people fluent in
Polya counting and the like, would probably find it totally trivial
and not worth talking about)

> but, at a wild guess, the ones you have chosen will give the
> biggest search space reduction.

yes and no ...
With the particular order in CheckList, I think yes: it usually pays
off to reduce at the top of the search tree; but suppose you would have
chosen the square H I L M for symmetry breaking by pre-assigning, then
you can just reorder the CheckList so that H I L M  are at the beginning
(and interfering locations nearby in the CheckList undsoweiter) and you
would have a similar (and actually larger) search space reduction: one
of my versions of the program does that and it runs twice as fast, which
seems to indicate that the search space is reduced more.

Cheers

Bart Demoen