How do you program a rubiks cube algorithm?

[S. Karim]

First of all let me start of by saying I can solve a rubiks cube in about 4 different methods and my faster time is 30.01 seconds. Therefore, dont hesitate to use rubiks notation or terminology with me if you feel its necessary.

Second, I have light sensors, line-following sensors (probably can be used to detect shade of color), a camera (which can only detect 3 colors at a time, and the color models can be changed dynamically).

So how do I go about programming a rubiks solving machine? Ive seen a whole bunch online but cant seem to find how they programmed it. The building is no problem, I have tons of motors/servos but I just dont wanna build it until I know I can program it.

Thanks for the help.

[SixRingz]

Hats off to your great solving time!    It takes me about 2-5 minutes to solve one depending on the initial shuffle... 
Well, to build a rubik solver isn't trivial at all. I would be happy just to make the rotations of the cube working with servos and all. But say you have that, you could maybe hook up mirrors or something to get your camera to get view of all sides. Some imaging processing on that to get the color of all the pieces and then "just" apply your favourite rubik method and -presto! your cube solver is done. Not that hard now that I gave you the full solution right?!? 

[S. Karim]

Hats off to your great solving time!    It takes me about 2-5 minutes to solve one depending on the initial shuffle... 
Well, to build a rubik solver isn't trivial at all. I would be happy just to make the rotations of the cube working with servos and all. But say you have that, you could maybe hook up mirrors or something to get your camera to get view of all sides. Some imaging processing on that to get the color of all the pieces and then "just" apply your favourite rubik method and -presto! your cube solver is done. Not that hard now that I gave you the full solution right?!? 

Love the enthusiasm, but its not that simple. Especially if I'm making my own solver from scratch.

Sure, I can process the image and keep numbers to track every corner and edge, but I cant "just" apply my favorite method and presto! To get what I'm talking about, why dont you come up with a specific solution for how to program it in depth and you'll realize how tough it is.

I can keep track of 54 colors, but I have no clue how to tell the robot what colors match what and where they belong .

[pomprocker]

how about the wavefront pathfinding type algorithm using a map?

[S. Karim]

how about the wavefront pathfinding type algorithm using a map?

Could you elaborate?

[Brandon121233]

I have seen a couple videos of rubiks cube solving machines and they all usually spin the cube in every direction first to catalog the orientation of all the colors, from there you wouldnt need any more feedback cause you could use something like this http://www.wrongway.org/cube/solve.html and take the source code from it http://www.wrongway.org/?rubiksource so from there it would just be a matter of breaking that up into executable rotate and twist functions.

[JesseWelling]

I'm imagining a breadth first search as it has been proven that any random Rubiks cube can be solved in 25 moves or less by the time you get to your 26th level of the tree you should have a solution. Assuming this is a 3X3X3 cube:

One move can result in a 'disk' (cross section?) to rotate into 3 new positions.
There are effectively 9 'disks'.
There are 3*9 moves to expand off of every new node.
So for every move made there are 26 new possible moves (Why would you want search a 'undo' and create an infinte cycle.... bleh  )
so that's only 27+26^24 = 9106685769537214956799814036095003 combinations you would have to search to find the optimal solution 

But like my comment before, if you could recognize configurations you have already been and halt the search of that part of the tree there (if you have already been there there was already a shorter path to that point, so if that leads you to a solution, you are already searching that path) I'm sure the number of un-searched limbs will dwindle quickly....

does this make sense to any one else 

[S. Karim]

I'm imagining a breadth first search as it has been proven that any random Rubiks cube can be solved in 25 moves or less by the time you get to your 26th level of the tree you should have a solution. Assuming this is a 3X3X3 cube:

One move can result in a 'disk' (cross section?) to rotate into 3 new positions.
There are effectively 9 'disks'.
There are 3*9 moves to expand off of every new node.
So for every move made there are 26 new possible moves (Why would you want search a 'undo' and create an infinte cycle.... bleh  )
so that's only 27+26^24 = 9106685769537214956799814036095003 combinations you would have to search to find the optimal solution 

