RubiksCube-TwophaseSolver - Python Solution for Near-Optimal Rubik's Cube Solving

RubiksCube-TwophaseSolver Project Overview

This project, called RubiksCube-TwophaseSolver, is a Python implementation of an advanced algorithm known as the two-phase algorithm to solve the Rubik's Cube. Although Python may not be as fast as programming languages like C++ or Java, this implementation is efficient enough to solve randomly scrambled cubes in fewer than 20 moves on average and executes within seconds, even on slower devices like the Raspberry Pi 3.

This solver is ideal for those who wish to explore and understand the inner workings of the two-phase algorithm, possibly for creating a robot that can solve the Rubik's Cube efficiently. However, for those interested in simply solving the Cube or diving into its patterns, other software like Cube Explorer might be more suitable.

Usage

To use this project, you can install it from the Python Package Index (PyPI) with the command:

$ pip install RubikTwoPhase

Afterwards, import the solver module in your Python code:

import twophase.solver as sv

Upon first execution, the program will generate essential tables that require around 80 MB of disk space and can take up to half an hour or more to build, depending on your hardware's capability. These tables enable the algorithm to find very efficient solutions.

Here's an example of how you might define a cube in code and solve it:

cubestring = 'DUUBULDBFRBFRRULLLBRDFFFBLURDBFDFDRFRULBLUFDURRBLBDUDL'
solution = sv.solve(cubestring, 19, 2)

The resulting solution string will resemble the following, representing the sequence of moves:

'L3 U1 B1 R2 F3 L1 F3 U2 L1 U3 B3 U2 B1 L2 F1 U2 R2 L2 B2 (19f)'

Here, the letters U, R, F, D, L, and B stand for Up, Right, Front, Down, Left, and Back faces, respectively, while numbers denote rotations (90°, 180°, or 270°).

You can also specify a constant time for solving with:

sv.solve(cubestring, 0, t)

Additional Features

The tool offers several advanced features:

Performance Testing: Users can test the algorithm's performance by solving multiple random cubes within a specified time.

import twophase.performance as pf
pf.test(100, 0.3)

Custom Goal Patterns: Solve a cube toward a favorite pattern using a goal string.

sv.solveto(cubestring, goalstring, 20, 0.1)

Local Server Operation: Create a server to handle cube solving requests.

import twophase.server as srv
srv.start(8080, 20, 2)

Client GUI: A graphical user interface for entering cube definitions.

import twophase.client_gui

Experimental Computer Vision Module: With OpenCV and a webcam, you can input the cube's facelet colors.

$ pip install opencv-python
$ pip install numpy

import twophase.computer_vision

Performance Metrics

Performance tests conducted on an AMD Ryzen 7 3700X processor reveal that using PyPy (with a Just-in-Time compiler) dramatically speeds up the algorithm by about 10 times compared to standard CPython.

These performance tests are insightful for optimizing solving times and moves. For example, an average solving time of 19 moves can be achieved through specific computational time allocations, such as 10 seconds on CPython or 1 second on PyPy.

Conclusion

RubiksCube-TwophaseSolver is a comprehensive tool for those interested in solving Rubik's Cubes efficiently using modern algorithmic techniques. With its expansive capabilities, from performance testing to computer vision integration, it serves both hobbyists and researchers aiming to build sophisticated cube-solving solutions.