4

I am trying to figure out how to measure the relative success level of a given (but unsolved!) Rubik's Cube state. My first idea was to calculate the number of overlapping "cells" in the destination (solved) state and the given (unsolved) state, and present this as the following:

number of actual correct cell positions / number of all positions (6x9)

But I have the feeling that this ratio doesn't necessarily correlate with the actual success level (so you're not necessarily closer to the full solution with a relatively high level of correct cell positions). Is there a more elegant (and calculable) way to measure this?

1
  • This way of measuring success in fact definitely doens't work for this problem, which is part of why the problem is harder to solve: the intuitive ways of gauging your progress don't give you useful clues. – Jules Feb 8 '18 at 10:51
8

If you could measure the distance from any state to the solved state, you'd have a trivial solution algorithm: simply make any move that reduces the distance! Therefore, a distance measure cannot be simpler than a cube-solving algorithm.

4
  • Thanks, but I hoped for something simpler ;) – Hendrik Feb 7 '18 at 9:33
  • 1
    perhaps not strictly true if you have local minima – Ewan Feb 7 '18 at 15:46
  • 5
    The logic of this answer is flawed - it makes the assumption that any "valid" distance measure has the property that for an unsolved cube, there is always a move reducing the distance. But this is only true for distance measures counting the required turns in respect to some cube-solving algorithm - which makes the whole statement a self-fulfilling prophecy. For other, heuristical distance measures, however, this approach can stick in a local minimum, as @Ewan already stated. – Doc Brown Feb 7 '18 at 16:34
  • Nitpick: There's a very "easy" solution that's guaranteed to get the best answer--simply do an A* walk from the solved cube. Obtaining the CPU cycles and memory for this option is left as an exercise for the reader.... – Loren Pechtel Dec 28 '19 at 3:34
2

If you for whatever reason cannot use one of the existing solver implementations, you can improve the estimation heuristic by not just counting how many cells are incorrectly positioned but rather summing the distance(whatever that might be) from their correct positions.

0. State representation

You can represent position of a cell by 3D vector(=array) of 3 values in range <-1,1> that is from -1 left/bottom, to 0 for center to right/top for +1. For example the [1,1,0] is for upper-right cell of front face. Center of cube is the origin. Note: face center cells are fixed so the position is orientation invariant as long as you always orient face centers the same way.

1. Manhattan distance

One of the simplest metrics is so called Manhattan distance, where you just add absolute differences of corresponding elements. For example manhattan distance from int[] v0 = [0,1,-1] to int[] v1 = int [1,1,1] is

var manhattan = abs(v0[0]-v1[0]) + abs(v0[1]-v1[1]) + abs(v0[2]-v1[2])

the solution level estimate is simply sum of Manhattan distance to correct position for each cell. While this is likely to be big improvement, it still does not take in account that the cube wraps around. If I am not mistaken the Manhattan distance was used as heuristic for IDA*, one of the first optimal solvers (in terms of least turns).

2. Swap & negate

As you might noticed, the actual distance to solution is corresponding to number (quarter)turns rather than physical distance on the cube. Instead, we should perform turns themselves - 3D rotation of the cell position vectors around axes which would lead to matrix multiplication...
...However as it turns out our case can be greatly simplified. Thanks to choosing <-1,1> instead of <0,2> we can use the well known swap & negate "trick", a way calculate perpendicular vectors. Fixing one element of vector, swapping the other two and negating one(which one controls the direction) of those will perform the quarter turn on face perpendicular to the fixed element. The procedure could look like this.

//calculates position of cell after a quarter-turn around given axis
void Rotate3DAligned(int[] vec, int axis, bool ccw)
{
  var first = vec[(i-1)%3];
  var second = vec[(i+1)%3];
  if(ccw) first = -first;
  else second = -second;
  vec[(i-1)%3] = second;
  vec[(i+1)%3] = first ;
}

Taking the current position of each cell and the correct one you need to determine how many turns (rotations - swap&negates) you need to take in order get it into the correct postion. This can be trivially solved by bruteforce since the max number is rather low, or better algorithmicaly - how many signs you need swap and how many values to "move" around.

2.1. Hash it

Count only distinct turn series i.e. save the series of turns into a HashSet or similar. This will allow detect many cases of "batch" moving cells, solving the one-turn-from solution problem.

disclaimer: algorithm not tested by implementation, code not checked

1

For a overestimating approach, you could implement a more or less simple cube solving algorithm and count how many moves it needs from a given position. Then run it with different starting orientations of the cube, and pick the minimum among those counts.

This approach can be extended by trying different variants of the algorithm, or different algorithms. For example, you could generate all configurations which can be reached by n quarter turns with n between 0 and some maximum, then run the solver, count the total number of turns and pick the minimum.

Measuring the number of correctly positioned "small cubes", and also the number of correctly oriented ones among can give you at least a rough measure about the "solution level". A high value of correctness will tell you that there is probably a solver algorithm which needs "not too many" turns any more. Any standard solving algorithm I have seen in the past increases the number of correctly placed "small cubes". If there are two or three "unrelated" cubes swapped, it is not too hard to construct a short move sequence to swap only those two or three cubes.

Unfortunately, the opposite is not true: a low level of correctness does not tell you that there cannot be an algorithm which may solve the cube in just a few turns. So all these suggestions above are just imperfect heuristics - if these helps you or not depends on your specific use case, which you actually did not mention in your question.

11
  • 5
    The problem with counting incorrectly positioned cubes is that one quater-turn on sovled cube creates 12 of those, while having two cubes swapped (just 2 incorrectly placed ones) on unrelated positions is arguably very hard to solve. – wondra Feb 7 '18 at 12:05
  • @wondra: sure, but if there are only a few cubes left, even if they don't belong to the same level, I am sure one can easily construct a move sequence to swap these two small pieces (at least with some minimal experience in how to construct such sequences). – Doc Brown Feb 7 '18 at 16:15
  • @wondra: if you have just two cubes swapped, then you are an infinite distance from a solved cube. No odd permutations are reachable from a solved cube. – kevin cline Feb 7 '18 at 17:58
  • @kevincline two cubes are just for illustration, you can imagine any visually almost-solved state instead. – wondra Feb 7 '18 at 18:01
  • @DocBrown: You cannot easily construct a move sequence that affects only a few pieces. – kevin cline Feb 7 '18 at 18:14
0

Each Rubik's cube can be solved in maximum of 26 quarter turns.

S = (26-N)/26

where N is number of remaining quarter turns necessary to solve the cube. This might be the most relevant metric to measure how far are you in solving the cube.

2
  • 2
    In some ways your and Kilian's answer are stating the same thing. The crux of the matter is knowing N - which you can only really know by solving the cube. – Peter M Feb 7 '18 at 12:26
  • @PeterM actually solving the cube for a software engineer should be rather easy - determine which cube-solving project suits the requirements the best (speed, language, docs,...) and submodule it. IMHO this is the most accurate metric (and contrary to the Kilian's answer an actual answer to the problem). – wondra Feb 8 '18 at 7:01
0

I've been looking at this same problem. One approach I am considering is to actually use the Two Phase Solver written by Herbert Kociemba here: https://github.com/hkociemba/RubiksCube-TwophaseSolver to solve the cube and determine the number of steps away from the solution you are.

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