Solutions for Session 5

1. Warm-up exercises

?- member(X,[1,2,3,4]).
X = 1 ;
X = 2 ;
X = 3 ;
X = 4 ;
No

```
?- length(List,3).
List = [_G263,_G265,_G267]
Yes 
```
(the letters and numbers behind the underscores might be different on your computer) As you can see, the call length(List,3) generates a list with 3 uninstantiated variables.

?- length(List,3), nth_element(1,List,a).
List = [a,_G281,_G283]
Yes

Now the first element has been instantiated to a.

?- length(List,3), nth_element(1,List,a), nth_element(2,List,b), nth_element(3,List,c). 
List = [a,b,c]
Yes

2. The cube stacking problem

The two most common strategies are:
- the brute force generate-and-test approach: generate a stack of four cubes and then test it, if it is not corrent, generate a new one
- a stepwise approach where we built a correct stack of n cubes and extend it to a correct stack of n+1 cubes (with potential backtracking if this would not be possible) for n=1..3.
We will illustrate both strategies.
- We will represent a cube as a term using the cube/6 functor. Concretely, we represent a cube as a term cube(A,B,C,D,E,F), where A is the figure on face 1, B is the figure on face 2, and so on. For instance, cube C1 is represented as cube(t,s,t,r,t,c) (t stands for traingle, s for star, r for rectangle and c for circle).
- We will represent an orientation as a term o(T,Bo,F,L,Ba,R), where T indicates which face of the cube is at the top, Bo indicates the Bottom, F the front, L the left, Ba the back and R the right. For instance the orientation o(1,5,2,6,4,3) means that face 1 is at the top, face 5 is a the bottom, face 2 is to the front, and so on.
  Note that this representation is redundant since knowing only the top and the front, we can derive all other information. This implies that some terms that might look like an orientation are in reality not valid orientations. For instance o(1,2,3,4,5,6) is not a valid orientation since (given our numbering of faces) if face 1 is at the top, face 5 must be at the bottom. A redundant representation has advantages (usually it allows for fast algorithmns) and disadvantages (it requires more memory and inconsistencies have to be avoided). Of course another (non-redundant) representation is possible as well.
- To represent a stack of cubes in certain orientations, will simply use a list of orientations, for example[o(2,4,1,3,5,6),o(1,5,6,2,3,4),o(1,5,2,3,4,6),o(3,6,4,5,2,1)] (the first element is the orientation of the first cube, and so on).

The brute force solution for the generate and test approach):

generate_and_test([Cube1,Cube2,Cube3,Cube4],[O1,O2,O3,O4]) :-
	% generate a stack with the cubes in some orientation:
	basic_orientation(O1), % 3 possibilities for cube1
	valid_orientation(O2), % 24 possibilities for cube2
	valid_orientation(O3), % 24 possibilities for cube3
	valid_orientation(O4), % 24 possibilities for cube4
	% test the stack:
	test_stack([Cube1,Cube2,Cube3,Cube4],[O1,O2,O3,O4]).

The stepwise approach:

stepwise([Cube1,Cube2,Cube3,Cube4],[O1,O2,O3,O4]) :-
	basic_orientation(O1), % 3 possibilities for cube1
	valid_orientation(O2), % 24 possibilities for cube2
	test_cube_stack(Cube2,O2,[Cube1],[O1]), % test cube2 versus the stack with cube1
	valid_orientation(O3), % cube3
	test_cube_stack(Cube3,O3,[Cube1,Cube2],[O1,O2]),% test cube3 versus the stack with cube1 and cube2
	valid_orientation(O4), % cube4
	test_cube_stack(Cube4,O4,[Cube1,Cube2,Cube3],[O1,O2,O3]). % test cube4 versus the stack with cube1, cube2 and cube3

To make the solution complete, we have to give definitions for the predicates basic_orientation/1, valid_orientation/1, test_stack/2 and test_cube_stack/4:

% 3 basic orientations:
basic_orientation(o(1,5,2,6,4,3)). 
basic_orientation(o(2,4,1,3,5,6)).			  
basic_orientation(o(3,6,1,4,5,2)).

