## 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.

• I am giving you a predicate `flipped`:
```% flipped(Click, Columns, Cells)
% Cells is the list of cells that are flipped by a click at index
% Click in a row of the given number of columns.

flipped(Click, Columns, [Left, Click, Right]) :- Click > 1, Click < Columns, Left is Click - 1, Right is Click + 1.
flipped(Click, Columns, [Left, Click]) :- Click > 1, Click = Columns, Left is Click - 1.
flipped(Click, Columns, [Click, Right]) :- Click = 1, Click < Columns, Right is Click + 1.
flipped(Click, Columns, [Click]) :- Columns = 1.

```
• Implement this predicate:
```% doFlips(Cells, Row, Columns, Result)
% Result is a list of red positions resulting from flipping all
% Cells (list of positions) in a Row (list of red positions)
% of the given number of columns.
```
For example, the following are true:
```doFlips([4, 5], [], 5, [3]).
doFlips([1, 2, 4, 5], [4, 5], 5, [4, 5]).
doFlips([1, 2, 3], [1, 2, 4, 5], 5, [1, 5]).
doFlips([2, 3, 4], [1, 2, 3], 5, [2, 5]).
doFlips([1, 3, 4], [2, 3, 4], 5, [1, 2, 3, 4, 5]).
```
Hint: `flipped`, a recursive call to `doFlips`, and `ord_symdiff` (and a fervent hope that you learned in Math 42 what the symmetric difference of two sets is).
• Implement this predicate:
```% allFlips(Flips, Row, Rows, Columns, AllFlips)
% yields in AllFlips a list of lists for flips for each row so that the
% initial set of Flips in the initial Row turns the rectangle
% of the given rows and columns all red.
```
Here is an outline:
```allFlips(Flips, Row, Rows, Columns, [Flips | MoreFlips]) :-
Rows > 0,
doFlips(...),
numlist(1, Columns, All),
ord_symdiff(...),
Rows1 is Rows - 1,
allFlips(...).
allFlips([], _, 0, _, []).
```
Example:
```?- allFlips([4,5],[],5,5,X).
X = [[4, 5], [1, 2, 4, 5], [1, 2, 3], [2, 3, 4], [1, 3, 4]] .```
• Note that the base case makes `allFlips` fail if the initial set of flips doesn't turn the last row completely red. Then add this rule:
`solution(Rows, Columns, Solution) :- numlist(1, Columns, L), sublist(Solution, L), allFlips(Solution, [], Rows, Columns, _).`
Here, `sublist` is from homework 9. When you query
```solution(5, 5, X).
```
you should get the initial click sequence [4, 5] as well as three others. What solution do you get for an 8x8 square? Run your `solution` query and try out the outcome with the puzzle web site.
The web site doesn't support arbitrary rectangles, but try the query with a 6x5 rectangle. You should get a unique starting sequence of [2, 4]. And for an 8x9 rectangle, you should get two starting sequences.
• If you googled, you may well have come across this post. If not, read it and weep. Choosing a good state representation is half the battle.

## 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

% addFront2(S, Ts, Result): Puts all elements of S in front of all
% elements of Ts

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

• A file `puzzle.prolog` with the `doFlips`, `allFlips`, and `solution` predicates.
• A file `cube.prolog` with the `cycles` predicate and any other predicates you used to solve the problem.
• A file `cube.txt` with the answers to the questions that I asked, together with an explanation how you arrived them (including any queries).