Thread: Rubix Cube Contest

  1. #1
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903

    Rubix Cube Contest

    The concept is simple. Write a program that will solve a rubix cube. You will need to determine the minimum input you will need from the user to solve any given rubix cube (i.e. entering 1, 2, 3 etc. side(s) of the cube) After the user has entered their current cube configuration, you will need to provide a step by step process to solve the cube in the least amount of moves.

    Programs must be written in c++

    Stickers cannot be removed/re-attached

    Programs will be graded on the following criteria:

    • Speed
    • Accuracy
    • Least Amount of code
    • Least amount of moves
    • Least Amount of user prompted input



    Contest Deadline: Have entries submitted to me via board pm/email by New Years Day.. 2005
    Last edited by The Brain; 11-25-2004 at 06:21 AM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  2. #2
    Nice contest,

    I have a question though. Does the rubik cube initialize itself with a random scramble method once the user entered the dimensions, i.e. 2x2x2 / 3x3x3?

    Overall, I may enter the contest, though I'm not making any promises. If I make a definite decision, I will be sure to announce it.


    - Stack Overflow
    Segmentation Fault: I am an error in which a running program attempts to access memory not allocated to it and core dumps with a segmentation violation error. This is often caused by improper usage of pointers, attempts to access a non-existent or read-only physical memory address, re-use of memory if freed within the same scope, de-referencing a null pointer, or (in C) inadvertently using a non-pointer variable as a pointer.

  3. #3
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    The user should be able to enter any configuration of a cube.. and your program should be able to solve the cube.

    Use a regular 3x3x3 standard rubix cube.. i think it is possible to come up with an algorithm that can at least solve any given cube in at least under 100 moves.

    In grading this contest.. I am going to use a real life rubix cube (which is already randomly configured) and grade each entry based on the number of moves the programs recommend for solving the cube. I'll use at least 5 different random configurations from a real life cube in order to establish a grade for each program.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  4. #4
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    On the cube that you have, what are the colour pairs? Some cubes are different. The ones which I have are B-W, R-O, Y-G. (By colour pairs I men opposite sides of the cube)
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  5. #5
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    I'm in if I have enough time

  6. #6
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Wow, I looked into writing an algorithm like this awhile back for a rubiks cube program I wrote, but gave up when I found out the number of factors involved. Maybe I'll give it a try again.

  7. #7
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    Quote Originally Posted by PJYelton
    Wow, I looked into writing an algorithm like this awhile back for a rubiks cube program I wrote, but gave up when I found out the number of factors involved. Maybe I'll give it a try again.
    yeah I also did something similar. It is a rather tough contest IMO, esspecially for an NxNxN cube.

    Plus, how will you judge this? You said you will use a random starting configuration...will this configuration be the same for all the programs? it should be, as some configurations are solved easier than others.

    What format would you like the positions to be indicated in? where would position 0,0,0 be?

    Overall, I think you should work out the details more and repost.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  8. #8
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    On the cube that you have, what are the colour pairs? Some cubes are different. The ones which I have are B-W, R-O, Y-G. (By colour pairs I men opposite sides of the cube)
    This is also the cube that I have.. so this would work out well. Programs should be written to handle this color scheme.


    Plus, how will you judge this? You said you will use a random starting configuration...will this configuration be the same for all the programs? it should be, as some configurations are solved easier than others.
    Of course... each program will be tested using the same 5 random configurations.


    What format would you like the positions to be indicated in? where would position 0,0,0 be?
    This is up to the programmers discretion.


    Overall, I think you should work out the details more and repost.
    If there are any further questions.. please post them in here.
    Last edited by The Brain; 11-26-2004 at 07:25 AM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    How are you going to input the problem to solve? The judging is going to be rather tricky, since you should, to be fair, give the same input for each solution to see how each fairs under identical situations.

    Quzah.
    Hope is the first step on the road to disappointment.

  10. #10
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    I had implemented a solution to Rubik's cube previously using OpenGL and Dev-C++ several years ago as my first, and only venture, into 3D gaming. The solution algorithm is not my own, but one I found online. The algorithm source is acknowledged. The files seem intact, though I haven't retested the program extensively. It averages 100-150 twists per solution, so it isn't the most efficient algorhithm available, and the code doesn't have a chance in the shortest code category either (2135 lines as is), but I'd be happy to send the code to you if you tell me how--
    a) paste and copy code in an email
    b) send file as attachment to an email (which files would you want?)
    c) whatever.

    The code can generate it's own random cube and solve it from the original random position, or from wherever user stops and request the program to solve it from there. Once the puzzle is solved you can view an animated solution or you can step through the solution one twist at a time. It keeps track of the number of twists and displays that value.

    Alternatively, if you don't generate a random cube you can just play with the cube without seeking a solution.

  11. #11
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    How are you going to input the problem to solve?
    Good Question. This is how I would do it:

    I would display an ascii graph of what a rubix cube would look like when unfolded. It would resemble a cross:

    Code:
                                     [  ][  ][  ]
                                     [  ][  ][  ]
                                     [  ][  ][  ]
                         [  ][  ][  ][  ][  ][  ][  ][  ][  ]
                         [  ][  ][  ][  ][  ][  ][  ][  ][  ]
                         [  ][  ][  ][  ][  ][  ][  ][  ][  ]
                                     [  ][  ][  ]
                                     [  ][  ][  ]
                                     [  ][  ][  ]
                                     [  ][  ][  ]
                                     [  ][  ][  ]
                                     [  ][  ][  ]


    Next, I would prompt the user to then enter their current cube configuration. As long as the user is consistant, they can orient the cube as they desire.. and start entering their color scheme. This would be a good time to perform error checking. An easy way to do this.. would be a count of each color entered. IF a user enters 10 green squares for example, one could display an error, "green color count exceeded."




    R = Red
    B = Blue
    W = White
    O = Orange
    Y = Yellow
    G = Green

    This is an example only and may not reflect a real life cube configuration:
    Code:
                                  [R][G][G]
                                  [B][Y][W]
                                  [Y][O][B]
                         [O][G][Y][R][W][W][O][G][Y]
                         [G][Y][O][W][B][B][R][G][G]
                         [B][B][G][W][Y][O][Y][O][O]
                                  [R][G][R]
                                  [B][O][R]
                                  [O][O][W]
                                  [G][R][Y]
                                  [B][R [R]
                                  [Y][O][O]



    From this point, I run my algorithm for comming up with a solution to the rubix cube (which is to get all sides to be one solid color)

    One algorithm I came up with right away.. would be to have the program run several different instances of randomly moving the cube.. keeping track of each movement.. until one of the random methods eventually achieves a solution. Keep a counter of moves for all the methods that achieve a solution.. and pick the one that has the fewest amount of moves. (This is the cheap, easy, inefficient way to do it)

    Finally:

    Tell the user to locate this face of the square (for example)

    Code:
     [R][B][W]
     [O][Y][G]
     [O][R][R]
    Then I would run a solution function.. which would provide the user instruction to move thier cube.


    example:
    Code:
         Move the top row of your cube 90 degrees clockwise so it will match this picture _
    
     [Y][G][B]
     [O][Y][G]
     [O][R][R]

    Repeat until the cube is solved:



    Code:
     [B][B][B]
     [B][B][B]
     [B][B][B]




    The judging is going to be rather tricky...
    Judging will be easier than you think. With a program of this caliber, it will be obvious when someone has come up with an efficient way to solve a cube. Scoring will be 'cut and dry' with no interpretation needed on my part. Your program must weigh the costs of reduced user input versus run time.. and amount of code.


    since you should, to be fair, give the same input for each solution to see how each fairs under identical situations.
    One criteria of the judging will be to see if you can take the minimum amount of user input in order to achieve a solution. In my previous examples, I promted for every single square. If a programmer can solve a cube if given.. let's say only 2 sides of a cube.. then that would score better than a program that prompts for all 6 sides the cube.

    My ethics and scoring will be standard for all entrants.. which will make the contest as fair as possible. I have developed a standard checklist of criteria in which to judge each entry. The scoring for this aspect of the contest is simple. I am going to use a scale of 1 to 6. 1 being the user was prompted for "one side of the square".. and 6 being the user was prompted for "6 sides of the square."

    Beyond this.. run time will be added to your score. Line length will be added to your score. Number of moves will be added to your score.

    Person with the lowest overall score wins. (Kinda like a game of golf per se)


    The overall goals of this contest are to mimic the goals of real life programming. A customer would want the fastest, most efficient, most accurate, program with the least amount of code... and with the least amount of input from the user.


    elad: I would like a copy of that program please.. mail to here with a zipped attachment.
    Last edited by The Brain; 11-26-2004 at 08:31 PM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  12. #12
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    No, I mean, juding is going to be a pain in the ass if you're actually going to get the same configuration on an actual cube for each entry:
    grading this contest.. I am going to use a real life rubix cube (which is already randomly configured) and grade each entry based on the number of moves the programs recommend for solving the cube. I'll use at least 5 different random configurations from a real life cube in order to establish a grade for each program.
    That is to say, it's going to be a pain in the ass for you to configure the cube the same for each entry.

    Quzah.
    Hope is the first step on the road to disappointment.

  13. #13
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    im going to make my entry randomly move but avoid solving the cube just to give your fingers a work out

  14. #14
    The C-er
    Join Date
    Mar 2004
    Posts
    192
    I don't know C++ so could I do it in C please?\

    Or would this give me an unfair advantage?

  15. #15
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Make it C, but make it compile as C++:
    Code:
    extern "C" {
        ...all of your C code here...
    }


    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Expression Evaluator Contest
    By Stack Overflow in forum Contests Board
    Replies: 20
    Last Post: 03-29-2005, 10:34 AM
  2. Contest Winners
    By Sang-drax in forum Contests Board
    Replies: 0
    Last Post: 02-28-2005, 04:41 PM
  3. Anyone good with a Rubix Cube?
    By Nakeerb in forum C++ Programming
    Replies: 7
    Last Post: 11-05-2002, 05:59 PM