SINGLE SIDE RUBIK’S CUBE SOLVER

CODE DOCUMENTATION

Kristofer E. delas Peñas

2009-32205
BSCS

1
INTRODUCTION

This document explains in detail the algorithm used in the program to

solve one face of the Rubik’s Cube. It also tabulates register usage and memory
allocations necessary in the program.

DESIGN CONSIDERATIONS

I. ASSUMPTION AND DEPENDENCY

This program is fully dependent on user input. It is assumed
that all inputs would be correct.
II. GOAL
At the end of the program run, a set of moves that would
solve the white face of the Rubik’s cube is to be displayed in the
console. The number of moves to be shown is not necessarily the
minimum as the program is not set for such.

CUBE REPRESENTATION

The Rubik’s Cube is composed of 54 squares. In this program, the

squares would be represented by a unique space in memory, individually.

2
USER-INPUT AND INPUT MAPPING

The user is assumed to input through the console the colors of each
square. The input for a square can only be one of the following:

w for white
b for blue
g for green
y for yellow
r for red
o for orange

Input would be done for each face, in such a way that for each face the
first input would be the top-left corner of the face, followed by the square next
to it, and so on until the bottom-right corner. Visually,

1 2 3

4 5

6 7 8

The center needs not an input because it only represents the cube’s
orientation, and the program is set such that at start, the front center square
would always be white and the top center square would always be red, and so
on.

Inputting of values of the squares of each face would be done in this

sequence,

White side, Red on top

Red side, Yellow on top
Yellow side, Orange on top
Orange side, White on top
Green side, Red on top
Blue side, Orange on top

3
An example of input in the console.

4
MEMORY USAGE AND ALLOCATION

Because each square of the Rubik’s cube is represented individually,

most of the memory utilized is for them. But aside from them, prompt
messages and output messages are also allocated with memory. The next table
tabulates memory usage and explains briefly each label.

Label Description
title *** SINGLE SIDE RUBIK'S CUBE SOLVER ***, title of the
program
one 1, prompt for first input for a face
two 2, prompt for second input for a face
three 3, prompt for third input for a face
four 4, prompt for fourth input for a face
five 5, prompt for fifth input for a face
six 6, prompt for sixth input for a face
seven 7, prompt for seventh input for a face
eight 8, prompt for eighth input for a face
input1 --- White Side, Red on Top ---, prompt for input for white
side
input2 --- Red Side, Yellow on Top ---, prompt for input for red
side
input3 --- Yellow Side, Orange on Top ---, prompt for input for
yellow side
input4 --- Orange Side, White on Top ---, prompt for input for
orange side
input5 --- Green Side, Red on Top ---, prompt for input for green
side
input6 --- Blue Side, Orange on Top ---, prompt for input for blue
side
front memory space for the center front square
front1 memory space for the front1 square
front2 memory space for the front2 square
front3 memory space for the front3 square
front4 memory space for the front4 square
front5 memory space for the front5 square
front6 memory space for the front6 square
front7 memory space for the front7 square
front8 memory space for the front8 square
left memory space for the center left square
left1 memory space for the left1 square
left2 memory space for the left2 square
left3 memory space for the left3 square
left4 memory space for the left4 square
5
 left5 memory space for the left5 square
left6 memory space for the left6 square
left7 memory space for the left7 square
left8 memory space for the left8 square
right memory space for the center right square
right1 memory space for the right1 square
right2 memory space for the right2 square
right3 memory space for the right3 square
right4 memory space for the right4 square
right5 memory space for the right5 square
right6 memory space for the right6 square
right7 memory space for the right7 square
right8 memory space for the right8 square
top memory space for the center top square
top1 memory space for the top1 square
top2 memory space for the top2 square
top3 memory space for the top3 square
top4 memory space for the top4 square
top5 memory space for the top5 square
top6 memory space for the top6 square
top7 memory space for the top7 square
top8 memory space for the top8 square
rear memory space for the center rear square
rear1 memory space for the rear1 square
rear2 memory space for the rear2 square
rear3 memory space for the rear3 square
rear4 memory space for the rear4 square
rear5 memory space for the rear5 square
rear6 memory space for the rear6 square
rear7 memory space for the rear7 square
rear8 memory space for the rear8 square
bottom memory space for the center bottom square
bottom1 memory space for the bottom1 square
bottom2 memory space for the bottom2 square
bottom3 memory space for the bottom3 square
bottom4 memory space for the bottom4 square
bottom5 memory space for the bottom5 square
bottom6 memory space for the bottom6 square
bottom7 memory space for the bottom7 square
bottom8 memory space for the bottom8 square
newline \n, a line break
solution --- SOLUTION ---, marks start of the solution
moveswingtop SWINGTOP, marks a swingtop move done
moveswingdown SWINGDOWN, marks a swingdown move done

