The magazine of the Melbourne PC User Group Rubik's Cube - Part 2 of 5 Let's Make It Work Ken Holmes

Have you decided yet to join in? Come on, stop dithering. If you are an expert, you will have your own opinions on how to improve the code, and you must be interested to see the solution of the cube. If you are a dabbler, you will know that other people's programs are an excellent way to get ideas for your own. If you are raw, or even afraid to start, simply copying code into, say, QBasic will strip away the magic and mystery and show that it is just a matter of attention to detail and taking one thing at a time. QBasic will not allow you to move off a line it can't understand and will give an indication of what it doesn't like. To tidy the listings, we have removed a lot of spaces; as you move off a line, it will reinsert them. There is one condition; if your spouse becomes obstreperous about your lack of attention, don't tell her or him that I started you.

So you have laboriously typed in a monstrous heap of code and all it will do is print something on the screen! We need a systematic way to handle those 54 little squares; Figure 2 illustrates a possible way. Apologies for the clunky diagram, but it's about the best you can do with VGA with its text characters placeable only at discrete multiples of eight pixels. SVGA would be better but it isn't supported by QBasic.

The faces are usually referred to as Up, Down, Left, Right, Front and Back or, in a shorthand way, as U, D, L, R, F and B; now you see why Bottom was avoided.

We will number them from 1 to 6 in that order and will work from two `origins', the centre points on each diagram, ie., the U/F/L and the D/B/R corners, with the squares on each face numbered 1 to 3 along both axes from the origin. Looking at a face, from the outside, with the origin at bottom left, the squares will be identified by i=1,2,3 moving out along the normal `x' axis, and by j=1,2,3 moving out along the `y' axis. This determines the contents of the 3-dimensional arrays c(6, 3, 3), x(6, 3, 3) and y(6, 3, 3); these have dimension parameters of (face number, i, j) for storing the value. For example, c(5, 2, 2) would be the colour of the centre square on the F face, and c(1, 2, 1) would be the colour of the U face of the small cube (U/F) at the middle of the common edge of U and F faces. Remember that the right hand picture is a view from the inside, so the handedness of the i/j axes is apparently reversed; thus c(2, 3, 1) would refer to D face of the small cube at the D/R/F corner.
This will be all very confusing at first but is fundamental to writing any code. It is worth drawing a larger diagram, like Figure 2, as in drawing it you will reinforce your understanding and it will be easier to refer to when copying the code. We notice a few things - the edges from each origin are in fact the i axis for one face and the j axis for the other face but the i/j values correspond for adjacent squares - whereas, the other edges (away from the origins) are parallel to both i or to both j axes but the values run oppositely, with "1"s corresponding to "3"s on each side of the edge. Got that? There'll be questions later!

Rotate It

Let us rotate, say, the upper layer. Firstly, the centre square is not going anywhere. In Listing 4, SUB Rotate(), we move (the colours of) four pairs (of a corner square and an edge square) around by a quarter turn by first, saving one pair in temporary variables, then making them equal to the next pair in an anticlockwise direction. Completing the circuit, we use the saved values for the last pair and will see that we have, in effect, rotated the U face 90 deg. clockwise.

We now have to do the same for the three top squares of the side faces and, to this end, we have already, (in Part 1, February PC Update), noted for each face in array f(6, 4) the identities of the adjacent faces in anticlockwise direction. So, a similar process is used to shuffle the four sets of triplets 90 deg. clockwise.

Finally, Redraw() is run to record the rotation on screen. We have been very careful in working relative to the origins, both in filling array f(6, 4) and by the side where we start the shuffle in order to avoid confusion by the differing relationships between i and j at edges. We only need a 90 deg. procedure since it can be used twice for 180 deg. or three times for 270 deg. k1; -90 deg.); the computer doesn't ie. mind a little extra work and it all happens very quickly. Fast computers encourage lazy programmers.

To rotate the whole cube, we need to also rotate the middle layer (clockwise)and the bottom layer (anticlockwise according to its frame of reference). The code in SUB MidLayer() is very similar to the previous shuffle of triplets. In the main procedure we already have the code to identify the opposite face based on the fact that the numbers of different pairs of opposite faces add up to different totals (U+D=3, L+R=7, F+B=11) and it calls up the three rotation procedures, again only for a +90 rotation - but more are just a click away. If this code is typed into the dummy SUBS created in Part 1, you can delete those dumb messages and see some action. You may study the effects of sets of moves and can get symmetrical patterns, if you do systematic sequences, eg. click on 180 for each face in order. Or you may prefer to jumble the cube with several random clicks and then try to solve it - if you are already an expert. If you are not, Reset will remove your embarrassment.

Groundwork For Auto-Solve

There is a conventional shorthand for specifying moves; a 90 deg. rotation uses the face initial, eg. F, and 180 deg. uses F2. A -90 deg. rotation uses F-1 with the -1 usually in superscript as used for `to the power of -1', or the inverse, since it is an inversion of the +90 operation. This is very useful in the solution as there are a number of routine sequences, such as L-1URU-1LUR-1U-1, which need to be remembered. In this form you eventually notice balancing operations crucial to solving it; le. in moving one cube to its correct position you may move several others that may be already correct and it is necessary to repair the damage. In the above sequence, an F undoes an F-1, a R-1 undoes an R and, twice, a U-1 cancels a U, with the order a bit jumbled. Of course, a perfectly anti-symmetrical sequence would simply take you back to the start. For references to the corner and edge cubes in the code (and, in future, in the text) we will use lower case; le. d/f/r refers to the down/front/right corner cube and u/f refers to the up/front edge cube.

Listing 5 sets up a framework for the solution code. The rest of the SUBS are DECLAREd and can be created, ready for code as we develop it, by copying the line, deleting DECLARE and moving off the line. SUB ROtPr() calls up Rotate() and PrStr() to tell us which rotation is about to happen during auto solve - if we have Pause ON and are clicking for each move. With Pause OF it happens too quickly although you may get the overall picture.

For convenience, RotCube() does a 90 deg. rotation of the whole cube about the vertical axis only, which is called frequently during the solution.

Solve() calls the seven procedures and, if you wish to confirm it is happening at this stage with the empty SUBS, you could print the odd screen message, with a DO: LOOP WHILE INKEY$ _ " so you can read it.

In Part 3, we will start the solution with the edge cubes and corner cubes of the top layer. 
Continued in PC Update Online for April 2000

Reprinted from the March 2000 issue of PC Update, the magazine of Melbourne PC User Group, Australia

[About Melbourne PC User Group]