THE NUTCRACKER SUITE - NUT # 1
Daniel Dudley
THE NUTCRACKER SUITE - NUT # 1
A university was to hold an examination in 5 subjects: Norwegian, German,
English, French and Spanish. In each of these languages there were 4
candidates. The examination room was therefore divided into 20 cells, as
shown in the figure below (view this in a fixed font):
X
X X X X X
X X X X
X X X X
X X X X X
X
The university's administration wanted to secure themselves against
cheating. Candidates in the same language were to be completely isolated
from each other - so much so that their cells were not to coincide even at
the corners.
A young lecturer was given the job of finding a solution to the problem,
which he did, and justly received a pat on the back from the dean.
Now it just so happens that the dean is an ardent prolog programmer in his
spare time (how else could he make dean?) and, realizing that there could
be several solutions to the problem, used his skills to find all solutions.
Can you do the same?
--
Daniel
Bernhard Pfahringer
/*
Here we go, not the most elegant solution, but
quite simple. Assume each cell is represented
by a logical variable as follows:
A
BCDEF
GHIJ
KLMN
OPQRS
T
to execute, use: solve(L),show(L).
Total solution count is 3584400.
*/
solve([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T]) :-
assign_all([A-[],
B-[A],
C-[A,B],
D-[C],
E-[D],
F-[E],
G-[B,C],
H-[G,B,C,D],
I-[H,C,D,E],
J-[I,D,E,F],
K-[G,H],
L-[K,G,H,I],
M-[L,H,I,J],
N-[M,I,J],
O-[K],
P-[O,K,L],
Q-[P,K,L,M],
R-[Q,L,M,N],
S-[R,M,N],
T-[R,S]],
[4-n,4-g,4-e,4-f,4-s]).
assign_all([],[]).
assign_all([X-Difs|L],Choices) :-
assign(X,Choices,Choices1),
all_dif(Difs,X),
assign_all(L,Choices1).
assign(V,L,L2) :-
select(N-V,L,L1),
( N == 1 ->
L2 = L1
; N1 is N-1,
L2 = [N1-V|L1]
).
select(X,[X|L],L).
select(X,[Y|L],[Y|L1]) :- select(X,L,L1).
all_dif([],_).
all_dif([X|L],V) :-
X \== V,
all_dif(L,V).
show([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T]) :-
write(' '),write(A),nl,
write(' '),write(B),write(C),write(D),write(E),write(F),nl,
write(' '),write(G),write(H),write(I),write(J),nl,
write(' '),write(K),write(L),write(M),write(N),nl,
write(O), write(P),write(Q),write(R),write(S),nl,
write(' '),write(' '),write(' '),write(' '),write(T),nl.
--
--------------------------------------------------------------------------
Bernhard Pfahringer
Austrian Research Institute for http://www.ai.univie.ac.at/~bernhard/
Artificial Intelligence bern...@ai.univie.ac.at
Robert F. Staerk
In article <6i4g1n$2ukk$1...@www.univie.ac.at>, bern...@korb.ai.univie.ac.at
(Bernhard Pfahringer) wrote:
> /*
>
> Here we go, not the most elegant solution, but
> quite simple. Assume each cell is represented
> by a logical variable as follows:
>
> A
> BCDEF
> GHIJ
> KLMN
> OPQRS
> T
>
> to execute, use: solve(L),show(L).
>
> Total solution count is 3584400.
>
> */
Note, that when you permute the languages [n,g,e,f,s] you
obtain again a solution. So you have to divide 3584400
by 5! to obtain the number of solutions modulo
permutations (= 29870).
You can achieve this directly. Look at:
A
B C
G H
The cells B, C, G, H have to be pairwise different.
The cell A can be G, H or the fifth language.
So you have essentially three assignments for A,B,C,G,H:
s e f
n g n g n g
e f e f e f
Robert F. Staerk http://www-iiuf.unifr.ch/~staerk
Institute of Informatics robert...@unifr.ch
University of Fribourg
Rue Faucigny 2
CH-1700 Fribourg, Switzerland
Ralph Becket
/**
Nutcracker Problem 1
Ralph Becket <rw...@cam.sri.com>
Tue Apr 28 19:00:47 BST 1998
Five languages [n,g,e,f,s].
Four students of each language.
Desk layout:
1
2 3 4 5 6
7 8 9 10
11 12 13 14
15 16 17 18 19
20
No two students of the same language may sit within a king's move
of each other.
To solve, place each set of students such
that none are within a king's move of each other.
This avoids the problem of permuting students by requiring that student i be
placed in a lower numbered seat than student i+1 from the same group.
It also avoids the problem of permuting languages by requiring language
i's first student to be placed in a lower numbered seat than language
i+1's first student.
Question: does this also cover rotations and reflections?
I'll post the results when this thing stops running...
**/
solve(N) :-
findall(x, place_all(_), Solutions),
length(Solutions, N).
place_all(Seats) :-
seats(Seats),
place_four(n, Seats, Nn),
place_four(g, Seats, Ng), Nn < Ng,
place_four(e, Seats, Ne), Ng < Ne,
place_four(f, Seats, Nf), Ne < Nf,
place_four(s, Seats, Ns), Nf < Ns.
place_four(L, Seats, N1) :-
seats(Denied),
place(N1, L-1, Seats, Denied),
place(N2, L-2, Seats, Denied), N1 < N2,
place(N3, L-3, Seats, Denied), N2 < N3,
place(N4, L-4, Seats, Denied), N3 < N4.
seats(s(_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_)).
place( 1, L, s(L,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_),
s(L,x,x,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_)).
place( 2, L, s(_,L,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_),
s(x,L,x,_,_,_,x,x,_,_,_,_,_,_,_,_,_,_,_,_)).
place( 3, L, s(_,_,L,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_),
s(_,x,L,x,_,_,x,x,x,_,_,_,_,_,_,_,_,_,_,_)).
place( 4, L, s(_,_,_,L,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_),
s(_,_,x,L,x,_,_,x,x,x,_,_,_,_,_,_,_,_,_,_)).
place( 5, L, s(_,_,_,_,L,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_),
s(_,_,_,x,L,x,_,_,x,x,_,_,_,_,_,_,_,_,_,_)).
place( 6, L, s(_,_,_,_,_,L,_,_,_,_,_,_,_,_,_,_,_,_,_,_),
s(_,_,_,_,x,L,_,_,_,x,_,_,_,_,_,_,_,_,_,_)).
place( 7, L, s(_,_,_,_,_,_,L,_,_,_,_,_,_,_,_,_,_,_,_,_),
s(_,x,x,_,_,_,L,x,_,_,x,x,_,_,_,_,_,_,_,_)).
place( 8, L, s(_,_,_,_,_,_,_,L,_,_,_,_,_,_,_,_,_,_,_,_),
s(_,x,x,x,_,_,x,L,x,_,x,x,x,_,_,_,_,_,_,_)).
place( 9, L, s(_,_,_,_,_,_,_,_,L,_,_,_,_,_,_,_,_,_,_,_),
s(_,_,x,x,x,_,_,x,L,x,_,x,x,x,_,_,_,_,_,_)).
place(10, L, s(_,_,_,_,_,_,_,_,_,L,_,_,_,_,_,_,_,_,_,_),
s(_,_,_,x,x,x,_,_,x,L,_,_,x,x,_,_,_,_,_,_)).
place(11, L, s(_,_,_,_,_,_,_,_,_,_,L,_,_,_,_,_,_,_,_,_),
s(_,_,_,_,_,_,x,x,_,_,L,x,_,_,x,x,x,_,_,_)).
place(12, L, s(_,_,_,_,_,_,_,_,_,_,_,L,_,_,_,_,_,_,_,_),
s(_,_,_,_,_,_,x,x,x,_,x,L,x,_,_,x,x,x,_,_)).
place(13, L, s(_,_,_,_,_,_,_,_,_,_,_,_,L,_,_,_,_,_,_,_),
s(_,_,_,_,_,_,_,x,x,x,_,x,L,x,_,_,x,x,x,_)).
place(14, L, s(_,_,_,_,_,_,_,_,_,_,_,_,_,L,_,_,_,_,_,_),
s(_,_,_,_,_,_,_,_,x,x,_,_,x,L,_,_,_,x,x,_)).
place(15, L, s(_,_,_,_,_,_,_,_,_,_,_,_,_,_,L,_,_,_,_,_),
s(_,_,_,_,_,_,_,_,_,_,x,x,_,_,L,x,_,_,_,_)).
place(16, L, s(_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,L,_,_,_,_),
s(_,_,_,_,_,_,_,_,_,_,x,x,_,_,x,L,x,_,_,_)).
place(17, L, s(_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,L,_,_,_),
s(_,_,_,_,_,_,_,_,_,_,x,x,x,_,_,x,L,x,_,_)).
place(18, L, s(_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,L,_,_),
s(_,_,_,_,_,_,_,_,_,_,_,x,x,x,_,_,x,L,x,_)).
place(19, L, s(_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,L,_),
s(_,_,_,_,_,_,_,_,_,_,_,_,x,x,_,_,_,x,L,x)).
place(20, L, s(_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,L),
s(_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,x,x,L)).
user:portray(s(A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T)) :-
nl,
format(" ~q~n", [A]),
format(" ~q ~q ~q ~q ~q~n", [B, C, D, E, F]),
format(" ~q ~q ~q ~q~n", [G, H, I, J]),
format(" ~q ~q ~q ~q~n", [K, L, M, N]),
format("~q ~q ~q ~q ~q~n", [O, P, Q, R, S]),
format(" ~q~n", [T]).
--
Ralph....@cl.cam.ac.uk http://www.cl.cam.ac.uk/users/rwab1
Ralph Becket
How odd. My solution (see parent article) comes up with 22084
solutions before permutation of languages and students (multiply by
5!.4! = 2880 to get 63601920). Whereas the first solution offered,
with added comment, gets
> Note, that when you permute the languages [n,g,e,f,s] you
> obtain again a solution. So you have to divide 3584400
> by 5! to obtain the number of solutions modulo
> permutations (= 29870).
So either I am missing some solutions or the first solution is getting
a few more - I suspect the latter since I'm fairly convinced that my
solution avoids rotations and reflections etc. Although even had I
the wit to prove it, I don't have the time.
Cheers,
Ralph
In article <6i55l3$4bt$1...@lyra.csx.cam.ac.uk>,
--
Ralph....@cl.cam.ac.uk http://www.cl.cam.ac.uk/users/rwab1
Robert F. Staerk
In article <6i6r7c$9l$1...@lyra.csx.cam.ac.uk>, rw...@cl.cam.ac.uk (Ralph
Becket) wrote:
> So either I am missing some solutions or the first solution is getting
> a few more - I suspect the latter since I'm fairly convinced that my
> solution avoids rotations and reflections etc. Although even had I
> the wit to prove it, I don't have the time.
I am not so convinced.
> >place( 3, L, s(_,_,L,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_),
> > s(_,x,L,x,_,_,x,x,x,_,_,_,_,_,_,_,_,_,_,_)).
^
Write an 'x' here.
We want:
x
x + x o o
x x x o
o o o o
o o o o o
o
> >place(15, L, s(_,_,_,_,_,_,_,_,_,_,_,_,_,_,L,_,_,_,_,_),
> > s(_,_,_,_,_,_,_,_,_,_,x,x,_,_,L,x,_,_,_,_)).
^
Delete this 'x'.
We want:
o
o o o o o
o o o o
x o o o
+ x o o o
o
Your first typing mistake did not restrict the number of solutions,
because if you had already an 'L' on position no 1 then it `denied'
position no 3.
The second typing mistake, however, restricts the number of solutions.
Position no 15 should not `deny' position no 12.
john garland
Ralph Becket wrote:
> So either I am missing some solutions or the first solution is getting
> a few more - I suspect the latter since I'm fairly convinced that my
> solution avoids rotations and reflections etc. Although even had I
> the wit to prove it, I don't have the time.
>
> Cheers,
>
> Ralph
>
> In article <6i55l3$4bt$1...@lyra.csx.cam.ac.uk>,
> Ralph Becket <rw...@cl.cam.ac.uk> wrote:
> >/**
> >
> >Nutcracker Problem 1
> >Ralph Becket <rw...@cam.sri.com>
> >Tue Apr 28 19:00:47 BST 1998
> >
> >Five languages [n,g,e,f,s].
> >Four students of each language.
> >
> >Desk layout:
> >
> > 1
> > 2 3 4 5 6
> > 7 8 9 10
> > 11 12 13 14
> > 15 16 17 18 19
> > 20
> >
> >No two students of the same language may sit within a king's move
> >of each other.
> >
You probably lack time more than wit :-)
Note that any solution which has students in the 1/2 position can be recreated by
rotating such that the 1/2 position becomes positions 15/16, 19/20, and 5/6
respectively. Therefore, you can keep track of (by adding to a list) the upper left
positions as they occur and disallow subsequent solutions in which these pieces
appear in the other 3 locations. That is, any solution which has students in
positions 15/16, 19/20, or 5/6 which were previously in positions 1/2 is _a solution
which has already been found by the search procedure_. (There are only 5*4 = 20
permutations of the 5 languages taken 2 at a time, so the operation is reasonably
efficient.) You will, of course, notice a severe dropoff in the frequency of
solutions found/unit time as more and more of the 20 permutations are added.
John Garland
nonspammers_remove_this...jgarlnd@ibm.net
Daniel Dudley
Well, there's a lot of big numbers coming up here! Unless I'm seriously
mistaken, there can be no more than 480 solutions.
Let's take Bernhard's denotation of the desks (cells) as our starting point
(view all figures hereunder in a fixed font):
A
BCDEF
GHIJ
KLMN
OPQRS
T
If we view the desks/cells in 4 groups of 5 languages, we get:
North East
----- ----
A
BC DEF
GH IJ
West South
---- -----
KL MN
OPQ RS
T
Each group is essentially alike, only the orientation differs.
Only one of these groups can have all 120 permutations (5!). This is the
start group. All other groups must have less than 120 permutations due to
the king's move restriction. Thus, taking North as our start group, the
total number of solutions must be less than:
(North = 120) + (East < 120) + (South < 120) + (West < 120)
--
Daniel
Daniel Dudley
I had better correct my own errors before someone else does!
GROUP ROTATION
Rotating the start group will give 3 more permutation sets than I original
stated. Whatever result is obtained with North as the start group will
apply equally to East, South and West as start groups. This will give 4 x
(< 480) permutations.
SAME LANGUAGE IN START GROUP
I oversaw the possibility of the same language occuring twice in the same
group. The A-G and A-H 'matches' can occur in the start group, 10
possibilities with 5 languages. Permutation of the remaining 3 desks/cells
with 4 languages (4 x 3!) gives a total of 240 extra permunations in the
start group.
In this case the number of possible permutations in the remaining 3 groups
will be considerably less than 5!, because only 2 of the 'matched' language
in the start group can be shared among them. This will be further reduced
because the language that was omitted in the start group will be available
for sharing 5 times among the remaining 3 groups.
As before, whatever result is obtained here must also be applied to rotated
start groups.
The question remains: does this cover all possibilities?
--
Daniel
Ralph Becket
In article <35476C2E...@ibm.net>, john garland <jga...@ibm.net> wrote:
>
>You probably lack time more than wit :-)
Flattery will get you nowhere!
>Note that any solution which has students in the 1/2 position can be
>recreated by rotating such that the 1/2 position becomes positions
>15/16, 19/20, and 5/6 respectively. Therefore, you can keep track of
>(by adding to a list) the upper left positions as they occur and
>disallow subsequent solutions in which these pieces appear in the
>other 3 locations. That is, any solution which has students in
>positions 15/16, 19/20, or 5/6 which were previously in positions 1/2
>is _a solution which has already been found by the search procedure_.
>(There are only 5*4 = 20 permutations of the 5 languages taken 2 at a
>time, so the operation is reasonably efficient.) You will, of
>course, notice a severe dropoff in the frequency of solutions
>found/unit time as more and more of the 20 permutations are added.
My algorithm is not prone to this problem since it places an order on
the languages and the students within each group: language i must have
its first student in a lower numbered seat than language i+1's first
student. Hence language 1 *must* have its first student in position 1;
language 2 *must* have its first student in position 2; similarly for
language 3. It is only languages 4 and 5 that have some freedom in
the placement of their first students since languages 1 and 2 *may*
put their second student in position 4.
Cheers,
Ralph
--
Ralph....@cl.cam.ac.uk http://www.cl.cam.ac.uk/users/rwab1
Ralph Becket
In article <01bd7394$df45f5a0$fb054382@dudley>,
Daniel Dudley <dud...@online.no> wrote:
>Well, there's a lot of big numbers coming up here! Unless I'm seriously
>mistaken, there can be no more than 480 solutions.
I think you might be:
> (North = 120) + (East < 120) + (South < 120) + (West < 120)
If I have N, E, S, and W possible arrangements for the four quarters,
then the bound on the number of solutions is NESW, not N + E + S + W.
Daniel Dudley
Oops! I can't wean my way out of that one, can I?
But let's not write off the four quarter method, it may yet be the best way
to approach the problem.
--
Daniel