39 ms·

I've been fascinated by the Rubik's cube for years after learning to solve one in 7th grade. I started to get back into it high school and dropped my solve time

I've been fascinated by the Rubik's cube for years after learning to solve one in 7th grade. I started to get back into it high school and dropped my solve times down below a minute. Then I continued in college and got down to 25 seconds average with a personal best of 15.15. I created a 2x2 Rubik's cube in Java as my freshman final project for my second computer science class, but it was quite ugly. Recently, I decided to take another look at implementing the cube - this time using Python. I also wanted a way to generate cubes and check if they were valid. The main representation of the cube is as a permutation group - a 48-tuple where each element in the tuple is unique. The solved cube is represented as (0, 1, ... , 46, 47). Turns of the cube simply permute this tuple. To figure these all out I spent a lot of time with a cube covered in post it notes. All of the stuff I implemented in the checking for valid cube comes from this stackoverflow post: https://math.stackexchange.com/questions/127577/how-to-tell-if-a-rubiks-cube-is-solvable/127627 https://math.stackexchange.com/questions/127577/how-to-tell-... I've had a lot of fun working with this cube as my personal project. I recently created a Django website and a RESTful API to display randomly generated cubes. Soon I'll be working on a data pipeline to process these random cubes and display them nicely. I've looked into working on a solution algorithm to implement Thistlethwaite's algorithm - https://www.jaapsch.net/puzzles/thistle.htm https://www.jaapsch.net/puzzles/thistle.htm. I think this will take me a while, but it should be doable. I haven't really though too much about implementing it, but I think the way to do it is to define what it is for each step to be completed and then BFS a graph of moves to end up in that state. If anyone has looked into this I'd love some advice! You can find the code I've written on Github: https://github.com/elliotmartin/RubikLite/blob/master/Rubik.py https://github.com/elliotmartin/RubikLite/blob/master/Rubik....

Retric 8y ago
My only suggestion is trying to quickly validate a cube is solvable seems like a waste of time vs generating them via a large number of random rotations. Especially when no cube can be more than 20 rotations from a solution.
- nsilvestri 8y ago
  Checking whether a cube is valid is effectively a random-state generator; i.e. it randomly chooses one of the 43 quintillion possible states. Generating random moves biases towards certain scrambles. This is why the World Cube Association generates random states of the cube with their library TNoodle, rather than random sequences of moves.
  - deleted 8y ago
    [deleted]
  - Retric 8y ago
    Citation needed on that. It’s trivial to do 10k random rotations in memory. At which point you have something indistinguishable from random.
    - perfect_wave 8y ago
      Except that simply isn't true. When randomly performing rotations you're much more likely to end up in certain states (as I mentioned in my other comment). Whether you make 10k random rotations or 20 random rotations you're still more likely to end up in a certain state.
      - Retric 8y ago
        In theory I agree with you, in practice I don’t. Sum 20 coin flips mod 3 and you can find the bias in the output. It’s hard with a small sample set, but you could do it. Sum 10k coin flips and it’s a different situation. Eventually you fall through the noise floor for any reasonable sample size.
        bunderbunder 8y ago
        It's almost certainly less effort (though arguably also less fun) to write a valid state checker than it is to prove that N random cube operations will yield something that's within some tolerance of a uniform distribution across all legal cube states.

Retric 8y ago

My only suggestion is trying to quickly validate a cube is solvable seems like a waste of time vs generating them via a large number of random rotations. Especially when no cube can be more than 20 rotations from a solution.

nsilvestri 8y ago
Checking whether a cube is valid is effectively a random-state generator; i.e. it randomly chooses one of the 43 quintillion possible states. Generating random moves biases towards certain scrambles. This is why the World Cube Association generates random states of the cube with their library TNoodle, rather than random sequences of moves.
- deleted 8y ago
  [deleted]
- Retric 8y ago
  Citation needed on that. It’s trivial to do 10k random rotations in memory. At which point you have something indistinguishable from random.
  - perfect_wave 8y ago
    Except that simply isn't true. When randomly performing rotations you're much more likely to end up in certain states (as I mentioned in my other comment). Whether you make 10k random rotations or 20 random rotations you're still more likely to end up in a certain state.
    - Retric 8y ago
      In theory I agree with you, in practice I don’t. Sum 20 coin flips mod 3 and you can find the bias in the output. It’s hard with a small sample set, but you could do it. Sum 10k coin flips and it’s a different situation. Eventually you fall through the noise floor for any reasonable sample size.
      - bunderbunder 8y ago
        It's almost certainly less effort (though arguably also less fun) to write a valid state checker than it is to prove that N random cube operations will yield something that's within some tolerance of a uniform distribution across all legal cube states.