6
 moveswingleft SWINGLEFT, marks a swingleft move done
moveswingright SWINGRIGHT, marks a swingright move done
moverotate ROTATE, marks a rotate move done
movefrontleft FRONTLEFT, marks a frontleft move done
movefrontright FRONTRIGHT, marks a frontright move done
movetopright TOPRIGHT, marks a topright move done
movetopleft TOPLEFT, marks a topleft move done
moverightforward RIGHTFORWARD, marks a rightforward move done
moverightbackward RIGHTBACKWARD, marks a rightbackward move done
endofsolution --end of solution--, marks the end of solution
bonussolution --bonus(solve first layer)--, marks start of solving the first
layer

REGISTER AND LABEL USAGE

The next tables show how registers are used in the program, as well as
the different labels that mark up sections of the code.

I. Register Usage

Register Uses
t0 used in loading bytes of the values of the squares of the
cube from and storing bytes to the memory
t1 used in loading bytes of the values of the squares of the
cube from and storing bytes to the memory
t2 used in loading bytes of the values of the squares of the
cube from and storing bytes to the memory
t3 used in loading bytes of the values of the squares of the
cube from and storing bytes to the memory
t4 used in loading bytes of the values of the squares of the
cube from and storing bytes to the memory
t5 used in loading bytes of the values of the squares of the
cube from and storing bytes to the memory
t6 used in loading bytes of the values of the squares of the
cube from and storing bytes to the memory
t7 used in loading bytes of the values of the squares of the
cube from and storing bytes to the memory
t8 used in loading bytes of the values of the squares of the
cube from and storing bytes to the memory
t9 used in loading bytes of the values of the squares of the
cube from and storing bytes to the memory
a0 used in loading the address of strings in memory, as
argument for syscalls
a1 used in specifying the length of string input via console,
7
 as argument for syscalls
v0 used in specifying syscall services
s0 used in loop controls, in counting the number of white
squares
s1 used also in loop controls, in line with s0 for
comparisons
s4 used in loop controls, in counting the number of white
squares in right position
sp used in specifying the position in the stack
ra used in storing the address of the next instruction, for
function calls

II. Labels

Label Description
main signifies start of program
searchedges search for white edges/sides
searchedges1 check if top5 is white
searchedges2 check if rear5 is white
searchedges3 check if top7 is white
searchedges4 check if rear7 is white
searchedges5 check if top2 is white
searchedges6 check if top4 is white
searchedges7 check if rear2 is white
searchedges8 check if rear5 is white
searchloop loop back to searchedges
searchcorners search for white corners
searchcorners1 check if top1 is white
searchcorners2 check if top3 is white
searchcorners3 check if top6 is white
searchcorners4 check if top8 is white
searchcorners5 check if rear1 is white
searchcorners6 check if rear3 is white
searchcorners7 check if rear6 is white
searchcorners8 check if rear8 is white
searchloop2 loop back to searchcorners
bonus solve first layer
arrangecorners place white corners in right position
checkfortwoequal check for two equal squares
setback1 bring to back the two equal squares using topleft move
setback2 bring to back the two equal squares using topright move
stopequal set of moves to arrange corners
arrangesides place white edges/sides in right position

8
 c1 check if front1 is equal to front2
c2 check if right1 is equal to right2
c3 check if rear7 is equal to rear8
c4 check if left7 is equal to left8
endc check if $s4 is equal to zero
checkforopposites1 check if opposites
checkforopposites2 check if opposites, then do topleft move
opposites set of moves to arrange opposite sides/edges in correct
position
checkforadjacents check if adjacents
bringtoback bring to back a complete side of the layer by doing
necessary topleft moves
endbringtoback end topleft moves and proceed to next section
dotopleft do a topleft move
onecompleteside set of moves to arrange/manipulate adjacent
sides/edges
dotopright do a topright move
exit prints the values of the squares for each face and ends
the program

FUNCTIONS – PERSPECTIVE AND ACTUAL MOVES

For this program, there would be defined moves that alter, change or
exchange values of the squares. A function would constitute a certain move,
such that consecutive moves can be easily done through jumps and returns.

