A basic, purePython Rubik's cube solver
Project description
Overview
This is a Python 3 implementation of a (3x3) Rubik's Cube solver.
It contains:
 A simple implementation of the cube
 A solver that follows a fixed algorithm
 An unintelligent solution sequence optimizer
 A decent set of test cases
Installation
The package is hosted on PyPI.
pip install rubikcube
Import from the rubik
package,
>>> from rubik.cube import Cube >>> c = Cube("OOOOOOOOOYYYWWWGGGBBBYYYWWWGGGBBBYYYWWWGGGBBBRRRRRRRRR") >>> print(c) OOO OOO OOO YYY WWW GGG BBB YYY WWW GGG BBB YYY WWW GGG BBB RRR RRR RRR
Implementation
Piece
The cornerstone of this implementation is the Piece class. A Piece stores two pieces of information:

An integer
position
vector(x, y, z)
where each component is in {1, 0, 1}:(0, 0, 0)
is the center of the cube the positive xaxis points to the right face
 the positive yaxis points to the up face
 the positive zaxis points to the front face

A
colors
vector(cx, cy, cz)
, giving the color of the sticker along each axis. Null values are place whenever that Piece has less than three sides. For example, a Piece withcolors=('Orange', None, 'Red')
is an edge piece with an'Orange'
sticker facing the xdirection and a'Red'
sticker facing the zdirection. The Piece doesn't know or care which direction along the xaxis the'Orange'
sticker is facing, just that it is facing in the xdirection and not the y or z directions.
Using the combination of position
and color
vectors makes it easy to
identify any Piece by its absolute position or by its unique combination of
colors.
A Piece provides a method Piece.rotate(matrix)
, which accepts a (90 degree)
rotation matrix. A matrixvector multiplication is done to update the Piece's
position
vector. Then we update the colors
vector, by swapping exactly two
entries in the colors
vector:
 For example, a corner Piece has three stickers of different colors. After a
90 degree rotation of the Piece, one sticker remains facing down the same
axis, while the other two stickers swap axes. This corresponds to swapping the
positions of two entries in the Piece’s
colors
vector.  For an edge or face piece, the argument is the same as above, although we may swap around one or more null entries.
Cube
The Cube class is built on top of the Piece class. The Cube stores a list of Pieces and provides nice methods for flipping slices of the cube, as well as methods for querying the current state. (I followed standard Rubik's Cube notation)
Because the Piece class encapsulates all of the rotation logic, implementing
rotations in the Cube class is dead simple  just apply the appropriate
rotation matrix to all Pieces involved in the rotation. An example: To
implement Cube.L()
 a clockwise rotation of the left face  do the
following:
 Construct the appropriate rotation matrix for a 90 degree rotation in the
x = 1
plane.  Select all Pieces satisfying
position.x == 1
.  Apply the rotation matrix to each of these Pieces.
To implement Cube.X()
 a clockwise rotation of the entire cube around the
positive xaxis  just apply a rotation matrix to all Pieces stored in the
Cube.
Solver
The solver implements the algorithm described
here and
here. It is a
layerbylayer solution. First the frontface (the z = 1
plane) is solved,
then the middle layer (z = 0
), and finally the back layer (z = 1
). When
the solver is done, Solver.moves
is a list representing the solution
sequence.
My first correctlooking implementation of the solver average 252.5 moves per solution sequence on 135000 randomlygenerated cubes (with no failures). Implementing a dumb optimizer reduced the average number of moves to 192.7 on 67000 randomlygenerated cubes. The optimizer does the following:
 Eliminate fullcube rotations by "unrotating" the moves (Z U L D Zi becomes L D R)
 Eliminate moves followed by their inverse (R R Ri Ri is gone)
 Replace moves repeated three times with a single turn in the opposite direction (R R R becomes Ri)
The solver is not particularly fast. On my machine (a 4.0 Ghz i7), it takes about 0.06 seconds per solve on CPython, which is roughly 16.7 solves/second. On PyPy, this is reduced to about 0.013 seconds per solve, or about 76 solves/second.
Project details
Release history Release notifications
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Filename, size  File type  Python version  Upload date  Hashes 

Filename, size rubik_cube0.0.1py3noneany.whl (14.1 kB)  File type Wheel  Python version py3  Upload date  Hashes View hashes 
Filename, size rubikcube0.0.1.tar.gz (12.3 kB)  File type Source  Python version None  Upload date  Hashes View hashes 
Hashes for rubik_cube0.0.1py3noneany.whl
Algorithm  Hash digest  

SHA256  3f48973e252e4e4adead580a87d06976419a51c3f502e291736d60a70d0eccbf 

MD5  8abca71ff2f803a9ae74c00c1a4e96ac 

BLAKE2256  addcc978b38e72e94414d2aff27bc18957a936a65ac3362f7ee574f4246360fd 