How do y'all represent EP as (EP_U, EP_D, EP_E separately)?

[StachuK1992]

Not sure whether this belongs in Puzzle Theory or Software Area.

In any case, it seems most cube solving programs try to store the position of a cube initially as:
CP, CO, EP, EO.

[CO has 3^7 possibilities.] [CP has 12!/2 possibilities] [EO has 2^11 possibilities] [EP has 12!/2 possibilities]

Obviously, EP is the biggest of these by a long shot, and most EFFICIENT cube solvers (that I've come across) split this up in some way, typically the split listed in the title.


Can someone link me to a code sample of where this is done, understandably, psuedocode it out, or reason it out in words? I'm having some trouble figuring out how this is usually done.

EDIT: Clarification: my issue is relevant to creating pruning tables. My interpretation things seems to be that EP_U, EP_D, and EP_E can somehow be stored separately, but not getting *how*.

Thanks,
Stachu

 

[cuBerBruce]

I tend to prefer to split the edges up in a more symmetrical fashion: EP_E,_EP_M, and EP_S. But EP_U, EP_D_, and EP_E can work just as well.

Anyway, I number the edge positions 0 to 11, and the edge pieces correspondingly according to their solved positions. So EP_M is for edge pieces 0 to 3, EP_S for pieces 4 to 7, and EP_E for pieces 8 to 11.

Index  Cubie
------------
  0     UF
  1     UB
  2     DF
  3     DB
------------
  4     LU
  5     LD
  6     RU
  7     RD
------------
  8     FL
  9     FR
 10     BL
 11     BR

With this convention a 120-degree rotation about the UFL-UBR axis (z y) changes every cubie to a different set of 4, but without changing its relative index within its new set of 4. This can be handy for simplifying symmetry reduction.

(I note that I will sometimes use the fully symmetric EO convention, as indicated by the way I labeled the S-layer cubies, rather than the more standard <U, D, L, R, F2, B2> EO convention.)

So anyway, I store the permutation by cubie, not by positions. That is, at index n, I store the position where the nth cubie is currently located. This allows updating each set independently when applying a move. A position-based array would not.

The position can be made into coordinates by using the following function I call perm_nm_pack. The n parameter represents the total number of pieces, 12 in this case. The m parameter indicates the number of pieces in the subset, 4 in this case. This will calculate a value from 0 to 11880-1 for each coordinate, where 11880 = 12 choose 4.

typedef unsigned char UBYTE;
typedef unsigned int UINT;

UINT
perm_nm_pack (UINT n, UINT m, const UBYTE* array_in)
{
	UINT idx;
	UINT i, j;
	UINT x;

	idx = 0;

	for (i = 0; i < m; ++i) {
		idx *= (n - i);

		x = 0;
		for (j = 0; j < i; ++j) {
			if (array_in[j] < array_in[i]) {
				++x;
			}
		}
		idx += array_in[i] - x;
	}
	return idx;
}

Note that the solved state is represented by { 0, 4360, 8720 } rather than { 0, 0, 0 }. I also note that at least 14 bits are needed to store each of the 3 coordinates, for a total of at least 42 bits. Whereas the actual number of permutations is 479,001,600, requiring just 29 bits. So it is not as storage efficient.