I. Perspective Moves
A. Swingtop
In the simplest sense, a swingtop would move the top face to
the front. More specifically, the exchange of values of the squares
is as follows:
top1  front1 rear4  top4
top2  front2 rear5  top5
top3  front3 rear6  top6
top4  front4 rear7  top7
top5  front5 rear8  top8
top6  front6 rear  top
top7  front7 front1  bottom1
top8  front8 front2  bottom2
top  front front3  bottom3
rear1  top1 front4  bottom4
rear2  top2 front5  bottom5
rear3  top3 front6  bottom6

9
 front7  bottom7 left8  left6
front8  bottom8 right1  right6
front  bottom right2  right4
left1  left3 right3  right1
left2  left5 right4  right7
left3  left8 right5  right2
left4  left2 right6  right8
left5  left7 right7  right5
left6  left1 right8  right3
left7  left4

B. Swingdown
A swingdown would move the bottom face to the front. More
specifically, the exchange of values of the squares is as follows:
bottom1  front1 rear5  bottom5
bottom2  front2 rear6  bottom6
bottom3  front3 rear7  bottom7
bottom4  front4 rear8  bottom8
bottom5  front5 rear  bottom
bottom6  front6 left1  left6
bottom7  front7 left2  left4
bottom8  front8 left3  left1
bottom  front left4  left7
front1  top1 left5  left2
front2  top2 left6  left8
front3  top3 left7  left5
front4  top4 left8  left3
front5  top5 right1  right3
front6  top6 right2  right5
front7  top7 right3  right8
front8  top8 right4  right2
front  top right5  right7
rear1  bottom1 right6  right1
rear2  bottom2 right7  right4
rear3  bottom3 right8  right6
rear4  bottom4

C. Swingleft
A swingleft would move the left face to the rear. More
specifically, the exchange of values of the squares is as follows:
left8  rear8 left3  rear3
left7  rear7 left2  rear2
left6  rear6 left1  rear1
left5  rear5 left  rear
left4  rear4 top6  top1

10
 top4  top2 right3  front3
top1  top3 right4  front4
top7  top4 right5  front5
top2  top5 right6  front6
top8  top6 right7  front7
top5  top7 right8  front8
top3  top8 right  front
bottom3  bottom1 rear1  right8
bottom5  bottom2 rear2  right7
bottom8  bottom3 rear3  right6
bottom2  bottom4 rear4  right5
bottom7  bottom5 rear5  right4
bottom1  bottom6 rear6  right3
bottom4  bottom7 rear7  right2
bottom6  bottom8 rear8  right1
right1  front1 rear  right
right2  front2

D. Swingright
A swingright would move the right face to the rear. More
specifically, the exchange of values of the squares is as follows:
left8  front1 bottom1  bottom3
left7  front2 bottom4  bottom2
left6  front3 bottom6  bottom1
left5  front4 right1  rear8
left4  front5 right2  rear7
left3  front6 right3  rear6
left2  front7 right4  rear5
left1  front8 right5  rear4
left  front right6  rear3
top6  top8 right7  rear2
top4  top7 right8  rear1
top1  top6 right  rear
top7  top5 rear1  left1
top2  top4 rear2  left2
top8  top3 rear3  left3
top5  top2 rear4  left4
top3  top1 rear5  left5
bottom3  bottom8 rear6  left6
bottom5  bottom7 rear7  left7
bottom8  bottom6 rear8  left8
bottom2  bottom5 rear  left
bottom7  bottom4

11
 E. Rotate
A rotate would move the right face to the top. More
specifically, the exchange of values of the squares is as follows:
rear1  rear3 left2  bottom4
rear2  rear5 left3  bottom1
rear3  rear8 left4  bottom7
rear4  rear2 left5  bottom2
rear5  rear7 left6  bottom8
rear6  rear1 left7  bottom5
rear7  rear4 left8  bottom3
rear8  rear6 left  bottom
front1  front6 bottom1 right6
front2  front4 bottom2 right4
front3  front1 bottom3 right1
front4  front7 bottom4 right7
front5  front2 bottom5 right2
front6  front8 bottom6 right8
front7  front5 bottom7 right5
front8  front3 bottom8 right3
top1  left6 bottom right
top2  left4 right1 top6
top3  left1 right2 top4
top4  left7 right3 top1
top5  left2 right4 top7
top6  left8 right5 top2
top7  left5 right6 top8
top8  left3 right7 top5
top  left right8 top3
left1  bottom6 right top

II. Actual Moves

A. Topleft B. Topright

12
 A topleft is a quarter turn of the top face in clockwise
