/*
The following is the sourcecode and comments, constituting the second mandatory
assignment in the course DM22, spring 2007, at IMADA, SDU.
This assignment is made entirely of Jacob Aae Mikkelsen (kok04@imada.sdu.dk or
kokken@grydeske.dk)
*/
/*
The objective of this assignment is a prolog implementation of a program that is used for
finding solutions to the puzzle: "Professorspillet".
The implementation must have the following two predicates:
1) profSolution(s)
2) noOfProfSolutions(N)
The predicates has the following tasks:
1) Must answer true if and only if S is a solution to the game.
2) Must answer true only if N is the total number of solutions (including symmetric ones).
*/
/*
The following pseudo code has been supplied as an aid in the implementation:
For each piece in remaining list
For each orientation of the piece
If it fits in position k then
recurse with updated solution and remaining list
A solution is then found if the length of the partial solution reaches 16.
The built-in in predicate 'select' is recommended.
When using the sceme for building a solution from the assignment, we need methods to
check if the piece is legal horisontally, and vertically.
Also needed is a method to take the next element from a list and use this
*/
/*
The main idea in the implementation is:
1) Define the pieces, and make a list of them
2) Define allowed combinations
3) Make machinery that can rotate the pieces
4) Define what constraints there is on each location on the board
- the first piece have no limitations
- The next three must fit horisontally
- The tree on top of the first must fit vertically
- The remaining 9 pieces must fit both horisontally and vertically.
5) Make methods that inserts the pieces in a correct way
*/
/*
1) The pieces in a list
Naming convention for the pieces.
The professors are named: location_color, where location can be t (= top/head) or b (=bottom/legs)
the colors are, from the coats: blue, red, green, purple.
piece(1,0,b_red,b_purple,t_green,t_blue) reads as: the first piece, rotated 0 times 90 degrees, with the specifications
blue legs as the leftmost figure on the piece etc. taken clockwise.
*/
pieces([ piece(1,0,b_red,b_purple,t_green,t_blue),
piece(2,0,b_blue,b_green,t_red,t_purple),
piece(3,0,b_green,b_blue,t_red,t_purple),
piece(4,0,b_green,b_purple,t_blue,t_red),
piece(5,0,b_red,b_blue,t_purple,t_green),
piece(6,0,b_red,b_purple,t_red,t_blue),
piece(7,0,b_red,b_blue,t_green,t_green),
piece(8,0,b_red,b_purple,t_green,t_blue),
piece(9,0,b_green,b_purple,t_red,t_blue),
piece(10,0,b_red,b_green,t_blue,t_purple),
piece(11,0,b_red,b_green,t_green,t_purple),
piece(12,0,b_blue,b_red,t_red,t_blue),
piece(13,0,b_green,b_blue,t_green,t_purple),
piece(14,0,b_green,b_red,t_purple,t_blue),
piece(15,0,b_green,b_green,t_red,t_purple),
piece(16,0,b_red,b_purple,t_green,t_red)
]).
/*
2) Define which combinations are allowed
*/
matches(b_red,t_red).
matches(t_red,b_red).
matches(b_green,t_green).
matches(t_green,b_green).
matches(b_purple,t_purple).
matches(t_purple,b_purple).
matches(b_blue,t_blue).
matches(t_blue,b_blue).
/*
Define the rotation of the pieces
*/
rotate0(X,Y):- Y = X.
rotate1(piece(N,_,A,B,C,D),piece(N,1,D,A,B,C)).
rotate2(piece(N,_,A,B,C,D),piece(N,2,C,D,A,B)).
rotate3(piece(N,_,A,B,C,D),piece(N,3,B,C,D,A)).
/*
Does these two bricks fit, left to right
*/
fit_horisontally(X,Y) :- X = piece(_,_,_,_,C,_), Y = piece(_,_,A,_,_,_) , matches(C,A).
/*
Does these two bricks fit, bottom to top
*/
fit_vertically(X,Y) :- X = piece(_,_,_,_,_,D), Y = piece(_,_,_,B,_,_) , matches(B,D).
/*
Get the brick 4 positions back in he list = brick below current brick
*/
get_brick_below(X,[_,_,_,Y|_]):- X = Y.
/*
The add_piece methods are for extending the solution,
R = Remaining, P=Partial solution, NR = NewRemaining
An observation, looking at the square figure in the assignment is,
that the brick at position 0 doesn't have any constraints at all,
piece 1,2,3 must fit with the piece to the right when inserted,
pieces 4,8,12 must fit to the piece below only, and the remaining pieces
must all fit with the piece below and to the right.
Therefore the add_piece method is split into several cases.
*/
/* The first piece, no constraints at all */
add_piece(0,R,_) :-
N1 is 1,
select(Brick,R,RN),
(rotate0(Brick,B);rotate1(Brick,B);rotate2(Brick,B);rotate3(Brick,B)),
add_piece(N1, RN , [B]).
/*Pieces 1,2,3 */
add_piece(N,R,[H|P]) :-
(N = 1; N = 2; N = 3),
N1 is N + 1,
select(Brick,R,NR),
(rotate0(Brick,B);rotate1(Brick,B);rotate2(Brick,B);rotate3(Brick,B)),
fit_horisontally(B,H),
add_piece(N1,NR,[B,H|P]).
/* Pieces 4,8,12 */
add_piece(N,R,P) :-
(N = 4; N = 8; N = 12),
N1 is N + 1,
select(Brick,R,NR),
(rotate0(Brick,B);rotate1(Brick,B);rotate2(Brick,B);rotate3(Brick,B)),
get_brick_below(U,P),
fit_vertically(B,U),
add_piece(N1,NR,[B|P]).
/* The rest of the pieces */
add_piece(N,R,[H|P]) :-
(N = 5; N = 6; N = 7;N = 9; N = 10; N = 11;N = 13; N = 14; N = 15),
N1 is N + 1,
select(Brick,R,NR),
(rotate0(Brick,B);rotate1(Brick,B);rotate2(Brick,B);rotate3(Brick,B)),
get_brick_below(U,[H|P]),
fit_vertically(B,U),
fit_horisontally(B,H),
add_piece(N1,NR,[B,H|P]).
/*
The solution must be complete, since 15 pieces allready has been placed.
Change the line below, if the solutions should be printed
*/
/* add_piece(16,R,P):- write(P).*/
add_piece(16,R,P).
/*
Generates a list of all possible solutions
*/
all_solutions(X,L):- findall(Y,add_piece(0,X,Y),L), write(L).
/*
Checks if a piece is in the list (Found member from the buildt in methods later),
But... when it ain't broken - don't fix it :)
*/
is_in(_,[]) :- fail.
is_in(S,[H|_]) :- S = H, !.
is_in(S,[_|T]) :- is_in(S,T).
/*
Here the two required predicates, using the above machinery.
*/
profSolution(S) :- pieces(X), all_solutions(X,A), is_in(S,A).
noOfProfSolutions(N) :- pieces(X), all_solutions(X,A), length(A,M), N = M.
/*
Note: piece 1 and 8 is identical => each solution is the same as another one.
Note, this implementation is not supposed to eliminate symmetric solutions, so it is clear,
that the total number of solutions must be a multiple of four. Reason: Any solution can be rotated
90, 180, and 270 degrees, making four solutions.
If the puzzle were to be solved without rotations of the entire puzzle, this could be solved
just by putting a constraint on one of the pieces, saying that piece isn't allowed to rotate.
With this in mind, we can divide the 184 solutions by 8, making 23 distinct solutions.
Testprint of all the solutions, can be seen in the file 184_solutions.txt.
Extra lines has been added for readability.
The first of those has been tested in real life.
*/