Re: rosettacode - Solve a Rubik's Cube

new topic     » goto parent     » topic index » view thread      » older message » newer message
petelomax said...

New rosetta code entry for Phix: http://rosettacode.org/wiki/Solve_a_Rubik%27s_Cube
First time I've managed to get in the first entry for a task.

Any insights/comments/suggestions on the thistlethwaite entry (de-golfed from C++) would be most welcome.

Pete

I spent many hours in my youth solving the Rubik Cube. It was just a case of applying a known sequence to a pattern, usually like this:

4 top corners
4 top edges
4 middle edges
4 bottom corners
4 bottom edges

Each subsequent sequence applied had the property of ultimately not changing the position/orientation of any previously solved pieces... this is all unsurprising. Enter Thistlewaite's algorithm.. when you get to "even John Conway finds it quite hard!" it might be time to reevaluate priorities.. so I didn't read further.

However, if I had to write a program that my brain could understand it'd be something like this:

Arrange all pieces more abstractly (instead of the usual grid form.. which you probably still need to do the rotations), ie, into 5 groups: top corners, top edges, middle edges, bottom corners, bottom edges:

Group 1: C1, C2, C3, C4
Group 2: E1, E2, E3, E4
Group 3: E5, E6, E7, E8
Group 4: C5, C6, C7, C8
Group 5: E9 E10, E11, E12

Write a permutator to determine all possible combinations for each group (eg, group 1 will have something like 4! x 3^3, group 2 like 4! x 2^2 ). Then find the shortest path for a particular combo by iterating all possibilities [by using recursion to a max depth of, say, 20] . The path must not perturb the original state of the preceding groups.

Once all paths have been found apply them to the actual problem in the above group order.

Ok. It won't find the absolute shortest path but once the sequences were worked out the actual problem could be solved in uS. So when they are firing billions of Rubik combinations at you in your work you'll be swatting them away effectively using just your mind power.

Spock

new topic     » goto parent     » topic index » view thread      » older message » newer message

Search



Quick Links

User menu

Not signed in.

Misc Menu