5
\$\begingroup\$

I wanted to write a c++ program to solve a 3x3 rubik's cube, but failed at it. So I picked up a 2x2 rubik's cube and wrote a program using Blindfold cubing algorithm. Can anyone help me write a more efficient program ? This is the program I wrote

#include<iostream>
#include<string>
using namespace std;
class Solver
{
    string b = "RD' RU' R'U' RU R'F' RU R'U' R'FR DR'      ";
    string c = "F RU' R'U' RU R'F' RU R'U' R'FR F'         ";
    string d = "FU' R'U' RU R'F' RU R'U' R'FR2F'           ";
    string e = "F'D RU' R'U' RU R'F' RU R'U' R'FR D'F      ";
    string f = "F2D RU' R'U' RU R'F' RU R'U' R'FR D'F2     ";
    string g = "RF RU' R'U' RU R'F' RU R'U' R'FR F'R'      ";
    string h = "D RU' R'U' RU R'F' RU R'U' R'FR D'         ";
    string i = "U' R'U' RU R'F' RU R'U' R'FR R             ";
    string j = "R'U' R'U' RU R'F' RU R'U' R'FR R2          ";
    string k = "R2U' R'U' RU R'F' RU R'U' R'F              ";
    string l = "RU' R'U' RU R'F' RU R'U' R'FR              ";
    string n = "D2 RF RU' R'U' RU R'F' RU R'U' R'FR F'R' D2";
    string o = "D'RU' R'U' RU R'F' RU R'U' R'FR D          ";
    string p = "R'F RU' R'U' RU R'F' RU R'U' R'FR F'R      ";
    string r = "F2 RU' R'U' RU R'F' RU R'U' R'FR F2        ";
    string s = "DR F RU' R'U' RU R'F' RU R'U' R'FR F' R'D' ";
    string t = "D2 RU' R'U' RU R'F' RU R'U' R'FR D2        ";
    string u = "F RU' R'U' RU R'F' RU R'U' R'FR F'         ";
    string v = "D'F RU' R'U' RU R'F' RU R'U' R'FR F'D      ";
    string w = "D2F RU' R'U' RU R'F' RU R'U' R'FR F'D2     ";
    string x = "DF RU' R'U' RU R'F' RU R'U' R'FR F'D'      ";
    public:
    string getSol(char letter)
    {
        switch(letter)
        {
            case 'b': return b;
            case 'c': return c;
            case 'd': return d;
            case 'e': return e;
            case 'f': return f;
            case 'g': return g;
            case 'h': return h;
            case 'i': return i;
            case 'j': return j;
            case 'k': return k;
            case 'l': return l;
            case 'n': return n;
            case 'o': return o;
            case 'p': return p;
            case 'r': return r;
            case 's': return s;
            case 't': return t;
            case 'u': return u;
            case 'v': return v;
            case 'w': return w;
            case 'x': return x;
            default: return "Please Enter Correct sequence";
        }
    }
};
int main()
{
    int i = 0;
    char seq[50];
    string solution;
    Solver sol;
    cout<<"-----------------------------------------------"<<endl;
    cout<<"|            Cube Solver 2x2 v1.0             |"<<endl;
    cout<<"|            Developed by Pavan P             |"<<endl;
    cout<<"-----------------------------------------------"<<endl<<endl;
    cout<<"Enter the Sequence in small letters: ";
    cin.clear();
    cin>>seq;
    while(seq[i]!='\0')
    {
        i++;
    }
    cout<<endl;
    cout<<"-----------------------------------------------"<<endl;
    cout<<"|    This may be a solution, try buddy        |"<<endl<<endl;
    for(int j=0;j<i;j++)
    {
        solution = sol.getSol(seq[j]);
        cout<<"| "<<solution<<" |"<<endl;
    }
    cout<<"-----------------------------------------------"<<endl;
    cout<<"Thank You"<<endl;
    cin.get();
        cin.get();
    return 0;
}
\$\endgroup\$
4
\$\begingroup\$

A 2x2x2 Cube has 6 faces each composed of 4 smaller faces (which we can call facelets) for a total of 24 facelets.

However, you do not need to model them all individually as the cube is composed of two 2x2 layers of smaller cubes (cubelets) and the orientation of the facelets is fixed on each cubelet.

The 8 cubelets can be in 8! permutations of positions and 7-of-the-8 cubelets can be independently rotated to any one of 3 orientations (the orientation of the last is dependent on the the orientation of the others) so there are 3^7 different orientations of cubelets. There are 6 ways of picking the top face and then 4 ways of picking the front face so there are 24 different orientations of the cube which have the same permutation and orientation of cubelets - if you fix the orientation of the faces then you can eliminate this factor of 24. So there are:

