Random State CubieCube converts to an impossible scramble

[michaelcmelton]

When converting a random state scramble to a StickerCube, the resulting color string results in an impossible scramble with a potential corner parity. In my testing, the cube state {[{5 0} {4 2} {2 2} {6 0} {7 2} {0 0} {3 1} {1 2}] [{8 false} {6 true} {11 true} {3 true} {2 false} {9 false} {0 false} {4 true} {10 true} {5 false} {1 false} {7 true}]} converts to OWGYWBWYR RRBGYRGOO BBYOGBWYO OGWOBWYYR BOWWRWYBG BGRROGYRG.

Inputting those colors into a site like: https://rubiks-cube-solver.com/ give an impossible scramble to the solver, because of a potential corner parity. I twisted the colors on a corner twice, and it was able to successfully calcualate a solve solution.

[unixpickle]

Have you tested how often this happens? Random state generation does intentionally rotate the last corner to make the cube solvable. Might be worth using the solver in this repo to directly solve the scramble returned by the random state method, to see if maybe the conversion to sticker cube is actually what's broken, or something else.

[unixpickle]

This is where I see corner orientation being checked. https://github.com/unixpickle/gocube/blob/master/random_state.go#L40

[michaelcmelton]

I hadn’t thought about testing the random state with the solver to isolate the issue. I’ll check that out later today, and report back. Thanks!!

[michaelcmelton]

Solver finds solutions for the random cube state with no issues. Seems to be an issue with conversion then.

[michaelcmelton]

Looking into it further, RandomCubieCube does not give a true random state, either. Every time the function is called, it returns the same cube.

Edit: I should clarify this statement a bit. Excuse my rudimentary go code below.

func main() {
    var cube gcube.CubieCube
    var cube2 gcube.CubieCube
    cube = gcube.RandomCubieCube()
    cube2 = gcube.RandomCubieCube()
    fmt.Println(cube == cube2)
    fmt.Println(cube)
    fmt.Println(cube2)
    var solver *gcube.Solver
    solver = gcube.NewSolver(cube, 22)
    solutions := solver.Solutions()

    for x := range solutions {
        fmt.Println(x)
    }
}

Every time the main function is executed, cube and cube2 always return the same cubes, however, they are not the same states. My Interpretation was that no matter how many times the main function was executed, the cube and cube2 variables would almost always certainly be unique.

[unixpickle]

Go has a random number generator that is always fixed at program initialization. You can seed it like rand.Seed(time.Now().UnixNano()). The solutions are different likely because the solver is multithreaded which introduces non-determinism separate from the RNG.

[unixpickle]

If I get some time I can try to figure out what is wrong with the sticker conversion. I remember using this tool quite a bit at one point so I'm a bit surprised it's broken, although I don't think I used the cubie -> sticker cube -> string feature very much, so it seems like a likely candidate for a bug.

[unixpickle]

I also notice I have a ParseStickerCube function, so it should be easy to at least check that cubie -> sticker -> string -> sticker -> cubie always recovers the same cubie cube. Surprised I don't have a unit test for that.

[michaelcmelton]

I can see if I can’t get a test written for it, and open a PR if you like.

[unixpickle]

I had some time to get to the bottom of this tonight. Indeed the bug was random state scrambles, as you'd originally suspected (sorry for doubting you!). This went unnoticed because of a bug in the solver when corner orientation is invalid: it will happily spit out an "answer" that isn't actually solved.

Interestingly, the bug was not present in the sister library of this repo, puzzle.js, which does random state scrambles the same way. The bug doesn't happen there because random states are initialized as the identity, rather than in Go where they are created as all zeros. The strange thing is that I implemented the algorithm in gocube before puzzle.js, so it's surprising that my first implementation relied on an incorrect assumption that happened to be correct in the newer implementation. Maybe this wasn't the first time I had implemented random states in general...alas the explanation is lost in the sands of time!