The magazine of the Melbourne PC User Group
Rubik's Cube, Part 1 of 5
 A programming challenge
Ken Holmes

Eriio Rubik was a Hungarian Professor of Engineering who devised this fiendish 'toy' to exercise his students' ability to think in three dimensions; others made a lot of money out of it. My copy has hidden in a drawer for two decades, in the jumbled state it was in a few days after I acquired it. The local library supplied a booklet, "Mastering Rubik's Cube", written (1980) by Don Taylor, then a Senior Lecturer in Pure Mathematics at the University of Sydney, which allowed me to finally see what the cube looked like when first bought.

I invite members interested in dabbling in programming to join in putting The Cube on screen, to be able to experiment with it without getting sore wrists and also to solve it by programming. We will work with QuickBasic or with QBasic; some may wish to use other languages. In this Part 1, we will be content to set up the main module, draw the picture on screen and get the mouse working to select actions. In Part 2, we will deal with conventions for numbering the 6 faces of the cube and the 54 visible faces of the smaller cubes. Also, we will write code for rotating the faces or the whole cube so that it can be `played' to study effects of various combination moves. A quick reset will return it to its pristine state - somewhat easier than with the real thing.


 Figure 1.

In Part 3, we will start to write the code to solve it automatically. The procedure, following Don Taylor's booklet, is lengthy and the code has a lot of repetition, so, if the Editor's patience looks like wearing thin, abbreviated descriptions will be given and you can write the extra bits. Ultimately the whole code will be on the BBS, but I'm sure you will get more fun out of punching in the lot, or as much of it as you can.

QBasic or QuickBasic?

QBasic would be available to most of you since it came with later versions of DOS in the files QBasic.exe and QBasic.hlp. Programs work only in the QBasic environment by interpretation of ASCII text code. QuickBasic is a separate compiler language which can save programs in ASCII or in unreadable, compiled code (fast load and save), and it can make .EXE files to work on their own. Most code is interchangeable between QBasic and QuickBasic but quite different approaches are needed to get mouse operation.

Mouses (or Meeces?)

To read mouse clicks and position, it is necessary to call Interrupt 33Hex, with some number in the ax register and then to read numbers from the bx, cx and dx registers. QBasic has a CALL ABSOLUTE() function which takes the program to an absolute position in memory and any code starting at that address will be executed.

A way to put the code there is to fill an array of integers representing the `machine code' derived from an Assembly Language procedure. On page 44 of PC Update, Dec. 97, Keith Phillips produced a suitable 17 number array and this is used here for those using QBasic. In Listing 1, array a(17) is DIMensioned and the numbers READ into it from the 3 DATA lines. In Listing 3, SUB Mouse(), the ax register is set per a(2) before a CALL ABSOLUTE to the a(1) address; the machine code calls Interrupt 33 and puts the resulting bx, cx and dx registers values into a(15 to 17), whence they may be retrieved. I have included a similar array to restrict the mouse movements to the selection panel; array b(8) is similarly filled from DATA and allows ax, cx and dx registers to be entered per b(2), b(4) and b(6) before calling Interrupt 33. With ax = 7, cx and dx become the limits to horizontal mouse movement and with ax = 8, similarly for the vertical; see Listing 3, MouseLimit().

QuickBasic has a more versatile CALL INTERRUPT(), using a structured variable TYPE, RegType, which can hold all register values. In Listing 1, four commented lines set up for the mouse; the `INCLUDE line (that 2nd apostrophe is not a comment indicator) includes file QB.BI (via its Path), which declares TYPE RegType. Two such structures, inregs and outregs, are DIMed; in SUB Mouse(), ax is set per inregs.ax, then CALL INTERRUPT() puts bx, cx and dx into outregs.bx, outregs.cx and outregs.dx. Also, we can put ax, cx and dx into inregs and CALL INTERRUPT() to limit the mouse movements.

The main module

Listing 1 shows the main module which you can type in as is, substituting the appropriate commented lines if using Quickbasic (and, naturally, omitting the QBasic lines). If are new to this, with each DECLARE SUB line, make a copy, delete the word `DECLARE' and move off the line. The SUB Whatsis() will be created automatically and you will then be able to then type in its contents. You move around the SUBS using the F2 key.

The Rest

Listing 3 includes the SUBs, apart from Grafics() which is in Listing 2. Mouse 3 (or CALL Mouse(3)) returns 2 from bx for a right button click, which sets click = 2 to quit; a left click returns bx = 1, cx = x position and dx = y position. A little arithmetic determines which 56 x 16 block of pixels was clicked, and thereby which face and rotation is desired. Only if you don't use MouseLimit(), do you need the lines " I F f a c > 0 AND. . . " and the next line, and their END IFs, to ignore any clicks outside the panel. Wrong values would abort the program. The SUBS Rotate(), MidLayer() and Solve() just type a message on screen for the moment. SUB Init() initialises the 3 dimensional array c(6, 3, 3) with the colours of the 3 x 3 squares on each of the 6 faces with the colour number = the face number, le. the cube you bought, and this can be regained, at any time by clicking on `RESET'; at the moment, nothing appears to happen since you can't yet mess up the cube.

But you will see whether the program is working properly from the printout of fac and rot in the top left corner. SLL Redraw() colours each square using PAINT, which colours every pixel to the white line boundary. We rotate faces, of rather, the layer of small cubes, by shuffling around the colours of its squares and of the adjacent squares on other faces. SUB PrStr() provides a shorthand way to print a 2, character string starting at column 58 on any line; we will use it on lines 1 to 7 extensively in the auto-solve phase to help us follow what is happening. New strings can print over previous strings at the same position, but sometime we want to blot out a line, and you may note we have created 'blank' for this.

The Picture

Listing 2 is the tedious bit, putting all the lines and text onto the screen, as in Figure 1, but, if you haven't done much graphics programming, it will be useful practice. The VG screen offers any colour background, as long as it is black if you paint the whole screen another colour, any text will print its own black background with ugly results. 

The left-hand view is an external view of front, left and up faces. I have elected for the right-hand view to be an internal view of the further faces; an external view, which might seem more natural, would need constant mental horizontal flipping, which I prefer to avoid. You may note that the cube lines are extravagantly drawn 9 times, giving a triple width line in any direction; the PAINT command paints all pixels within the white boundary of each square and it can jump single lines to escape to flood the whole screen. Text is kept well clear but allowing the mouse to wander over the cubes can cause problems. Each square needs a starting point for PAINT, placed in the x(6, 3, 3) and y(6, 3, 3) arrays. Next month we will write SUB Rotate(), needing for each face, its adjacent faces in anticlockwise order, so these are filled into array f(6, 4) here.

What next?

The coding is voluminous, especially when we get to 'Solve', and every effort is made to curtail it; short algebra variable names assist in this by keeping down the size of the trees so we can see the forest. I hope you get enjoyment out of typing in your own code. In Part 2, we will get it to do something.

Note: This series is continued in PC Update Onlinefor March 2000

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