For the first cube in the stack there is only one choice that is important: which four faces are visible (which faces are front, back, left and right), or in other words, which faces are top and bottom. Suppose that faces 1 and 5 are top and bottom or bottom and top. Then it is irrelevant whether 1 is actually top and 5 bottom or the other way around. It is also irrelevant which of faces 2, 3, 4 and 6 are front, back, left and right. So from all the possibilities where 1 and 5 are top and bottom or bottom and top, we can simply choose one possibility as a 'basic orientation' (the choice is not important). The same holds for all possiblities where 2 and 4 are top and bottom or bottom and top and all possiblities where 3 and 6 are top and bottom or bottom and top. So in total, we have only 3 basic orientations.

For the other cubes we do need all valid orientations, 24 in total. We can do this smarter than by simply enumerating the 24 possibilities. From each of the 3 basic orientations, we can derive 8 valid orientations. More precisely, from each basic orientation we can derive 4 valid orientations by turning it horizontally (around the vertical axis) by 0, 90, 180 or 270 degrees and we can derive another 4 valid orientations by first turning it upside down and then again turning it horizontally by 0, 90, 180 or 270 degrees.

% 24 orientations in total:
valid_orientation(O) :- 
	% take a basic orientation ...
	basic_orientation(B),
	% ... and turn it around horizantally 0, 90, 180 or 270 degrees	     
	member(Degrees,[0,90,180,270]), 
	turn_horizontally(B,Degrees,O).

valid_orientation(O) :- 
	% take a basic orientation ...
	basic_orientation(B),
        % ... turn it upside down (switching top and bottom) ...
	turn_upside_down(B,UpsideDown), 
	% ... and turn it around horizantally 0, 90, 180 or 270 degrees
	member(Degrees,[0,90,180,270]), 
	turn_horizontally(UpsideDown,Degrees,O).

The above two clauses each give 12 orientations (3 possibilities for the basic orientation times 4 possibilities for the degrees), so in total we get all 24 valid orientations.

member(X,[X|_]).
member(X,[_|T]) :-
	member(X,T).

turn_upside_down(o(T,Bo,F,L,Ba,R),o(Bo,T,Ba,L,F,R)).
turn_horizontally(o(T,Bo,F,L,Ba,R),0,o(T,Bo,F,L,Ba,R)).
turn_horizontally(o(T,Bo,F,L,Ba,R),90,o(T,Bo,R,F,L,Ba)).
turn_horizontally(o(T,Bo,F,L,Ba,R),180,o(T,Bo,Ba,R,F,L)).
turn_horizontally(o(T,Bo,F,L,Ba,R),270,o(T,Bo,L,Ba,R,F)).

test_stack([],[]).
test_stack([Cube1|Cubes],[O1|O]) :-
	test_cube_stack(Cube1,O1,Cubes,O),
	test_stack(Cubes,O).

test_cube_stack(_,_,[],[]).
test_cube_stack(Cube1,O1,[Cube2|Cubes],[O2|O]) :-
	test_two_cubes(Cube1,O1,Cube2,O2),
	test_cube_stack(Cube1,O1,Cubes,O).

test_two_cubes(C1,O1,C2,O2) :-
        % the front, left, back and right sides should be different 
	test_side(C1,O1,C2,O2,front),
	test_side(C1,O1,C2,O2,left),
	test_side(C1,O1,C2,O2,back),
	test_side(C1,O1,C2,O2,right).

test_side(C1,O1,C2,O2,Side) :-
	get_figure(C1,O1,Side,Fig1),
	get_figure(C2,O2,Side,Fig2),
	not(Fig1=Fig2).

% For a given cube in a given orientation, what is the Figure on a given side:
get_figure(Cube,O,Side,Figure) :-
	get_face(O,Side,FaceNb),
	get_figure_on_face(Cube,FaceNb,Figure).

get_face(o(FaceNb,_,_,_,_,_),top,FaceNb).
get_face(o(_,FaceNb,_,_,_,_),bottom,FaceNb).
get_face(o(_,_,FaceNb,_,_,_),front,FaceNb).
get_face(o(_,_,_,FaceNb,_,_),left,FaceNb).
get_face(o(_,_,_,_,FaceNb,_),back,FaceNb).
get_face(o(_,_,_,_,_,FaceNb),right,FaceNb).

get_figure_on_face(cube(Fig,_,_,_,_,_),1,Fig).
get_figure_on_face(cube(_,Fig,_,_,_,_),2,Fig).
get_figure_on_face(cube(_,_,Fig,_,_,_),3,Fig).
get_figure_on_face(cube(_,_,_,Fig,_,_),4,Fig).
get_figure_on_face(cube(_,_,_,_,Fig,_),5,Fig).
get_figure_on_face(cube(_,_,_,_,_,Fig),6,Fig).

