The magazine of the Melbourne PC User Group Rubik's Cube - Part 3 of 5 The Automatic Solution Ken Holmes

As promised previously, we will start to write code to put the cube back to its proper state using the strategy outlined in Don Taylor's "Mastering Rubik's Cube". In the SUB Solve(), we have already created the series of empty SUBS in which we will accomplish this.

Dealing with the real cube, we have the advantage of the amazing human brain which, at a glance, can spot cubes out of place and, ignoring those already in place, can (sometimes) plan a quick and expedient rectification of a cube that has not been too vigorously messed up. On the other hand, the computer must follow a completely rigorous procedure, even if it operates on a cube already in proper order. When you click on "Solve", the on-screen arrangement becomes the starting point with, for example, the UP and FRONT faces already chosen, and the following occurs.

Top Edge Cubes

Based on colour, or, more specifically, the numbers in array c(face, i, j), the code looks at all of the edge cubes to find the one which should be at the u/f position, le. the one with the same colours, uc and fc, as the centre squares of the U and F faces. By rotating appropriate faces, it is moved to u/f. The whole cube is rotated 90 deg. clockwise about the U face axis (R face becomes F) and the u/f cube is again correctly positioned. All faces except U may be used but, if any U edge cube (which might have already been corrected) is disturbed, it must be replaced by an opposite move to the offending one. The Rotate/Fix is performed again twice and the four UP edge cubes will be correct - while chaos prevails elsewhere since no attempt is made to avoid disturbing the bottom and middle layers.

Looking at the code in Listing 6, the correct u/f cube could be in any of 12 locations with two possible orientations. We check each of the 23 wrong places it could be and move it with the minimum number of moves to its correct place, as you would with the real cube. We don't need to check the correct place since that is where it is if not found among the wrong ones. We might be tempted to spare the computer from checking all 23 places by bypassing the rest once it is found. One way would be to use GOTO in each IF statement, but, among your programming friends, GOTOs are NONOs; or you could use 24 nested IF..ELSE..END IF statements which would add 48 lines and 24 indenting spaces which could cost me the friendship of the editor. Don Taylor's book suggests moving the found cube to d/f first, then, depending on orientation, moving it to u/f.

In one case the latter is a 180 rotation of the F face but the other involves backing and filling around a lower corner to fix the orientation. Whatever, a number of wasted moves is incurred; and two nested IF statements would be necessary at each of the twelve positions so the number of code lines would not be much less, once the final d/f to u/f move is added. If you study the sequences of moves in the code on a real cube, or on screen, you will start to learn the tricks involved. At this stage, we don't worry what happens to the lower two layers, so the routines are simple. Later, when most of the cubes are sorted, the sequences become more elaborate to avoid upsetting the already correct placements. 

Top Corner Cubes

The correct u/f/r cube might be at any of eight positions with three possible orientations and we must put it in its proper place. Don Taylor suggests moving it first to the d/f/r position, then, depending on orientation, an appropriate set of moves puts it into correct orientation at u/f/r. This breaks the problem in two more understandable pieces but does cause wasteful extra moves. We will use it. In Listing 7, we need three nested IF statements at each of the eight corners to identify our errant cube, ie. the one with colours uc, fc and rc, the centre colours of U, F and R. By using variables i, j and k, the eight sets of three IF statements
are identical, so we only include them for the first case and you may copy them down later as indicated in comments. This saves 32 lines in the magazine, and also saves you a bit of typing.

Next, the information messages are displayed about the planned move to d/f/r; if Pause is ON, you can control each individual rotation and study the process. Even if the corner cube was correct it still makes a trip to d/f/r and back; this wastes moves but avoids a few extra lines of code. 

With the cube at d/f/r, we check where the uc-coloured face is located. If it is on the D face the small cube is given a preliminary twirl to put uc on the R face. We then have two alternative routines depending on whether the uc colour is now on the F or the R face. Three rotations of the whole cube, repeating the above, should see all top corners, as well as the top edges, in proper order as shown in Fig 3. Also, note in the top left corner that it has taken 36 individual face rotations to reach this point. As a matter of interest, a thoroughly disturbed cube needs about 150 such moves to completely sort it and a pristine cube would still register 25 moves. This
latter figure could be reduced to just the whole cube rotations if, at every stage, we checked the correct location and then left it alone if it were OK. But why would we want to bother? You may, however, wish to do this later as an exercise once you have the program fully operational.

Incidentally, you may find that, with Pause ON with a fast computer, the mouse response is too rapid and a lazy mouse click will allow two or more faces to rotate. If so, add a time delay in SUB RotPr() within the IF pause = 1 THEN ... END IF block as follows (in addition to the mouse loop)- tim! = TIMER + .33: DO: LOOP UNTIL TIMER > tim!

Note that this is the same as used in the main module; if you wish, you may change the time delay of .33 (seconds) so that you just have time to release the mouse button before it comes around again.

Where Are We?

If you examine the code for Solve() in Listing 5, Part 2, you will see that the next procedure is Edges2() in which we first invert the whole cube, putting the finished layer on the bottom, and then correct the middle layer edge cubes. This, and more, will occur in next month's Part 4.

Note: Continued in PC Update Onlinefor May 2000

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

[About Melbourne PC User Group]