Session 5: playing with cubes and solving sudoku puzzles

1. Warm-up exercises

What is the answer to the query ?- member(X,[1,2,3,4]). ? What if you ask for all answers (using ";")?

Do the following queries succeed or fail? In case of success, what are the variable bindings?

?- length(List,3).
?- length(List,3), nth_element(1,List,a).
?- length(List,3), nth_element(1,List,a), nth_element(2,List,b), nth_element(3,List,c).

The definitions of length/2 and nth_element/3 are the usual ones:

length([],0).
length([_|T],N) :-
   length(T,N2),
   N is N2+1.

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

2. Stacking cubes

You are given 4 cubes. On each face (side) of each cube, there is a figure. There are 4 different figures in total. The cubes we will use are given, you can find them here.

We will stack these four cubes on top of each other (cube4 on top of cube3 on top of cube2 on top of cube1). Note that for each cube, there are 24 possible orientations (there are 6 possibilities for the bottom, and once we know which is the bottom there are 4 possibilities for the front, and once we knwow the bottom and the front then everything else is fully determined).
We define a stack as 'correct' if the orientations are such that on each side of the stack (front, back, left and right) each figure occurs exactly once. Your task is to write a prolog-program that can find all orientations for the four cubes that yield a correct stack.

There is one small complication: for the second, third and fourth cube you indeed have to consider all 24 orientations, but for the first cube you only need to consider 3 orientations. This is because if you have a correct stack, you can obtain another correct stack by rotating all cubes 90, 180 or 270 degrees, or by turning every cube upside down. But we do not want to consider all these variantions as 'different' solutions. Hence, for the first cube, the only thing that matters is which four sides are visible (front, back, left and right), or in other words which two sides are invisible (bottom and top). This gives only 3 different possibilities for the first cube, instead of 24.

This is not an easy problem, so try to solve it gradually:

Think about alternative high-level strategies to solve the problem. Think about which strategy is most efficient.
This problem is all about cubes, orientations and stacks. Find a good representation in prolog for the 4 given cubes with their figures. Then find a good representation for an orientation of a cube. Then find a good representation for a stack of cubes in certain orientations.
To decide about the representations, think about which actions will have to be performed on the orientations and the stack and which representations will be easiest or most efficient for this.
Write a predicate that takes as input a list of 4 cubes and has as output a correct stack of these cubes. Do this by transforming the high-level strategy you found above into prolog code. Use non-existing predicates for lower level tasks.
Write prolog predicates to solve the lower level tasks.

If you do not understand the problem completely, experiment a bit with the paper cubes first. Once you have a solution it might be interesting to test it later on pc!

3. Solving sudoku puzzles

In this exercise we will write a prolog solver for sudoku puzzles.

A sudoku puzzle is a 9x9 table. In the final solution for the puzzle, each of the 81 cells in the table should contain a (integer) number between 1 and 9, and the following constraints should be satisfied:

no row can contain the same number more than once
no column can contain the same number more than once
no block can contain the same number more than once (a block is one of the nine 3x3 subtables of the big table; see the thick lines in the example below.

In the initial puzzle, some of the numbers in the cells are given. To solve the puzzle, you have to find all the remaining numbers.Now try to write a prolog program that solves such a sudoku puzzle.

Think about alternative high-level strategies to solve the problem. Take into account that the search space is quite large. Suppose that the numbers for 31 cells are given, then 50 numbers are still unknown, which means there are 9^50 possibilities ! Try to find an efficient solution (hint: in generate-and-test programs being efficient usually means testing constraints as soon as you can).
Think about a good representation of (the solution of) a sudoku puzzle.
Write a predicate that has as input the numbers for the known cells and as output a solution (the numbers for all the cells). Do this by transforming your most efficient high-level strategy into prolog code. Use non-existing predicates for lower level tasks.
Write prolog predicates to solve the lower level tasks.
Try to adapt your program so that it can also solve chaos-sudoku puzzles. A chaos-sudoku is a sudoku where instead of square blocks (of size 3x3 as above) we use blocks with arbitrary shapes. Of course, each block still consists of exactly 9 cells. Which cells belong together in a block is usually indicated using colors, see the example below. Before trying to adapt your program, first think about how you will represent these blocks in prolog.