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.
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.
% 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).% 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]] .
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.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.
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.
puzzle.prolog with the doFlips, allFlips, and solution predicates.cube.prolog with the cycles predicate and any other predicates you used to solve the problem.cube.txt with the answers to the questions that I asked, together with an explanation how you arrived them (including any queries).