But like my comment before, if you could recognize configurations you have already been and halt the search of that part of the tree there (if you have already been there there was already a shorter path to that point, so if that leads you to a solution, you are already searching that path) I'm sure the number of un-searched limbs will dwindle quickly....

does this make sense to any one else 

Makes perfect sense...but I just have no clue how to do that using this program called Interactive C that I'm using to program.

[JesseWelling]

If you are going to do this proper like, you will want to use proper horse power to crunch away at the tree, so you want to program I/O on a MCU and then have your main brain solving on a PC and just send serial commands like turn this, twist that. You can bet your bottom dollar that an MCU doesn't have enough memory to accomplish what I just proposed.

If you are going to program in C I suggest you make a decent structure to hold the 'state' of the cube. Since there could be potentially a lot of these stored values I suggest you use an array of 8 bit unsigned integers like this:

Code: [Select]

#ifndef RUBIK_H
 #define RUBIK_H
 
 typedef struct
 {
    uint8_t cube [3][3][6];
 }RubikCube_T;
 
 typedef enum
 {
    FRONT=0,
    BACK,
    LEFT,
    RIGHT,
    TOP,
    BOTTOM
 }RubikSide_T;

typedef enum
{
    GREEN=0,
    YELLOW,
    BLUE,
    RED,
    WHITE,
    ORANGE // Is that right?
}RubikColor_T;
 #endif
Then you have to go about defining the rules to make a move in a function and come up with a way to portray that movement. Always a good thing to do is to make a function that returns all possible moves, and then weed out the configurations you may have seen before.

[S. Karim]

Very little of that went through my head. I'm not coding with full blown C, but a basic version of it. I have arrays, variables, definitions, functions, etc. The turning functions are easy, I just need something to return a solve algorithm

[Webbot]

Google will give you lots of examples including the 'how to solve the Rubik cube' algorithm. As well as concrete examples - e.g. the Lego Mindstorms Rubik Cube solver.

If you just wish to find how to 'solve' it then there are lots of booklets - probably available from Amazon and the like

[S. Karim]

Google will give you lots of examples including the 'how to solve the Rubik cube' algorithm. As well as concrete examples - e.g. the Lego Mindstorms Rubik Cube solver.

If you just wish to find how to 'solve' it then there are lots of booklets - probably available from Amazon and the like

No no I dont need the algorithm on how to solve, I need the the computer to find an algorithm. I can look at the cube and know what goes where, my problem is telling the processor to figure out how to do that.

[awally88]

Hey,

My made a program which did this. His was only a digital cube rather than an actual mechanical solution but this is how it worked.

He made an array for each face. This could be input directly or had a cool method of inputting turns to randomise it by hand.
He then made general functions to change a selected face backwards or forwards (note L'=3L)
Then the program would solve the cube constrained to the different methods of solving.

There was also a random few turns added in every 100 or so turns to get out of infinate loops which sometimes occurred (hack method but it worked )

If you can get information of each side from camera or colour sensors and then just input it into the array it should work the same way except instead of moving only numbers it would rotated servos as well!

Good luck with the project, it looks like fun!
Awally88

[mklrobo]

Hello! I have a suggestion. (I was on my way to do this myself)
I started to use a method like Awally88.
You can aquire a free "digital" cube solving software on the internet.
Then, the work begins.
I tried to find color sensors, and match them up to the emplacment on the cube.
In parallel, program the digital cube in the software to the same color/state emplacement.
Program the digital cube to step though the solution; in each step, program the robot
to move the real cube accordingly. Thus, the cube will be solved for you, with little or no
headaches involved.
       The trick is, of course, to interface the software. That is where the work will be. Making your
own systems of equations to solve the cube will be a JOB.  I wanted to rent my cube solving robot to
a near circus, for amusement, but no one wanted to entertain the idea. Good luck with your project!

[mklrobo]

I forgot to add that I did find a program that solved it, and put the coordinates in a
file; the positions were listed in the vanacular of the program itself. That would have to
be interpreted and interfaced to the robot.