Here are the solutions:

?- generate_and_test([cube(t,s,t,r,t,c),cube(t,r,c,s,r,s),cube(s,c,s,r,c,t),cube(r,s,t,r,c,c)],Solution).
Solution = [o(1, 5, 2, 6, 4, 3), o(6, 3, 5, 4, 1, 2), o(2, 4, 5, 6, 1, 3), o(4, 2, 3, 1, 6, 5)] ;

Solution = [o(2, 4, 1, 3, 5, 6), o(1, 5, 3, 2, 6, 4), o(1, 5, 4, 3, 2, 6), o(6, 3, 2, 5, 4, 1)] ;

Solution = [o(2, 4, 1, 3, 5, 6), o(5, 1, 6, 2, 3, 4), o(5, 1, 2, 3, 4, 6), o(3, 6, 4, 5, 2, 1)] ;

Solution = [o(3, 6, 1, 4, 5, 2), o(2, 4, 6, 1, 3, 5), o(3, 6, 2, 1, 4, 5), o(5, 1, 4, 6, 2, 3)] ;

Solution = [o(3, 6, 1, 4, 5, 2), o(4, 2, 3, 1, 6, 5), o(6, 3, 4, 1, 2, 5), o(1, 5, 2, 6, 4, 3)] ;

No

3. Solving sudoku puzzles

The easiest high-level strategy is to generate a number for each of the 81 cells, test whether these numbers satisfy all constraints and backtrack if necessary. Since the search space is so large, however, this is extremely inefficient.
A more efficient strategy can be obtained by testing constraints sooner. Concretely, this goes as follows. We first fill in all the given numbers. Then we generate a number for the first cell, test whether this number satisfies all constraints and backtrack if necessary. Then generate a number for the second cell, ... and so on, until we have a number for each of the 81 cells. We call this strategy a stepwise generate-and-test approach (since the generate-phase is interleaved with the test-phase).
We will represent a solution as a list of 81 numbers (elements 1 to 9 correspond to the first row, 10 to 18 the second row, ...).

Below is a solution using the stepwise generate-and-test approach.

solve(Given,Solution) :-
	make_empty_solution(Solution,81), % all 81 elements are still uninstantiated
	fill_in_given_values(Given,Solution), % the given elements are now instantiated
	% find the remaining unknown values:
	stepwise_generate_and_test(Solution,1,81), % all 81 elements are now instantiated
	write_solution(Solution,1,9).

Given is a list containing the values already known (e.g. an element 1/4/5 in the list indicates that the value in the cell in row 1 and column 4 is 5). To find a solution we call solve/2 with the first argument instantiated and the second argument uninstantiated.
Note that in the beginning Solution is a list that contains 81 uninstantiated elements (this the result of the call make_empty_solution(Solution,81)). Then we fill in the numbers for the cells that were given (using the call fill_in_given_values(Given,Solution)), this makes some of the 81 elements in Solution instantiated. Then we go through each of the 81 cells one by one, each time generating a number for the cell, testing it and backtracking if necessary (the call stepwise_generate_and_test(Solution,1,81)). At the very end all 81 elements of Solution will be instantiated, and we print out this solution.

Below are the predicates for the three main steps: making an empty solution, filling in the given values and stepwise applying generate-and-test.

make_empty_solution(Solution,Tot) :-
	% create a list with all uninstantiated variables
	length(Solution,Tot).

fill_in_given_values([],_).
fill_in_given_values([Row/Col/Val|Given],Solution) :-
	% instantiate the element at position Row/Col to Val:
	Pos is Col+(Row-1)*9, 
	nth_element(Pos,Solution,Val), % this sets the element at position Pos to the value Val
	fill_in_given_values(Given,Solution).

stepwise_generate_and_test(_,CurrentPos,Tot) :-
	CurrentPos>Tot.
stepwise_generate_and_test(Solution,CurrentPos,Tot) :-
	CurrentPos=<Tot,
	% generate a value for the current position:
	member(Val,[1,2,3,4,5,6,7,8,9]),
	nth_element(CurrentPos,Solution,Val), % match the element at position CurrentPos to Val
	% test this value:
	test_constraint(row,Solution,CurrentPos,Val),
	test_constraint(column,Solution,CurrentPos,Val),
	test_constraint(block,Solution,CurrentPos,Val),
	% if all tests succeed, continue with the next position:
	NextPos is CurrentPos+1,
	stepwise_generate_and_test(Solution,NextPos,Tot).

