# Thread: Simple 2D rubiks cube algorithm.

1. ## Simple 2D rubiks cube algorithm.

I'm trying to write a program that transforms a user given pattern into a standard pattern as follows:

Standard:
1 2 3 4
8 7 6 5

(imagine each number as a different colored square on a board.)

There's three different transform operations that can be made:

A = Switch rows,
B = Rotate each row right one step,
C = Rotate the mid four "squares/numbers" clockwise one step.

So, if the user enters "2 6 8 4 5 7 3 1", the starting position becomes;

2 6 8 4
1 3 7 5

from which the computer program attempts to transform it into the standard form. In this case, the moves required are: BCABCCB.

Now, the issue for me is not to write it in C, but rather to come up with a suitable algorithm for solving the puzzle. I've tried a few methods but they didn't work, so I'm hoping someone could perhaps give me a hint? 2. So Switch Rows would be a full row swap of all digits?

1234
8765

becomes:

8765
1234

correct?

Rotate right from 1234..., would be:

8123
7654

correct?

Can you solve this puzzle by hand, with paper and pencil? Nevermind the algorithm for the computer. Do YOU have an algorithm to solve this puzzle?

If so, post it, and we'll go from there.

We like to do the prodding for students, more than the solving and just giving you the answer. You can't learn anything much from that. 3. I realize I should have clarified the different transformations from the beginning. Anyway:

Start:
1 2 3 4
8 7 6 5

A (switch rows):
8 7 6 5
1 2 3 4

B (move each square right one step):
4 1 2 3
5 8 7 6

C (rotate mid 4 clockwise):
1 7 2 4
8 6 3 5

You're right I should probably try and find an algorithm by pen and paper first. As for helping out with studies, this is actually an optional assignment which carries no extra credit whatsoever, I just found it very interesting and would love to find a solution for it.

Thanks. 4. Well, I'm only batting .333 for the moves, but yeah, paper and pencil. If you don't know how to do it by hand, you have little chance of just sitting down at the computer and getting some muse to come through for ya. I love your spirit - that's just the kind of thing that good solutions feed off of. I don't know the solution myself, but now I've got an idea.  5. My initial thought was to brute force permutations to get the solution, but I don't know if this is really feasible. I mean, if we assume that no more than 10 transformations in a row are needed to solve any given puzzle, this gives 3^10 = 59,049 different combinations of A, B and C to test out. If a solution is found after, say, the 7 first transformations of a given permutation of 10, we break; or something similar. Sounds extremely clumsy though  6. I wouldn't use brute force - much as I like it, generally.

I'd look for some short term goals - steps if you will - leading you closer and closer to the final solution.

That's how the real rubik's cube can be solved, and this is similar, although easier, imo. AFAIK, in the real cube, you have to get certain squares and colors matched up first, (the corners, I believe), then you get the inside top and bottom centers, and last the rest.

I'd try that - corners first maybe, then the interior 4 digits (the one's that can be rotated with C moves).

