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 sorry for not responding earlier. I've a busy weekend so I won't be able to code anything 'til mon-tue. ...

  1. #16
    Registered User
    Join Date
    Nov 2008
    Posts
    7
    I'm sorry for not responding earlier. I've a busy weekend so I won't be able to code anything 'til mon-tue. Anyway, I asked my lecturer and he was very vague regarding the solution, but he said something like:

    Start with a tree and test each depth and go deeper:

    . A....B....C
    . /|\ /|\ /|\
    .ABCABCABC

    etc. (hard to write up but you get the idea).

    Doesn't really add much to our discussion though.

    I might have a solution in mind that I'll try to code up soon. I'll also take a look at your code.

    As for admin moving this thread to the game programming forum, I've no objections if that would keep it on the first page for longer.
    Last edited by jeanmarc; 11-08-2008 at 09:31 AM.

  2. #17
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    OK, I'll ask them to just leave a stub post here, about it, and move the rest to the games forum, on this board.

    That's the search tree, alright!

    I'm not sure what type of search he had in mind, but either way should be OK.

    Did he think the brute force solver was the right way to go for this puzzle, generally?

    Most good puzzles have a certain "key" or trick you can use, leading to some further keys, and finally solve the puzzle.

    Sudoku is one example. It has tons of keys, and some are *extremely* subtle. When I wrote a sudoku solver, the human logic part eventually became too subtle, so now if it can't solve the puzzle via the human logic part of the program, it just uses brute force to finish it off.

    The code example is really just a collection of functions. I haven't coded up much of the search tree yet. I wanted to hear what your instructor said.

    TTYL, probably in the games forum.

  3. #18
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    An update that actually runs.

    Code:
    /* Will solve via brute force, the 8 tile 2D "rubik's cube" puzzle, when finished
    Adak, Nov. 2008 
    
    Status: just started 7/11/08
    */
    
    #include <stdio.h>
    
    void copyB(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, depth, solved, reset, 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;
    */
    // test depth of 2, solution 1 + 2
    /*   b[0][0][0] = 7; b[0][1][0] = 6; b[0][2][0] = 5; b[0][3][0] = 8;
       b[1][0][0] = 2; b[1][1][0] = 3; b[1][2][0] = 4; b[1][3][0] = 1;
    */
    //test depth of 2, solution 2 + 3  no depth=2 solution found for 1+3
       b[0][0][0] = 8; b[0][1][0] = 2; b[0][2][0] = 7; b[0][3][0] = 5;
       b[1][0][0] = 1; b[1][1][0] = 3; b[1][2][0] = 6; b[1][3][0] = 4;
    
    //test depth of , solution 
    /*   b[0][0][0] = ; b[0][1][0] = 2; b[0][2][0] = 1; b[0][3][0] = 4;
       b[1][0][0] = 8; b[1][1][0] = 7; b[1][2][0] = 6; b[1][3][0] = 5;
    */
       printf("\n Starting position:\n");
       showB(0);
       //getch();
       depth = deep = solved = reset = 0;
    
       do  {
          move = 1; depth = 2;
    
            
          while(1)  {   // this is the main loop, for now
             ++deep;
             if(move == 1)
                solved = move1(deep);
             else if(move == 2)
                solved = move2(deep);
             else
                solved = move3(deep);
    
             if(solved) 
                break;
    
             if(reset)  {    //depth was reset, move needs to reset to 1 again
                move = 1;
                reset = 0;
                continue;
             }
    
    
             if(deep >= depth)  {
                line[deep-1] = 0;
                deep = depth - 1;
                if(++move > 3) { 
                   deep -= 1;
                   move = line[deep] + 1;
                   if(move > 1)
                      reset = 1;
                }
             }
          }
    
       }while(!solved);
    
       printf("\n\n\t Press Enter to Quit\n ");
       gar = getchar(); gar++;
       return 0;
    }
    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] = b[r][c][d-1];
    }
    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);
       //showB(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;
       }
       
       showB(d);
       line[d-1] = 1;
       solved = isSolved(d);
       
       return solved;
    }
    int move2(int d)  { //swaps rows
       int r, c, solved;
       solved = 0;
       printf("\n Swap rows:");
       copyB(d);
       //showB(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];
       }
    
       showB(d);
       line[d-1] = 2;
       solved = isSolved(d);
       
       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);
       //showB(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;
    
       showB(d);
       line[d-1] = 3;
       solved = isSolved(d);
       
       return solved;
    }         
    void showB(int d)   {
       int r, c, tab;
       printf("\n");
       for(tab = 0; tab < d; tab++)
          putchar('\t');
       for(r = 0; r < 2; r++) {
          for(c = 0; c < 4; c++)  
             printf(" %d", b[r][c][d]);
          putchar('\n');
          for(tab = 0; tab < d; tab++)
             putchar('\t');
       }
    }
    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("\t Line: ");
             for(i = 0; i < d; i++)
               printf(" %d", line[i]);
    
             //printf("\n\t Press Enter to Continue");
             //gar = getchar(); ++gar;
          }
          
       return done;
    }
    This shows a very basic graphic of the various depths and the moves being made, to a
    depth of 2 ply. The leftmost board being the starting board, and is at depth 0. The next board column to the right is depth 1. Going right one more board width, the boards for depth = 2 are shown (if the search went that far), etc.

    So it's the search tree, with the root on the far left, and the leaves to the right side.

    Code:
    Starting 
    board:
    nnnn
    nnnn
    Description of move 1 at depth 1:
             nnnn
             nnnn
    Description of move 1 at depth 2:
                      nnnn
                      nnnn
    Description of move 2 at depth 2:
                      nnnn
                      nnnn
    Description of move 3 at depth 2:
                      nnnn
                      nnnn
    Description of move 2 at depth 1:
             nnnn
             nnnn
    etc.

    I'm a hobby programmer, so you may very well find something you like better. I'd suggest this as a good starting off point or food for thought, rather than a hard and fast "this is the way it should be done" kind of thing.

    There are several ways to search through a tree, this is just one that felt right (DFS), in this instance, to me.
    Last edited by Adak; 11-09-2008 at 04:45 PM.

  4. #19
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    The above program handles 2 ply searches, but not 3 or more. The part after
    Code:
    if(solved)
       break;
    needs to be adjusted to handle multiple "back ups" in ply. After moves of 1, 3, 3, you need to back up 2 ply, for instance, not just one. That makes your next move 2.

    The program prints the board array now, but even more helpful is getting it to print the line of moves as it goes through it's search.

    If you change the lines array to print < deep right after the if(solved) break, line of code, then you can get a better reference for debugging the DFS.

    The moves should be:
    1
    11
    111
    112
    113
    12
    121
    122
    123
    13
    131
    132
    133
    2
    21
    211
    212
    213
    22
    221
    222
    223
    23
    231
    232
    233

    Which will solve this position:
    b[0][0][0] = 8; b[0][1][0] = 3; b[0][2][0] = 2; b[0][3][0] = 5;
    b[1][0][0] = 1; b[1][1][0] = 6; b[1][2][0] = 7; b[1][3][0] = 4;

    Since this is a student's project, I'm going to refrain from posting any more code on this.

    Original starting position of:

    2684
    1375

    the first solution found for it was: 3 3 1 3 1 1 1

    Here's a laugh for you.

    I thought I'd try an easy puzzle position, something with just one pair of numbers in the wrong position - should be a good way to get started with a new puzzle, right?


    2134
    8765

    Wrong!

    I just couldn't figure the dang thing out, but now my program has. The shortest answer found was 18 ply's deep:


    depth is 18 ply, board is (2134/8765), solution is 231231313131231312


    I still haven't figured out how to solve a lot of these positions by hand. LOL
    Last edited by Adak; 11-10-2008 at 05:36 AM.

  5. #20
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I think this is the best puzzle for figuring out a search, because the selection of moves is so limited, and the depth (number of moves) required for a solution, is not trivial, or the answers obvious.

    This is much easier to learn depth first search from than Tic Tac Toe, for example.

Page 2 of 2 FirstFirst 12
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