Here are the predicates for testing the constraints:

test_constraint(Dimension,Solution,CurrentPos,Val) :-
	get_positions_to_test(Dimension,CurrentPos,Positions),
	test_positions(Positions,Solution,CurrentPos,Val).

To test a constraint for a certain dimension (row, column or block), we first find all positions (cells) that are in the same row/column/block as the current position using the call get_positions_to_test(Dimension,CurrentPos,Positions). For instance, if the current position is 12 (this is the cell in row 2 and column 3) and the dimension is row, then Positions is [10,11,12,13,14,15,16,17,18] (i.e. all positions of row 2).

For each of these positions (except the current position itself) we than have to test whether the number at that position is different from the number that we just generated for the current position (Val):

% Test whether the value Val that we just generated didn't already occur somewhere (except at position CurrentPos):
test_positions([],_,_,_).
test_positions([Pos1|Positions],Solution,CurrentPos,Val) :-
	(CurrentPos=Pos1 ->
	    true
	;
	    test_one_position(Pos1,Solution,Val)
	),
	test_positions(Positions,Solution,CurrentPos,Val).

% Test whether the value Val that we just generated didn't already occur at position Pos1:
test_one_position(Pos1,Solution,Val) :- 
	nth_element(Pos1,Solution,Val2), % get the element at position Pos1
	(var(Val2) ->
	    true
	;
	    not(Val2=Val)
        ).

Here are the reamining low-level predicates:

get_positions_to_test(row,Pos,Positions) :-
	row(Positions),
	member(Pos,Positions).

get_positions_to_test(column,Pos,Positions) :-
	column(Positions),
	member(Pos,Positions).

get_positions_to_test(block,Pos,Positions) :-
	block(Positions),
	member(Pos,Positions).

row([1,2,3,4,5,6,7,8,9]).
row([10,11,12,13,14,15,16,17,18]).
row([19,20,21,22,23,24,25,26,27]).
row([28,29,30,31,32,33,34,35,36]).
row([37,38,39,40,41,42,43,44,45]).
row([46,47,48,49,50,51,52,53,54]).
row([55,56,57,58,59,60,61,62,63]).
row([64,65,66,67,68,69,70,71,72]).
row([73,74,75,76,77,78,79,80,81]).

column([1,10,19,28,37,46,55,64,73]).
column([2,11,20,29,38,47,56,65,74]).
column([3,12,21,30,39,48,57,66,75]).
column([4,13,22,31,40,49,58,67,76]).
column([5,14,23,32,41,50,59,68,77]).
column([6,15,24,33,42,51,60,69,78]).
column([7,16,25,34,43,52,61,70,79]).
column([8,17,26,35,44,53,62,71,80]).
column([9,18,27,36,45,54,63,72,81]).

block([1,2,3,10,11,12,19,20,21]).
block([4,5,6,13,14,15,22,23,24]).
block([7,8,9,16,17,18,25,26,27]).
block([28,29,30,37,38,39,46,47,48]).
block([31,32,33,40,41,42,49,50,51]).
block([34,35,36,43,44,45,52,53,54]).
block([55,56,57,64,65,66,73,74,75]).
block([58,59,60,67,68,69,76,77,78]).
block([61,62,63,70,71,72,79,80,81]).

member(X,[X|_]).
member(X,[_|T]) :-
	member(X,T).

nth_element(1,[H|_],H).
nth_element(N,[_|T],E) :-
	N>1,
	N1 is N-1,
	nth_element(N1,T,E).

Finally, here is the predicate for writing the solution (under the form of a table):

write_solution([],_,_) :- nl.
write_solution([H|T],Pos,N) :-
	write(H),
	M is mod(Pos,N),
	(M==0 ->
	    nl  % if Pos is a multiple of N, write a newline 
	;
	    write(' ') % otherwise write a space
	),
	NextPos is Pos+1,
	write_solution(T,NextPos,N).

The sudoku from the example can be solved as follows:

% the known values:
given1([1/4/2, 1/5/3, 1/9/5,
	2/2/4, 2/3/2, 2/5/9, 2/9/3,
	3/1/3, 3/6/8, 3/7/7,
	4/3/7, 4/8/5, 4/9/6,
	5/2/9, 5/4/7, 5/5/2, 5/8/1, 5/9/4,
	6/1/5, 6/4/9, 
	7/1/6, 7/6/2, 7/7/8, 7/8/4, 7/9/9,
	8/3/8, 8/6/1, 8/9/7,
	9/1/2, 9/2/5, 9/6/9, 9/7/6]).

Then we ask prolog the query ?- given1(G),solve(G,S). The answer is:

1 8 9 2 3 7 4 6 5
7 4 2 5 9 6 1 8 3
3 6 5 4 1 8 7 9 2
4 2 7 1 8 3 9 5 6
8 9 6 7 2 5 3 1 4
5 1 3 9 6 4 2 7 8
6 7 1 3 5 2 8 4 9
9 3 8 6 4 1 5 2 7
2 5 4 8 7 9 6 3 1

G = [1/4/2,1/5/3,1/9/5,2/2/4,2/3/2,2/5/9,2/9/3,3/1/3,3/6/8,3/7/7,4/3/7,4/8/5,4/9/6,5/2/9,5/4/7,5/5/2,5/8/1,5/9/4,6/1/5,6/4/9,7/1/6,7/6/2,7/7/8,7/8/4,7/9/9,8/3/8,8/6/1,8/9/7,9/1/2,9/2/5,9/6/9,9/7/6]
S = [1,8,9,2,3,7,4,6,5,7,4,2,5,9,6,1,8,3,3,6,5,4,1,8,7,9,2,4,2,7,1,8,3,9,5,6,8,9,6,7,2,5,3,1,4,5,1,3,9,6,4,2,7,8,6,7,1,3,5,2,8,4,9,9,3,8,6,4,1,5,2,7,2,5,4,8,7,9,6,3,1]
Yes

Computing this answer takes prolog less than a second!

block([1,2,3,4,5,6,7,8,9]). % green
block([10,19,20,28,37,38,46,55,56]). % red
block([11,12,13,14,15,16,22,23,24]). % light-purple
block([17,18,26,27,35,36,45,53,54]). % orange
block([21,29,30,31,39,40,47,48,49]). % yellow
block([25,32,33,34,41,42,50,59,60]). % cyan
block([43,44,51,52,61,62,63,71,72]). % pink
block([57,58,64,65,66,67,73,74,75]). % blue
block([68,69,70,76,77,78,79,80,81]). % dark-purple

given2([1/1/3,1/6/2,1/9/1,
	 2/3/5,
	 3/1/9,3/4/7,3/6/6,3/8/2,
	 4/3/8,4/9/6,
	 5/1/2,5/3/9,5/5/6,5/6/4,
	 6/4/5,6/7/1,6/8/3,
	 7/2/5,7/9/2,
	 8/1/1,8/4/4,8/5/8,8/7/2,8/8/9,
	 9/2/8,9/5/3]).

Then we can ask prolog the query ?- given2(G),solve(G,S).. The anwser is:

3 9 4 6 7 2 5 8 1
6 2 5 8 9 1 3 4 7
9 3 1 7 4 6 8 2 5
4 7 8 2 5 3 9 1 6
2 1 9 3 6 4 7 5 8
7 4 6 5 2 8 1 3 9
8 5 3 9 1 7 4 6 2
1 6 7 4 8 5 2 9 3
5 8 2 1 3 9 6 7 4

G = [1/1/3,1/6/2,1/9/1,2/3/5,3/1/9,3/4/7,3/6/6,3/8/2,4/3/8,4/9/6,5/1/2,5/3/9,5/5/6,5/6/4,6/4/5,6/7/1,6/8/3,7/2/5,7/9/2,8/1/1,8/4/4,8/5/8,8/7/2,8/8/9,9/2/8,9/5/3]
S = [3,9,4,6,7,2,5,8,1,6,2,5,8,9,1,3,4,7,9,3,1,7,4,6,8,2,5,4,7,8,2,5,3,9,1,6,2,1,9,3,6,4,7,5,8,7,4,6,5,2,8,1,3,9,8,5,3,9,1,7,4,6,2,1,6,7,4,8,5,2,9,3,5,8,2,1,3,9,6,7,4]
Yes

On my computer this takes 73 seconds. You can check this with the query ?- time((given2(G),solve(G,S)))..
(time/1 is a built-in predicate that executes a query and prints out the time needed)