Homework 10

Problem 1. Flipping Tiles

Check out this puzzle.

Try to solve the default 5 by 5 puzzle.

Read through the hints for solving it. Convince yourself that it is true that it doesn't matter in which order you click the tiles.

Given that it doesn't matter, we may as well click them top-to-bottom/left-to-right.

Suppose we select the clicks for the first row. Say we click in positions 4 and 5 (where 1 is the first position).

Now move on to the second row. It's now completely clear what you must click. Try it out—click 4 and 5 in the first row, and you see that you must click 1, 2, 4, 5 in the second row. That makes the first row all red, and nothing else will (since we click top-to-bottom).

Move on to the next row. Do you have to click 1, 2, 3?

And the next. Do you have to click 2, 3, 4?

Now click 1, 3, 4 in the final row. Sweet success. All tiles are red.

How did I figure out that clicking 4 and 5 in the first row yields sweet success? Are there any other selections? What if it's not a 5 by 5 array? That's where Prolog comes in.

Problem 2. A Rubik-Like Cube

My kids got this puzzle cube as a gift. Daddy, how do you solve it?

I know how to solve a regular Rubik's cube, using this beginner's method. This time, I wanted to develop a solution myself instead of following someone else's.

The key is to find sequences of rotations that have simple effects.

The cube has eight corners, which I label as follows:

        6-------7
       /|      /|
      2-------3 | 
      | |     | |   y
      | 4-----|-5   | z
      |/      |/    |/
      0-------1     +--x

I label the faces as f r u d l r (front, rear, up, down, left, right).

You can grab each corner of the puzzle cube and twist it 120 degrees (clockwise for the front, counterclockwise for the back). These rotations have the following effects on the corners and faces:

r0 (1 4 2) (d l f)  
r1 (0 3 5) (d f r)  
r2 (0 6 3) (f l u)  
r3 (1 2 7) (f u r)  
r4 (0 6 5) (b d l)  
r5 (1 4 7) (b r d)  
r6 (2 7 4) (b l u)  
r7 (3 5 6) (b u r)  

Here, r0 is the rotation around corner 0. Corner 1 moves to corner 4, corner 4 moves to corner 2, and corner 2 moves to corner 1. Such a permuation is called a cycle. Three faces are also permuted in a cycle. Note that the remaining corners and faces are not permuted.

Applying r0 twice (twisting the corner 240 degrees) is the same as twisting it counterclockwise by 120 degrees. Applying r0 three times is the identity (do-nothing) operation.

Some sequence of rotations r0 ... r7 will restore the cube to order. But which one?

Let's start small. What is the effect of r1 r2 on the corners? In cycle notation, that is (0 3 5)(0 6 3). 0 is sent to 3 and 3 back to 0. That's nice. 3 is sent to 5, where it stays. 5 is sent to 0 and then to 6. 6 is sent to 3. The result is another cycle (3 5 6).

But the product of two cycles isn't always a single cycle. Multiply with r1 again: (3 5 6)(0 3 5) = (0 3)(6 5)

Hopefully you learned in Math 42 that every permutation can be represented as a sequence of cycles.

Computing the outcome of these cycles by hand is tedious. Your first task is to produce a predicate that, given a sequence of cycles, computes their effect, as a normalized sequence of cycles. For example,

cycles([[0,3,5],[0,6,3],[0,5,3],[0,3,6]], X).
X = [[0, 5], [3, 6]]

In the normalized result, each list starts with the smallest element. For example, it's [0, 5] and not [5, 0] (which would be mathematically the same). And the cycles are ordered in the list by that first element: it's [[0, 5], [3, 6]] and not [[3, 6], [0, 5]].

Here are some of the predicates that I used to build up my solution:

% applyCycle(Cycle, A, B)
% The given cycle sends A to B

% applyPerm(Cycles, A, B)
% The given permutation (list of cycles) sends A to B

% orbit(Perm, A, Orbit)
% Repeatedly applying Perm to A sends A to all elements in Orbit

Now that you have this basic tool, it is time to make some queries. Use these facts to label your results:

rotation(r0, [1, 4, 2], [d, l, f]).
rotation(r1, [0, 3, 5], [d, f, r]).
rotation(r2, [0, 6, 3], [f, l, u]).
rotation(r3, [1, 2, 7], [f, u, r]).
rotation(r4, [0, 6, 5], [b, d, l]).
rotation(r5, [1, 4, 7], [b, r, d]).
rotation(r6, [2, 7, 4], [b, l, u]).
rotation(r7, [3, 5, 6], [b, u, r]).

name(R, N) :- rotation(N, R, _).
name(R, N) :- rotation(N, _, R).

This predicate yields all ordered samples with replacement of size N from a given set:

% addFront1(E, Ts, Result): Puts E in front of all elements of Ts
addFront1(_, [], []).
addFront1(E, [T|Ts], [[E|T]|Rs]) :- addFront1(E, Ts, Rs).

% addFront2(S, Ts, Result): Puts all elements of S in front of all
% elements of Ts
addFront2([], _, []).
addFront2([H|T], Ts, Us) :- addFront1(H, Ts, R1), addFront2(T, Ts, R2), append(R1, R2, Us).

picks(_, 0, [[]]).
picks(S, N, R) :- N > 0, N1 is N - 1, picks(S, N1, R1), addFront2(S, R1, R).

Now it's easy to find all sequences of length N that produce a given target permutation:

find(Perms, Target, Pick, N) :- picks(Perms, N, Picks), member(Pick, Picks), cycles(Pick, Target).

Try it out:

findall(X, rotation(_, X, _), VertexRotations), find(VertexRotations, [], S,  4).

Look at a few of these. These sequences keep the vertices unchanged but they still move the faces. This is key. One can first adjust all the vertices (which is pretty easy by hand), and then use vertex-preserving operations such as [r0,r0,r6,r5] to move the faces to the right place. In total, there are 360 possible permutations for the faces. This is the “alternating group” A6 on six letters. To show that you can obtain all these permutations, it suffices to show that you can obtain [b,d,f], [b,d,l], [b,d,r], and [b,d,u]. They generate the entire group. Show how these four permutations can be produced from r0 . . . r7 so that the vertices are left unchanged.

Submission Instructions