In the example that you gave, how did you know that the first move should be a "B", or when to make a "C" move? 7. My first example was an example given within the assignment, so I didn't solve it my self (unfortunately). The idea with corners first sounds quite good, and I will definitely try that. Thanks! 8. Hi, I was looking at this example earlier and it just wouldn't leave me alone, so I created a quick program that brute forces it (i know brute force really isn't the "right" way to solve it but it was still fun), it's kinda funny the way it does it, but I must say it does the job. Anyway, I managed to solve a few random puzzles by employing the "corners first"-method, but a few I couldn't solve. Are all puzzles solvable (I assume they are).. 10. I'm trying to write a program that transforms a user given pattern into a standard pattern as follows:

Standard:
1 2 3 4
8 7 6 5

(imagine each number as a different colored square on a board.)

There's three different transform operations that can be made:

A = S = Switch rows,
B = R = Rotate each row right one step,
C = C = Center Rotate (the mid four "squares/numbers" clockwise one step.)

So, if the user enters "2 6 8 4 5 7 3 1", the starting position becomes;

2 6 8 4
1 3 7 5

from which the computer program attempts to transform it into the standard form. In this case, the moves required are: BCABCCB, (or RCSRCCR, in my notation)

Now, the issue for me is not to write it in C, but rather to come up with a suitable algorithm for solving the puzzle. I've tried a few methods but they didn't work, so I'm hoping someone could perhaps give me a hint?

=================================

Code:
```Start:

Apply B   Apply C   Apply A   Apply B   Apply C   Apply C   Apply B
2684  R-> 4268  C-> 4128  S-> 5367  R-> 7536  C-> 7456  C-> 7146  R-> 6714
1375      5137      5367      4128      8412      8132      8352      2835```
Show me where I'm wrong with this, because the example solution you posted, doesn't seem to work. Easy to make an error with this however, and once you do, you're cooked for all the other moves. 11. It would be a great exercise to implement all kind of strategies that ultimately will lead to the one and only solution... like for example tabu search, hill climbing, simmulated annealing etc...

It wont be the fastest since they what I like to call smart brute force algorithms but I would love to see a comparative study on how they perform on this problem.

(I think I'll write this one down in my possible-project-list-for-when-im-bored) 12. This reminds me a little of the old 15 number slide puzzles that were popular back in the 50's and 60's.

I don't remember meeting anyone who could solve it, but it was a solvable puzzle.

After some study with paper and pencil on this, I would opt for the brute force program, also.

I doubt that taking the time to learn the sequences you'd need to know for this, would really be worth the time you'd spend.

I'm generally fond of depth first searches, but with no ability to "score" anything for a "cut out", I'm thinking a breadth first search would be a much better solution.

You've had more time with this now, what do you think? 13. Thanks for your answers. I actually wrote a few randomly picked starting positions and tried to solve them each by pen and paper. I managed to solve most of them (including the one given in my first post, albeit in a different combination but with the same amount of A's B's and C's). A few, however, I couldn't solve, but that might be because I cought a cold the day before and didn't think straight I mean, they should all be solvable, right?

I'm also leaning toward the brute force solution now. I'm not too experienced with that though, but it shouldn't be super difficult. I'm actually gonna ask my lecturer tomorrow if he could give me a hint. I really want to know the algorithm here. 14. This is one way:

Make a 3D array for the board[][][] board is the starting position.

Now make a move, say A, record that change in board[][]and test if it solved the puzzle.

If not make another A move. Record it in board[][], and test it.

Save each move as you go deeper, into the array. At some depth, say 6 moves, you need to say "I'm deep enough for my first pass". Now back up, by referencing board[][][depth - 1],
and make the next move, say B.

At this point you will have tested AAAAAA, exhaustively, to 6 ply.

Now you're "bottom feeding" in a depth first search, at AAAAAB. AAAAAC is the next move.

After the C move is tested, you decrease your depth by 2, and select B as your next move.

I think of it as an upside down tree. The root is up at 0, and the leaf nodes are the leaves of the tree.

This can be done rather slickly with recursive code, but I'd use iterative code for this to avoid the recursive overhead. Might not be as much as I'm thinking, though. In the recursive style of code, the stack frame handles the creation of the boards - it's sort of like a magician pulling a rabbit out of a hat. After you've searched to a depth of 6 ply, you may need to increase your depth and go down to 10. Every increase in depth exponentially increases the number of leaf nodes that need to be checked. That's called "iterative deepening", and is surely beyond what you need to do for this puzzle, but it's interesting - and used a lot in chess and checker programs, where the search tree can be gigantic.

I'll be coding up for this puzzle, also. It looks so simple, but looks are deceiving in this case.

Good puzzle! 15. This is my start on this brute force solver:

Code:
```/* Will solve via brute force, the 8 tile 2D "rubik's cube", puzzle

Status: just started 7/11/08
*/

#include <stdio.h>

void copyB(int);
int leaves(int);
int move1(int);
int move2(int);
int move3(int);

void showB(int);
int isSolved(int);

int b;    //b is shorthand for the board
int t;        //t is a temporary holding row
int line;       //the line of moves that are played

int main(void)  {
int i, r, row, c, col, move, deep, solved, gar;
// test right shift
/*
b = 2; b = 3; b = 4; b = 1;
b = 7; b = 6; b = 5; b = 8;
*/
// test row swap
/*
b = 8; b = 7; b = 6; b = 5;
b = 1; b = 2; b = 3; b = 4;
*/
// test Rotate 4 inner tiles
b = 1; b = 3; b = 6; b = 4;
b = 8; b = 2; b = 7; b = 5;

printf("\n Starting position:\n");
showB(0);
getch();
move = deep = solved = 0;
do  {
move++; //deep++;

for(deep = 1; deep < 11; deep++)  {
//88888888888888  working here 8888888888888
//get next perm here
//decode it and make the move
solved = leaves(deep);

}
for(i = 1; i < 4; i++)  {  //handles the leaf nodes
if(i == 1)
solved = move1(deep);
else if(i == 2)
solved = move2(deep);
else
solved = move3(deep);
if(solved)
break;

}

}while(!solved);

printf("\n\t This program is done ");
gar = getchar(); gar++;
return 0;
}
int leaves(int d)  {
int i, solved;
solved = 0;

for(i = 1; i < 4; i++)  {  //handles the leaf nodes
if(i == 1)
solved = move1(d);
else if(i == 2)
solved = move2(d);
else
solved = move3(d);
if(solved)
break;
}
return solved;
}
void copyB(int d)  {  //copy the old board position, into the new depth
int r, c, temp;

for(r = 0; r < 2; r++)
for(c = 0; c < 4; c++)
b[r][c][d+1] = b[r][c][d];
}
int move1(int d)  {  //shifts all numbers one column to the right &  wraps
int r, c, solved, temp;
solved = 0;
printf("\n Right shift:");
copyB(d);
++d;

for(r = 0; r < 2; r++)  {
temp = b[r][d];
for(c = 2; c >-1 ; c--)
b[r][c+1][d] = b[r][c][d];
b[r][d] = temp;
}

line[d-1] = 1;

solved = isSolved(d);
if(!solved)
line[--d] = 0;

return solved;
}
int move2(int d)  { //swaps rows
int r, c, solved;
solved = 0;
printf("\n Swap rows:");

copyB(d);
++d;

for(c = 0; c < 4; c++)  {
t[c] = b[c][d];
b[c][d] = b[c][d];
b[c][d] = t[c];
}

line[d-1] = 2;
solved = isSolved(d);
if(!solved)
line[--d] = 0;

return solved;
}
int move3(int d) { //turns the 4 inner tiles, clockwise
int r, c, solved, temp;
solved = 0;
printf("\n Rotate 4 inner tiles:");

copyB(d);
++d;

temp = b[d];
b[d] = b[d];
b[d] = b[d];
b[d] = b[d];
b[d] = temp;
line[d-1] = 3;

solved = isSolved(d);
if(!solved)
line[--d] = 0;

return solved;

}
void showB(int d)   {
int r, c;
printf("\n");
for(r = 0; r < 2; r++) {
for(c = 0; c < 4; c++)
printf(" &#37;d", b[r][c][d]);
putchar('\n');
}
}
int isSolved(int d)  {
int i, gar;
int done = 0;
if(b[d]==1 && b[d]==2 && b[d]==3 && b[d]==4)
if(b[d]==8 && b[d]==7 && b[d]==6 && b[d]==5)  {
done = 1;
printf("\n\n\t\t It's solved!");
showB(d);
printf(" line: ");
for(i = 0; i < d; i++)
printf(" %d", line[i]);

//printf("\n\t Press Enter to Continue");
//gar = getchar(); ++gar;
}

return done;
}```
What do you think about asking a mod to move this thread to the game programming forum?

The main C programming forum is very busy, and this is constantly being pushed off the first page, in a single day or two. The game forum (on this same board), is much less busy. Popular pages Recent additions 