direction, while a topright, is a quarter turn of the top face in
counter-clockwise direction.

In terms of exchange of values of the squares,

Topleft Topright
before move after move before move after move
top1 top3 top1 top6
top2 top5 top2 top4
top3 top8 top3 top1
top4 top2 top4 top7
top5 top7 top5 top2
top6 top1 top6 top8
top7 top4 top7 top5
top8 top6 top8 top3
front1 left8 front1 right1
front2 left7 front2 right2
front3 left6 front3 right3
left8 rear8 left8 front1
left7 rear7 left7 front2
left6 rear6 left6 front3
rear8 right1 rear8 left8
rear7 right2 rear7 left7
rear6 right3 rear6 left6
right1 front1 right1 rear8
right2 front2 right2 rear7
right3 front3 right3 rear6

C. Frontright D. Frontleft

13
 A frontleft is a quarter turn of the front face in counter-
clockwise direction, while a frontright, is a quarter turn of the front
face in clockwise direction.

In terms of exchange of values of the squares,

Frontleft Frontright
before move after move before move after move
front1 front6 front1 front3
front2 front4 front2 front5
front3 front1 front3 front8
front4 front7 front4 front2
front5 front2 front5 front7
front6 front8 front6 front1
front7 front5 front7 front4
front8 front3 front8 front6
top6 left1 top6 right1
top7 left4 top7 right4
top8 left6 top8 right6
left1 bottom3 left1 top6
left4 bottom2 left4 top7
left6 bottom1 left6 top8
bottom3 right1 bottom3 left1
bottom2 right4 bottom2 left4
bottom1 right6 bottom1 left6
right1 top6 right1 bottom3
right4 top7 right4 bottom2
right6 top8 right6 bottom1

E. Rightforward F. Rightbackward

14
 A rightforward is a quarter turn of the right face in clockwise
direction(when you are looking at it directly front), while a
rightbackward, is a quarter turn of the right face in counter-clockwise
direction(when you are looking at it directly front).
In terms of exchange of values of the squares,

Rightforward Rightbackward
before move after move before move after move
right1 right3 right1 right6
right2 right5 right2 right4
right3 right8 right3 right1
right4 right2 right4 right7
right5 right7 right5 right2
right6 right1 right6 right8
right7 right4 right7 right5
right8 right6 right8 right3
front3 top3 front3 bottom3
front5 top5 front5 bottom5
front8 top8 front8 bottom8
top3 rear3 top3 front3
top5 rear5 top5 front5
top8 rear8 top8 front8
rear3 bottom3 rear3 top3
rear5 bottom5 rear5 top5
rear8 bottom8 rear8 top8
bottom3 front3 bottom3 rear3
bottom5 front5 bottom5 rear5
bottom8 front8 bottom8 rear8

OTHER FUNCTIONS

I. Ready
The ready function makes sure that until the cross is not yet
complete, at the start of searchedge, the front4 square is vacant(not
white), if it is not vacant, do a necessary number of frontleft moves to
make front4 vacant.

II. Ready2

15
 The ready2 function makes sure that until the corners are not
all white, at the start of searchcorner, the front1 square is vacant(not
white), if it is not vacant, do a necessary number of frontleft moves to
make front1 vacant.

III. Countedge
The countedge function counts the number of white edges in
the front face and stores the number in $s0.

IV. Countcorner
The countcorner function counts the number of white corners
in the front face and stores the number in $s0.

ALGORITHM

The program divides the problem of solving the white face into two – (a)
solve first the white cross/the white edges, then (b) complete the corners.

The goal is to find a white square and do subsequent moves to bring the
square to the front(white face).

a. Solving the edges/cross

First is to find a white square either on the top or the rear face,
doing a linear search like as follows:

top5 rear5 top7 rear7 top2 top4 rear2 rear4

If a white square is found, defined moves would be executed.

top5 rightbackward
rear5 rightforward,rightforward
top7 topright,frontright,rightbackward
rear7 frontleft,topleft,topleft
top2 frontleft,topleft,frontright,rightbackward
top4 frontleft,topleft,topleft,frontright,rightbackward
rear2 swingleft,rightforward,frontleft,frontleft,swingright
rear4 swingleft,rightforward,rightforward,frontleft,frontleft,swingrigh
t

After executing the set of moves, the search would go back to and
test the first element(top5).

16
 If a search ends without finding a white square, a rotate move
would be done and a new search on the new top face would follow.

The search would loop until the cross is complete(i.e. counter $s0
is equal to 4).

