Solve a cube by state, not by previous moves

[vmiklos]

Hi!

Thanks for this crate, looks quite promising. :-)

If I want to solve a cube where I know the previous moves from the solved solution, I can do something like:

use barbarosa::cube3::heuristics::mus;

fn main() {
    let cube = Cube3::solved();
    let mov = AxisMove::parse("F").unwrap();
    let moved = cube.clone().moved(&mov.clone().into());

    let heuristic = mus;
    let solution = moved.solve_with_heuristic(&heuristic);
}   

This works, but in case I just have the state of a real world cube, then I have a state, not a list of moves. Is it possible to use your solver to figure out such a state? If not, then this issue would be a feature request for that. :-)

Thanks again.

[Odilf]

Oh it's such a delightful surprise to see someone actually using the crate ^^

There are a couple of problems currently with what you're saying.

Firstly, you actually can do the thing you want, but it is very cumbersome. Cube3 has two fields, corners and edges, which are public. Therefore, you can just set them to the desired state. For example, the first entry of corners is the RUF corner, so if the RUF corner is, let's say, at RDF then you would have to set cube.corners[0] to RDF (so Corner::new(vector![[Positive, Negative, Positive]). And then set the correct orientation.

And when you're done, you still have the problem of not being able to know for sure if the state you have entered is correct, since I haven't implemented yet cube visualization (this is a problem because it's easy to make a mistake when figuring out orientations).

The last problem is that IDA* with the mus heuristic can't solve an arbitrary cube in a reasonable amount of time. In my M1 Pro it already takes some 9s to solve 13 moves, and most scrambled states take 17 (up to a max of 20). You would be lucky if an arbitrary state could be solved in less than a few hours.

As to solutions:

I think the most ergonomic way to input an external state is by using the unfolded representation, something like:

            -------------
            | U | U | U |
            | U | U | U |
            | U | U | U |
-------------------------------------
| L | L | L | F | F | F | R | R | R |
| L | L | L | F | F | F | R | R | R |
| L | L | L | F | F | F | R | R | R |
---------------------------------------
            | D | D | D |
            | D | D | D |
            | D | D | D |
            -------------
            | B | B | B |
            | B | B | B |
            | B | B | B |
            -------------

(obviously not as a string, but rather with some rust representation, and maybe a macro for convenience)

And while we're at it I should implement doing this the reverse way, which basically boils down to having a flat visualization of cubes.

I think I'll prioritize this right now (but no promises).

Finally, regarding actually solving the cube, I'm looking into implementing Kociemba's algorithm which can solve the cube in less than 20 moves very quickly (but is sometimes sub-optimal).

PS: The published crates.io version is very outdated, I'm not sure if that's the one you're using (if it is, consider using the crate as a git dependency). Also, you can tighten up the code by reducing some clones and using new_solved instead of solved, as so:

fn main() {
    let mov = AxisMove::parse("F").unwrap();
    let cube = Cube3::new_solved().moved(&mov);

    let solution = cube.solve_with_heuristic(heuristics::mus);
}

[vmiklos]

You would be lucky if an arbitrary state could be solved in less than a few hours.

Oh I see, thanks for being honest about performance. That's a bit slow, I'm a beginner when it comes to manual cube solving, but I usually solve it under 30 mins. :-)

So feel free to ignore this issue if you like till #17 is fixed.

[vmiklos]

Just to be completely upfront, currently I switched to https://crates.io/crates/kewb because that already has the kociemba algo implemented, and gives me a solution for a "not arbitrary, but what usually happens in practice" case in <1s. So if you enjoy doing that, feel free to implement this issue; but otherwise it's not a problem if you just close it. Have a nice weekend. :-)

[vmiklos]

Just to follow-up on this, my immediate need for this is gone. I assume it's better to close this issue, so you spend your time on issues which are useful to fix in practice.