11
$\begingroup$

As a fun project, I've been working on a C# implementation of Richard Korf's - Finding Optimal Solutions to Rubik's Cube Using Pattern Databases.

https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf

I actually have it working, I'm just trying to improve my solution.

One thing that Korf glazes over in his paper is how he stores and indexes into the pattern databases. Ideally, I think we want to use an instance of a rubik's cube to generate an index into an array.

My question is about the best way to generate this index.

My solution is to generate a minimal perfect hash. This involves keeping ALL of the cubes in memory until I have discovered the entire pattern database then generating a minimal perfect hash based off of that. The MPH takes a couple hours to run depending on the pattern database size, but I only need to do it once since I save it to disk. In the end, I can throw away the cubes themselves storing only the MPH. That way I can take a randomized rubik's cube, apply the pattern, then look up the array index in the MPH to get an estimated solution length.

I believe Korf and Shultz describe a better way to determine the cube's index in their 2005 paper called "Large Scale Breadth-First Search"

https://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf

This paper describes an algorithm to generate an index based off of the lexicographical ordering of a permutation. Basically you can take the permutation {1, 2, 3} and figure that it is the smallest with an index of 0. {1, 3, 2} is next up with an index of 1 and so on.

I feel like I should be able to apply this algorithm to a rubik's cube to get its index within a pattern database, but I'm having a hard time figuring out how it would work in practice.

The corners only pattern database for instance contains all rubik's cubes that have had their edge stickers taken off. There are exactly 88,179,840 cubes in this set. Any corner cubie on a rubiks cube can be in one of 24 different states. The state of the 8th corner cubie can be calculated based on the other 7 so cubes in the corners only pattern database each have 7 values between 0 and 23

e.g. {0, 3, 6, 9, 12, 15, 18, 21} defines the "solved" cube with all edge stickers removed.

if I rotate the front face 90 degrees the permutation might be: {0, 3, 11, 23, 12, 15, 8, 20}

Is there a way to get an index out of these sort of permutations?

Improve this question
$\endgroup$
3
  • $\begingroup$ You'll probably find this interesting. $\endgroup$
    – Tom van der Zanden
    Commented Mar 11, 2016 at 20:57
  • $\begingroup$ interesting! you say he "glazes over" something in the paper. it would be better to be more specific about the section that is not "fleshed out". you also say you have it working. what is your initial indexing implementation? is this a school project? suggest further Computer Science Chat on it. also eg blogging about it or open sourcing the code can be helpful to others & lead to more detail. also the paper does not seem to refer to any hashing functions... $\endgroup$
    – vzn
    Commented Mar 12, 2016 at 17:46
  • $\begingroup$ I implemented Korf's algorithm: github.com/benbotto/rubiks-cube-cracker. I, too, found the indexing to be difficult, so I wrote an article about it on Medium: medium.com/@benjamin.botto/… $\endgroup$
    – benbotto
    Commented Jan 2, 2020 at 19:45

1 Answer 1

Reset to default
6
$\begingroup$

You don't explain what the numbers from 0 to 23 mean, but according to this answer, you can represent the state of the corners using eight pairs $(p_i,o_i)$, where $(p_0,\ldots,p_7)$ is a permutation of $(0,\ldots,7)$, $o_i \in \{0,1,2\}$, and $o_7$ (say) is determined by $o_0,\ldots,o_6$. In total, this gives $8! \cdot 3^7 = 88179840$ degrees of freedom. Assuming that you can decompose your $\{0,\ldots,23\}$ to pairs $(p_i,o_i)$, you can easily convert a position to an index by encoding separately the permutation $(p_0,\ldots,p_7)$ (which the AAAI paper explains how to do) and the values $o_0,\ldots,o_6$, which you can encode in base 3. Putting the two values together in the obvious way (for example, $3^7p + o$ or $8!o + p$), we get an index.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Hey Yuval, thanks for the comment. For me, 0 to 23 are how I identify the unique position / orientation that a corner cube can be in. 8 positions times 3 orientations per position = 24. Fortunately I can easily split this value up into separate position / orientation tuples. Your answer led me to this code which is an implementation of the algorithm you're describing. github.com/brownan/Rubiks-Cube-Solver/blob/master/cornertable.c I'll need to do a bit of work to make this more generic (so that I can handle different patterns than "corners only") but now Im on the right track thx! $\endgroup$
    – Cosmosis
    Commented Mar 15, 2016 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.