The following shows a part of the code for solving the white cross
and explains each line.

searchedge1: #check first element

lbu $t0, top5 #load value of the square

$t0, 119, searchedge2 #check if equal to 119(white). if equal,
proceed, else check next
element
jal ready #make sure front4 is not white
jal rightbackward #do set of moves to bring the square to
front4
addi $s0, $s0, 1 #increment counter
b searchedges #branch back to search(start search
again)

b. Complete the corners

First is to find a white square either on the top or the rear face,
doing a linear search like as follows:

top1 top3 top6 top8 rear1 rear3 rear6 rear8

If a white square is found, defined moves would be executed.

top1 swingleft, topleft, rightforward, topright, swingright

top3 swingleft, rightbackward, topleft, rightforward, rightforward,
topright, swingright
top6 swingleft, topleft, rightforward, topright, rightbackward,
topleft, rightforward, topright, swingright
top8 swingleft, topright, rightbackward, topleft, rightforward,
swingright, swingleft, rightbackward, topleft, rightforward,
rightforward, topright, swingright
rear1 swingleft, swingleft, frontright, rightbackward, frontleft,
rightforward, frontleft, rightbackward, frontright, rightforward,
swingleft, swingleft
rear3 swingleft, swingleft, rightbackward, frontleft, rightforward,

17
 frontleft, rightbackward, frontright, rightforward, swingleft,
swingleft
rear6 swingleft, swingleft, rightbackward, frontleft, frontleft,
rightforward, frontleft, topleft, frontright, frontright, topright,
swingleft, swingleft
rear8 swingleft, swingleft, rightbackward, frontleft, frontleft,
rightforward, frontleft, rightbackward, frontright, rightforward,
swingleft, swingleft
If a search ends without finding a white square, a rotate move
would be done and a new search on the new top face would follow.

The search would loop until all corners are complete(i.e. counter
$s0 is equal to 4).

The following shows a part of the code for solving the corners and
explains each line.

searchcorner1: #check first element

lbu $t0, top1 #load value of the square

bne $t0, 119, searchcorner2 #check if equal to 119(white). if equal,
proceed, else check next element
jal ready2 #make sure front1 is not white
jal swingleft #do set of moves to bring the square to
front4
jal topleft
jal rightforward
jal topright
jal swingright
b searchcorners #branch back to search(start search
again)

CONSOLE OUTPUT

After the program run, the set of moves that solves the white face would
be displayed in the console.

BONUS

After having solved the white face, a section of the code would rearrange
the white face in such a way that each white square would be in correct
position relative to others(i.e. the first layer is solved).

18
 Rearranging the white face is done in two steps – (a) placing corners in
the right position, and (b) placing edges/sides in the right position.

a. Arrange the Corners

First make a swing down move such that the white face would be
on top. Then, start checking corners if they are in correct place. A corner
is/Corners are not in correct place if one of the following is true.

front1 is not equal to front3

right1 is not equal to right3
rear6 is not equal to rear8
left6 is not equal to left8

If none of the conditions is satisfied, rest assured that the corners

are already in the correct position. Else, the following sequence would be
executed.

rightbackward
frontright
rightbackward
swingleft
rightforward
rightforward
frontright
swingright
frontleft
rightbackward
swingleft
rightbackward
rightbackward
frontleft
frontleft
swingright

Before executing the code, make necessary topleft/topright such

that rear6 would be equal to rear8. There would be some cases that no
squares would satisfy this condition. In such cases, the set of moves
above would be executed twice.

b. Arrange the Sides/Edges

19
 Count the number of sides/edges not in right position and store
the number in $s4. Edges are not in the right position if

front1 is not equal to front2

left6 is not equal to left7
rear6 is not equal to rear7
right1 is not equal to right2

Next, check if the edges are opposite to their correct position such
that any of the following is satisfied.

front2 is equal to rear8 and rear7 is equal to front1

right2 is equal to left8 and left7 is equal to right1

If any of the above conditions is satisfied, the following set of

moves would be executed.

rightforward
rightforward
swingright
frontleft
frontleft
topleft
topleft
frontleft
frontleft
swingleft
rightforward
rightforward
If $s4 is equal to 3 or 4, the following is executed.

frontleft
frontleft
topright/topleft
rightbackward
swingright
frontright
rightforward
rightforward
frontleft
swingleft

20
 rightforward
topleft/topright
frontleft
frontleft

If after executing these sets of moves and the first layer is not yet
complete, loop back and check the edges again.

21