Simple 2D rubiks cube algorithm.

This is a discussion on Simple 2D rubiks cube algorithm. within the Game Programming forums, part of the General Programming Boards category; I'm trying to write a program that transforms a user given pattern into a standard pattern as follows: Standard: 1 ...

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    7

    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?

    Thanks in advance.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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. #3
    Registered User
    Join Date
    Nov 2008
    Posts
    7
    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. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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. #5
    Registered User
    Join Date
    Nov 2008
    Posts
    7
    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. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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. #7
    Registered User
    Join Date
    Nov 2008
    Posts
    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. #8
    Registered User
    Join Date
    Mar 2008
    Location
    slovenia
    Posts
    25
    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.

  9. #9
    Registered User
    Join Date
    Nov 2008
    Posts
    7
    Sounds interesting, could you please upload/paste the source file?

    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)..
    Last edited by jeanmarc; 11-03-2008 at 01:52 PM.

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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?

    Thanks in advance.
    =================================

    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. #11
    and the Hat of Clumsiness GanglyLamb's Avatar
    Join Date
    Oct 2002
    Location
    between photons and phonons
    Posts
    1,109
    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. #12
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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. #13
    Registered User
    Join Date
    Nov 2008
    Posts
    7
    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. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This is one way:

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

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

    If not make another A move. Record it in board[][][2], 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.

    Please post up what your instructor has to say about this, OK?

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

    Good puzzle!

  15. #15
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This is my start on this brute force solver:

    Code:
    /* Will solve via brute force, the 8 tile 2D "rubik's cube", puzzle
    Adak, Nov. 2008 
    
    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[2][4][20];    //b is shorthand for the board
    int t[1][4];        //t is a temporary holding row
    int line[20];       //the line of moves that are played
    
    int main(void)  {
       int i, r, row, c, col, move, deep, solved, gar;
    // test right shift    
    /* 
       b[0][0][0] = 2; b[0][1][0] = 3; b[0][2][0] = 4; b[0][3][0] = 1;
       b[1][0][0] = 7; b[1][1][0] = 6; b[1][2][0] = 5; b[1][3][0] = 8;
    */
    // test row swap
    /*
       b[0][0][0] = 8; b[0][1][0] = 7; b[0][2][0] = 6; b[0][3][0] = 5;
       b[1][0][0] = 1; b[1][1][0] = 2; b[1][2][0] = 3; b[1][3][0] = 4;
    */
    // test Rotate 4 inner tiles
       b[0][0][0] = 1; b[0][1][0] = 3; b[0][2][0] = 6; b[0][3][0] = 4;
       b[1][0][0] = 8; b[1][1][0] = 2; b[1][2][0] = 7; b[1][3][0] = 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][3][d];
          for(c = 2; c >-1 ; c--)  
             b[r][c+1][d] = b[r][c][d];
          b[r][0][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[0][c] = b[0][c][d];
          b[0][c][d] = b[1][c][d];
          b[1][c][d] = t[0][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[0][1][d];
       b[0][1][d] = b[1][1][d];
       b[1][1][d] = b[1][2][d];
       b[1][2][d] = b[0][2][d];
       b[0][2][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[0][0][d]==1 && b[0][1][d]==2 && b[0][2][d]==3 && b[0][3][d]==4)
          if(b[1][0][d]==8 && b[1][1][d]==7 && b[1][2][d]==6 && b[1][3][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.

    And what did your instructor say about solving this puzzle?
    Last edited by Adak; 11-08-2008 at 12:06 PM.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. simple hashing algorithm??
    By iori in forum C Programming
    Replies: 7
    Last Post: 04-14-2003, 05:18 PM
  2. Debuggin a Simple STL Algorithm :: STL
    By kuphryn in forum C++ Programming
    Replies: 4
    Last Post: 10-25-2002, 10:09 AM
  3. Simple 2D array problem...In a Hurry!
    By 67stangman in forum C++ Programming
    Replies: 8
    Last Post: 04-18-2002, 01:22 PM
  4. a simple algorithm and questions
    By ustuzou in forum C++ Programming
    Replies: 0
    Last Post: 02-18-2002, 10:12 AM
  5. Simple File Creation Algorithm
    By muffin in forum C Programming
    Replies: 13
    Last Post: 08-24-2001, 03:28 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21