$$\frac{8!\cdot{}3^7}{24}=3,674,160$$

Possible permutations of the cube.

You can then pick several different approaches:

  1. Brute force - the problem size is not particularly big and you can pack the orientation of the cube into a single 32-bit integer (3,674,160 will fit in 22 bits leaving 10 bits to encode the optimal move towards solving the cube) so with ~14Mb memory you can represent the entire problem. You then just need to enumerate all the different permutations of the cube and then start with the solved cube and perform a breadth-first search of the problem space scrambling it until you have reached all permutations. This will then give you the optimal solution for every cube (but will take a long time to generate the initial result).
  2. Use a depth-first (with a maximum iteration depth) or breadth-first search to solve the cube in small incremental steps. Start by solving a 2x1x1 section of the cube then build on this so a 2x2x1 layer is solved then solve the opposite facelets (ignoring the orientation of the sides) then finally orientate the sides correctly to solve the entire cube. This is likely to generate sub-optimal solutions but it will generate each incremental step fairly quickly.
\$\endgroup\$
3
\$\begingroup\$

Here are some things that may help you improve your code.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Rethink your object design

Right now, the Solver object simply holds two dozen static strings. It has no intelligence and does not, in any sense, know anything about the cube it purports to solve. A better solver might keep a model of the scrambled cube to track its state.

Don't optimize blindly

First, we should keep in mind what Donald Knuth has said about optimization:

"The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming."

Your particular program probably spends 99% of its time doing I/O, so the performance differences among possible alternatives is probably best approximated as zero. If what you're really after is a better algorithm, then that's a different problem.

Don't use std::endl if '\n' will do

Using std::endl emits a \n and flushes the stream. Unless you really need the stream flushed, you can potentially improve the performance of the code by simply emitting '\n' instead of using the potentially more computationally costly std::endl.

Use string concatenation

The code currently includes these lines:

cout<<"-----------------------------------------------"<<endl;
cout<<"|            Cube Solver 2x2 v1.0             |"<<endl;
cout<<"|            Developed by Pavan P             |"<<endl;
cout<<"-----------------------------------------------"<<endl<<endl;
cout<<"Enter the Sequence in small letters: ";

Each of those is a separate call to operator<< but they don't need to be. Another way to write that would be like this:

std::cout <<
    "-----------------------------------------------\n"
    "|            Cube Solver 2x2 v1.0             |\n"
    "|            Developed by Pavan P             |\n"
    "-----------------------------------------------\n"
    "Enter the Sequence in small letters: ";

This reduces the entire sequence to a single call to operator<< because consecutive strings in C++ (and in C, for that matter) are automatically concatenated into a single string by the compiler.

Omit return 0

When a C or C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no need to put return 0; explicitly at the end of main.

Note: when I make this suggestion, it's almost invariably followed by one of two kinds of comments: "I didn't know that." or "That's bad advice!" My rationale is that it's safe and useful to rely on compiler behavior explicitly supported by the standard. For C, since C99; see ISO/IEC 9899:1999 section 5.1.2.2.3:

[...] a return from the initial call to the main function is equivalent to calling the exit function with the value returned by the main function as its argument; reaching the } that terminates the main function returns a value of 0.

For C++, since the first standard in 1998; see ISO/IEC 14882:1998 section 3.6.1:

If control reaches the end of main without encountering a return statement, the effect is that of executing return 0;

All versions of both standards since then (C99 and C++98) have maintained the same idea. We rely on automatically generated member functions in C++, and few people write explicit return; statements at the end of a void function. Reasons against omitting seem to boil down to "it looks weird". If, like me, you're curious about the rationale for the change to the C standard read this question. Also note that in the early 1990s this was considered "sloppy practice" because it was undefined behavior (although widely supported) at the time.

So I advocate omitting it; others disagree (often vehemently!) In any case, if you encounter code that omits it, you'll know that it's explicitly supported by the standard and you'll know what it means.

\$\endgroup\$
  • \$\begingroup\$ Thank you for your help, I'm new to coding and I just wanted to write a program that solves rubik cube. I was looking for better algorithms as most of the manual techniques are difficult to implement in a program as they are intutive. \$\endgroup\$ – Pavan Padubidri Jul 6 '16 at 6:31
  • \$\begingroup\$ Omitting return 0; is bad advice. \$\endgroup\$ – Vinícius Magalhães Horta Jul 17 '17 at 3:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.