<HTML><HEAD><TITLE>CubeSearch</TITLE></HEAD>
<BODY BGCOLOR=d0d0d0 TEXT=800000>
<BIG><BIG><BIG>Title: CubeSearch</BIG></BIG><BR>
Author: David J. Stein, Esq.<BR>
Version: 1.0<BR>
Written: February, 2005</big><BR>
<HR>
<B>Abstract:</B>
This application is a simulation of a classic Rubik's Cube, which the user may manipulate by mouse, keyboard, or the window interface of the simulator. The application also contains a heuristic-based search algorithm to find solutions for the Rubik's Cube from any desired start state, and provides a list of manipulations for solving the cube. The application also features a number of color schemes for recoloring the cube for aesthetic purposes.
<P>
<B>Installation Instructions:</B>
Nothing unusual - simply run the enclosed executable. The included "Help.rtf" file may be accessed within the application for more information.
<P>
<B>Operation Instructions:</B><P>

<i>Basic operation:</i> When you start the program, you will see a 3D representation of the Rubik's Cube at top left, and a 2D layout of each face at top-right. You can work with the cube in two ways:
<UL><LI>You can rotate the entire cube about any axis to see different faces. You can do this by clicking the different "View" buttons at bottom-left. Alternatively, you can use the popular "WASD" keyboard layout: A and D turn the cube left and right; W and S turn the cube up and down; and Q and E rotate the cube clockwise and counterclockwise.
<LI>You can manipulate the cube by rotating a "slice" of the cube along its axis. You can do this by clicking the different "Manipulate" buttons at bottom-center. Alternatively, you can manipulate the cube using the mouse. When you move the mouse over one of the edge tiles on the 3D cube, it becomes highlighted in white; you may hold down the left mouse button and move the mouse to manipulate this slice.</UL>
Finally, the cube may be returned to its start state by clicking the "Reset Cube" button. The cube can also be placed in a random (valid) cube state by clicking the "Randomize" button.<P>

<i>Artificial-intelligence solution finder:</i> This application includes an artificial-intelligence algorithm for finding solutions. Simply click the "Find Solution" button to start searching for a solution. The application will attempt to find a solution by manipulating the cube a great deal, and will display its progress. You may modify the depth of search by using the "Search Method" slider: "quick" searches will finish sooner (but are less likely of finding a solution), whereas "full" searches may take longer but may be more apt to succeed. If the algorithm finds a solution, it will display a list of transformations for solving the cube; you may click through the entries in the list to see the cube at each state in the solution. If the algorithm takes too long to run, you may click "Abort" to stop the process.<P>

<i>Color schemes:</i> I have included a few schemes for recoloring the faces of the cube: Original, Reds, Greens, Blues, Pastels, Earth Tones, Neon, and Greyscale. You can click through the entries on this list to recolor the cube. (This doesn't change the actual state of the cube - it just substitutes one color for another.)
<P>
<B>Comments:</B><P>

The solution finder for this algorithm is far from perfect. It has difficulty finding solutions even a few steps away from the solved cube state, and it is very unlikely to find solutions for more complicated problems.<P>

The problem is that, mathematically, the Rubik's Cube is very complex. Consider the following two facts:
<UL><LI>At every stage, twelve different moves are available. Consequently, the search space simply explodes: even with six transformations, over two million unique states are available.
<LI>Moving from one state to another involves changing the values of 20 different squares. If you've ever played with an actual Rubik's Cube, you know that it's very difficult to calculate a path toward a desired result, because so much changes with every rotation.</UL>
As a result of the above facts, it's very difficult to determine how close you are to solving the cube. Accordingly, it's extremely difficult to develop a good heuristic function for choosing promising solution pathways over unpromising solution pathways. The embedded heuristic function does its best, but it can't do much better than a brute-force search. Note that computer scientists have earned their Ph.D.s by developing cube-solving heuristic functions; I wrote this program over the course of two weeks without relying on anyone else's efforts. So, it's not a good algorithm. The particular heuristic chosen is as follows:<BR>
<UL>Score = 120 - sum(face scores) + number of steps from the starting position.
Face score = 1 point for each matching corner tile and edge tile + 1 point for each matching corner tile and center tile + 2 points for each matching edge tile and center tile.</UL>
Not terribly original, or based on sound mathematics, but it's the best I could do in the circumstances.
<P>
<B>Application History:</B>
This program was written in Spring 2005 as a homework assignment in an artificial intelligence course taught by Dr. Toshinori Munakata at Cleveland State University. The program is solely mine, except for the use of a generic priority queue ("heap") data structure, created by Mr. Ben Di and available via The Code Project. (It's a mystery why Microsoft failed to include such a classic data structure in .NET, but Mr. Di's implementation is very clean and user-friendly.)<P>

Of course, there is no relationship between this application and the actual Rubik's Cube, which is currently owned by Hasbro, Inc. Although Mr. Rubik's patent for the puzzle (Hungarian Patent No. 170,062) expired several years ago, several aspects of the cube are still protected, including the name "Rubik's Cube" and, perhaps, the original color scheme. The intellectual property owners have not granted permission for this work, and no license or business relationship is expressed or implied herein. Use of this product may well violate their intellectual property rights, but it is hoped that such infringement is <i>de minimis</i>, and the author has not been contacted by any owner to date.
<P>
<B>Questions/Comments:</B> Please contact David J. Stein, Esq. via email at <a href="mailto:djs10@po.cwru.edu">djs10@po.cwru.edu</a>.
<P>
<B>Terms and Conditions of Use:</B>
Please see the enclosed "License.html" file for terms and conditions of use of this software package.
<P><HR>
</BODY></HTML>