I'm trying to build a 3x3x3 solver for a school project. I got inspired by Ben Botto's solver, which you can find here.

Such as Ben does with his solver, I'd like to implement Korf's heuristic approach, as described in his paper on Finding Optimal Solutions to Rubik's Cube Using Pattern Databases. The approach consists in making 3 separate heuristics : one for the corners, one for half of the edges, and one for the other half of the edges. I'm having trouble implementing the last two.

For some context : for each heuristic, there are 2 parameters to be taken in account, which are directly accessible with my data structure :

  • The orientation of each cubie (0, 1 or 2 if it's a corner ; 0 or 1 if it's an edge)
  • The position of each cubie, which we can convey with a permutation of size 8 for the corners, and of size 12 for the edges.

The next step is to create a hash for each heuristic, which we will use in our heuristic search. In order to do that, we need to hash the orientation of a cubie (that will simply be either a base 3 or base 2 integer) and the permutation, using Korf's linear algorithm for sequentially indexing permutation which uses Lehmer Codes to determine the lexicographic rank of a permutation.

I solved the corners, but I'm having trouble the edges. The problem is related to how we shall conceive "taking the first half of the edges". In his approach, Ben Botto simply considers the 6 first digits of the edge permutation and applies a modified version Korf's algorithm

The problem I'm encountering with this approach is that in the next step where you would use a Depth First Search to determine the depth associated with each possible hash value (that is to say each possible configuration of the edges), my program just doesn't find all the states. The reason for that is, I suspect, because multiple edge configuration can have the same hash value (because we only consider the first half of the edges). Therefore, if we encounter one configuration with a specific hash value and a depth n, in order to avoid endless recursion, the DFS will only consider a state with this hash value if and only if it has a depth lower than n. As a consequence, all the configuration with this hash value and a depth equal or greater than n (and all the states that are one move away from them, and so on...) will never be reached by the search.

I feel like I'm in a dead end, I don't know how to solve this problem. Has anyone by any chance experienced this issue or would have any idea how to solve it ?



Your Answer

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