1
|
package org.distorted.solvers.cube3;
|
2
|
|
3
|
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
4
|
//Cube on the cubie level
|
5
|
class CubieCube
|
6
|
{
|
7
|
private static int[][] cnk = new int[12][7];
|
8
|
|
9
|
private static byte[] tmpByte12 = new byte[12];
|
10
|
private static byte[] tmpByte8 = new byte[8];
|
11
|
|
12
|
private static int[] tmpEdge12 = new int[12];
|
13
|
private static int[] tmpEdge6 = new int[6];
|
14
|
private static int[] tmpEdge4 = new int[4];
|
15
|
private static int[] tmpEdge3 = new int[3];
|
16
|
|
17
|
private static int[] tmpCorner6 = new int[6];
|
18
|
private static int[] tmpCorner8 = new int[8];
|
19
|
|
20
|
// initialize to Id-Cube
|
21
|
|
22
|
// corner permutation
|
23
|
int[] cp = { Corner.URF, Corner.UFL, Corner.ULB, Corner.UBR, Corner.DFR, Corner.DLF, Corner.DBL, Corner.DRB };
|
24
|
|
25
|
// corner orientation
|
26
|
byte[] co = { 0, 0, 0, 0, 0, 0, 0, 0 };
|
27
|
|
28
|
// edge permutation
|
29
|
int[] ep = { Edge.UR, Edge.UF, Edge.UL, Edge.UB, Edge.DR, Edge.DF, Edge.DL, Edge.DB, Edge.FR, Edge.FL, Edge.BL, Edge.BR };
|
30
|
|
31
|
// edge orientation
|
32
|
byte[] eo = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
|
33
|
|
34
|
// ************************************** Moves on the cubie level ***************************************************
|
35
|
|
36
|
private static int[] cpU = { Corner.UBR, Corner.URF, Corner.UFL, Corner.ULB, Corner.DFR, Corner.DLF, Corner.DBL, Corner.DRB };
|
37
|
private static byte[] coU = { 0, 0, 0, 0, 0, 0, 0, 0 };
|
38
|
private static int[] epU = { Edge.UB, Edge.UR, Edge.UF, Edge.UL, Edge.DR, Edge.DF, Edge.DL, Edge.DB, Edge.FR, Edge.FL, Edge.BL, Edge.BR };
|
39
|
private static byte[] eoU = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
|
40
|
|
41
|
private static int[] cpR = { Corner.DFR, Corner.UFL, Corner.ULB, Corner.URF, Corner.DRB, Corner.DLF, Corner.DBL, Corner.UBR };
|
42
|
private static byte[] coR = { 2, 0, 0, 1, 1, 0, 0, 2 };
|
43
|
private static int[] epR = { Edge.FR, Edge.UF, Edge.UL, Edge.UB, Edge.BR, Edge.DF, Edge.DL, Edge.DB, Edge.DR, Edge.FL, Edge.BL, Edge.UR };
|
44
|
private static byte[] eoR = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
|
45
|
|
46
|
private static int[] cpF = { Corner.UFL, Corner.DLF, Corner.ULB, Corner.UBR, Corner.URF, Corner.DFR, Corner.DBL, Corner.DRB };
|
47
|
private static byte[] coF = { 1, 2, 0, 0, 2, 1, 0, 0 };
|
48
|
private static int[] epF = { Edge.UR, Edge.FL, Edge.UL, Edge.UB, Edge.DR, Edge.FR, Edge.DL, Edge.DB, Edge.UF, Edge.DF, Edge.BL, Edge.BR };
|
49
|
private static byte[] eoF = { 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0 };
|
50
|
|
51
|
private static int[] cpD = { Corner.URF, Corner.UFL, Corner.ULB, Corner.UBR, Corner.DLF, Corner.DBL, Corner.DRB, Corner.DFR };
|
52
|
private static byte[] coD = { 0, 0, 0, 0, 0, 0, 0, 0 };
|
53
|
private static int[] epD = { Edge.UR, Edge.UF, Edge.UL, Edge.UB, Edge.DF, Edge.DL, Edge.DB, Edge.DR, Edge.FR, Edge.FL, Edge.BL, Edge.BR };
|
54
|
private static byte[] eoD = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
|
55
|
|
56
|
private static int[] cpL = { Corner.URF, Corner.ULB, Corner.DBL, Corner.UBR, Corner.DFR, Corner.UFL, Corner.DLF, Corner.DRB };
|
57
|
private static byte[] coL = { 0, 1, 2, 0, 0, 2, 1, 0 };
|
58
|
private static int[] epL = { Edge.UR, Edge.UF, Edge.BL, Edge.UB, Edge.DR, Edge.DF, Edge.FL, Edge.DB, Edge.FR, Edge.UL, Edge.DL, Edge.BR };
|
59
|
private static byte[] eoL = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
|
60
|
|
61
|
private static int[] cpB = { Corner.URF, Corner.UFL, Corner.UBR, Corner.DRB, Corner.DFR, Corner.DLF, Corner.ULB, Corner.DBL };
|
62
|
private static byte[] coB = { 0, 0, 1, 2, 0, 0, 2, 1 };
|
63
|
private static int[] epB = { Edge.UR, Edge.UF, Edge.UL, Edge.BR, Edge.DR, Edge.DF, Edge.DL, Edge.BL, Edge.FR, Edge.FL, Edge.UB, Edge.DB };
|
64
|
private static byte[] eoB = { 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1 };
|
65
|
|
66
|
// this CubieCube array represents the 6 basic cube moves
|
67
|
static CubieCube[] moveCube = new CubieCube[6];
|
68
|
|
69
|
static
|
70
|
{
|
71
|
moveCube[0] = new CubieCube();
|
72
|
moveCube[0].cp = cpU;
|
73
|
moveCube[0].co = coU;
|
74
|
moveCube[0].ep = epU;
|
75
|
moveCube[0].eo = eoU;
|
76
|
|
77
|
moveCube[1] = new CubieCube();
|
78
|
moveCube[1].cp = cpR;
|
79
|
moveCube[1].co = coR;
|
80
|
moveCube[1].ep = epR;
|
81
|
moveCube[1].eo = eoR;
|
82
|
|
83
|
moveCube[2] = new CubieCube();
|
84
|
moveCube[2].cp = cpF;
|
85
|
moveCube[2].co = coF;
|
86
|
moveCube[2].ep = epF;
|
87
|
moveCube[2].eo = eoF;
|
88
|
|
89
|
moveCube[3] = new CubieCube();
|
90
|
moveCube[3].cp = cpD;
|
91
|
moveCube[3].co = coD;
|
92
|
moveCube[3].ep = epD;
|
93
|
moveCube[3].eo = eoD;
|
94
|
|
95
|
moveCube[4] = new CubieCube();
|
96
|
moveCube[4].cp = cpL;
|
97
|
moveCube[4].co = coL;
|
98
|
moveCube[4].ep = epL;
|
99
|
moveCube[4].eo = eoL;
|
100
|
|
101
|
moveCube[5] = new CubieCube();
|
102
|
moveCube[5].cp = cpB;
|
103
|
moveCube[5].co = coB;
|
104
|
moveCube[5].ep = epB;
|
105
|
moveCube[5].eo = eoB;
|
106
|
}
|
107
|
|
108
|
static
|
109
|
{
|
110
|
for(int n=0; n<12; n++)
|
111
|
for(int k=0; k<7; k++)
|
112
|
cnk[n][k] = -1;
|
113
|
}
|
114
|
|
115
|
CubieCube() { };
|
116
|
|
117
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
118
|
CubieCube(int[] cp, byte[] co, int[] ep, byte[] eo)
|
119
|
{
|
120
|
this();
|
121
|
|
122
|
for (int i = 0; i < 8; i++)
|
123
|
{
|
124
|
this.cp[i] = cp[i];
|
125
|
this.co[i] = co[i];
|
126
|
}
|
127
|
for (int i = 0; i < 12; i++)
|
128
|
{
|
129
|
this.ep[i] = ep[i];
|
130
|
this.eo[i] = eo[i];
|
131
|
}
|
132
|
}
|
133
|
|
134
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
135
|
// n choose k
|
136
|
static int Cnk(int n, int k)
|
137
|
{
|
138
|
if( cnk[n][k]<0 )
|
139
|
{
|
140
|
int i, j, s;
|
141
|
|
142
|
if (n < k) { cnk[n][k]=0; return 0; }
|
143
|
if (k > n / 2) k = n - k;
|
144
|
|
145
|
for (s = 1, i = n, j = 1; i != n - k; i--, j++)
|
146
|
{
|
147
|
s *= i;
|
148
|
s /= j;
|
149
|
}
|
150
|
cnk[n][k]= s;
|
151
|
}
|
152
|
|
153
|
return cnk[n][k];
|
154
|
}
|
155
|
|
156
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
157
|
static void rotateLeft(int[] arr, int l, int r)
|
158
|
// Left rotation of all array elements between l and r
|
159
|
{
|
160
|
int tmp = arr[l];
|
161
|
for (int i = l; i < r; i++) arr[i] = arr[i + 1];
|
162
|
arr[r] = tmp;
|
163
|
}
|
164
|
|
165
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
166
|
static void rotateRight(int[] arr, int l, int r)
|
167
|
// Right rotation of all array elements between l and r
|
168
|
{
|
169
|
int tmp = arr[r];
|
170
|
for (int i = r; i > l; i--) arr[i] = arr[i - 1];
|
171
|
arr[l] = tmp;
|
172
|
}
|
173
|
|
174
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
175
|
// return cube in facelet representation
|
176
|
FaceCube toFaceCube()
|
177
|
{
|
178
|
FaceCube fcRet = new FaceCube();
|
179
|
|
180
|
for ( int c=Corner.URF; c<=Corner.DRB; c++)
|
181
|
{
|
182
|
int j = cp[c]; // cornercubie with index j is at cornerposition with index i
|
183
|
byte ori = co[c];// Orientation of this cubie
|
184
|
|
185
|
for (int n = 0; n < 3; n++)
|
186
|
fcRet.f[FaceCube.cornerFacelet[c][(n + ori) % 3]] = FaceCube.cornerColor[j][n];
|
187
|
}
|
188
|
|
189
|
for ( int e=Edge.UR; e<=Edge.BR; e++)
|
190
|
{
|
191
|
int j = ep[e]; // edgecubie with index j is at edgeposition with index i
|
192
|
byte ori = eo[e];// Orientation of this cubie
|
193
|
|
194
|
for (int n = 0; n < 2; n++)
|
195
|
fcRet.f[FaceCube.edgeFacelet[e][(n + ori) % 2]] = FaceCube.edgeColor[j][n];
|
196
|
}
|
197
|
|
198
|
return fcRet;
|
199
|
}
|
200
|
|
201
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
202
|
// Multiply this CubieCube with another cubiecube b, restricted to the corners.<br>
|
203
|
// Because we also describe reflections of the whole cube by permutations, we get a complication with the corners. The
|
204
|
// orientations of mirrored corners are described by the numbers 3, 4 and 5. The composition of the orientations
|
205
|
// cannot
|
206
|
// be computed by addition modulo three in the cyclic group C3 any more. Instead the rules below give an addition in
|
207
|
// the dihedral group D3 with 6 elements.<br>
|
208
|
//
|
209
|
// NOTE: Because we do not use symmetry reductions and hence no mirrored cubes in this simple implementation of the
|
210
|
// Two-Phase-Algorithm, some code is not necessary here.
|
211
|
//
|
212
|
void cornerMultiply(CubieCube b)
|
213
|
{
|
214
|
for ( int corn=Corner.URF; corn<=Corner.DRB; corn++)
|
215
|
{
|
216
|
tmpCorner8[corn] = cp[b.cp[corn]];
|
217
|
byte oriA = co[b.cp[corn]];
|
218
|
byte oriB = b.co[corn];
|
219
|
byte ori = 0;
|
220
|
|
221
|
if (oriA < 3 && oriB < 3) // if both cubes are regular cubes...
|
222
|
{
|
223
|
ori = (byte) (oriA + oriB); // just do an addition modulo 3 here
|
224
|
if (ori >= 3) ori -= 3; // the composition is a regular cube
|
225
|
|
226
|
// +++++++++++++++++++++not used in this implementation +++++++++++++++++++++++++++++++++++
|
227
|
}
|
228
|
else if (oriA < 3 && oriB >= 3) // if cube b is in a mirrored state...
|
229
|
{
|
230
|
ori = (byte) (oriA + oriB);
|
231
|
if (ori >= 6) ori -= 3; // the composition is a mirrored cube
|
232
|
}
|
233
|
else if (oriA >= 3 && oriB < 3) // if cube a is an a mirrored state...
|
234
|
{
|
235
|
ori = (byte) (oriA - oriB);
|
236
|
if (ori < 3) ori += 3; // the composition is a mirrored cube
|
237
|
}
|
238
|
else if (oriA >= 3 && oriB >= 3) // if both cubes are in mirrored states...
|
239
|
{
|
240
|
ori = (byte) (oriA - oriB);
|
241
|
if (ori < 0) ori += 3; // the composition is a regular cube
|
242
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
243
|
}
|
244
|
|
245
|
tmpByte8[corn] = ori;
|
246
|
}
|
247
|
|
248
|
for ( int c=Corner.URF; c<=Corner.DRB; c++)
|
249
|
{
|
250
|
cp[c] = tmpCorner8[c];
|
251
|
co[c] = tmpByte8[c];
|
252
|
}
|
253
|
}
|
254
|
|
255
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
256
|
// Multiply this CubieCube with another cubiecube b, restricted to the edges.
|
257
|
void edgeMultiply(CubieCube b)
|
258
|
{
|
259
|
for ( int edge=Edge.UR; edge<=Edge.BR; edge++)
|
260
|
{
|
261
|
tmpEdge12[edge] = ep[b.ep[edge]];
|
262
|
tmpByte12[edge] = (byte) ((b.eo[edge] + eo[b.ep[edge]]) % 2);
|
263
|
}
|
264
|
|
265
|
for ( int e=Edge.UR; e<=Edge.BR; e++)
|
266
|
{
|
267
|
ep[e] = tmpEdge12[e];
|
268
|
eo[e] = tmpByte12[e];
|
269
|
}
|
270
|
}
|
271
|
|
272
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
273
|
// Multiply this CubieCube with another CubieCube b.
|
274
|
void multiply(CubieCube b)
|
275
|
{
|
276
|
cornerMultiply(b);
|
277
|
//edgeMultiply(b);
|
278
|
}
|
279
|
|
280
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
281
|
// Compute the inverse CubieCube
|
282
|
void invCubieCube(CubieCube c)
|
283
|
{
|
284
|
for ( int edge=Edge.UR; edge<=Edge.BR; edge++) c.ep[ep[edge]] = edge;
|
285
|
for ( int edge=Edge.UR; edge<=Edge.BR; edge++) c.eo[edge] = eo[c.ep[edge]];
|
286
|
|
287
|
for ( int corn=Corner.URF; corn<=Corner.DRB; corn++) c.cp[cp[corn]] = corn;
|
288
|
for ( int corn=Corner.URF; corn<=Corner.DRB; corn++)
|
289
|
{
|
290
|
byte ori = co[c.cp[corn]];
|
291
|
if (ori >= 3)// Just for completeness. We do not invert mirrored cubes in the program.
|
292
|
c.co[corn] = ori;
|
293
|
else
|
294
|
{// the standard case
|
295
|
c.co[corn] = (byte) -ori;
|
296
|
if (c.co[corn] < 0) c.co[corn] += 3;
|
297
|
}
|
298
|
}
|
299
|
}
|
300
|
|
301
|
// ********************************************* Get and set coordinates *********************************************
|
302
|
|
303
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
304
|
// return the twist of the 8 corners. 0 <= twist < 3^7
|
305
|
short getTwist()
|
306
|
{
|
307
|
short ret = 0;
|
308
|
|
309
|
for ( int i=Corner.URF; i<Corner.DRB; i++)
|
310
|
ret = (short) (3 * ret + co[i]);
|
311
|
|
312
|
return ret;
|
313
|
}
|
314
|
|
315
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
316
|
void setTwist(short twist)
|
317
|
{
|
318
|
int twistParity = 0;
|
319
|
|
320
|
for ( int i=Corner.DRB-1; i>=Corner.URF; i--)
|
321
|
{
|
322
|
twistParity += co[i] = (byte) (twist % 3);
|
323
|
twist /= 3;
|
324
|
}
|
325
|
co[Corner.DRB] = (byte) ((3 - twistParity % 3) % 3);
|
326
|
}
|
327
|
|
328
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
329
|
// return the flip of the 12 edges. 0<= flip < 2^11
|
330
|
short getFlip()
|
331
|
{
|
332
|
short ret = 0;
|
333
|
|
334
|
for ( int i=Edge.UR; i<Edge.BR; i++)
|
335
|
ret = (short) (2 * ret + eo[i]);
|
336
|
|
337
|
return ret;
|
338
|
}
|
339
|
|
340
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
341
|
void setFlip(short flip)
|
342
|
{
|
343
|
int flipParity = 0;
|
344
|
|
345
|
for (int i=Edge.BR-1; i>=Edge.UR; i--)
|
346
|
{
|
347
|
flipParity += eo[i] = (byte) (flip % 2);
|
348
|
flip /= 2;
|
349
|
}
|
350
|
eo[Edge.BR] = (byte) ((2 - flipParity % 2) % 2);
|
351
|
}
|
352
|
|
353
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
354
|
// Parity of the corner permutation
|
355
|
short cornerParity()
|
356
|
{
|
357
|
int s = 0;
|
358
|
|
359
|
for (int i=Corner.DRB; i>=Corner.URF+1; i--)
|
360
|
for (int j = i - 1; j >= Corner.URF; j--)
|
361
|
if (cp[j] > cp[i]) s++;
|
362
|
|
363
|
return (short) (s % 2);
|
364
|
}
|
365
|
|
366
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
367
|
// Parity of the edges permutation. Parity of corners and edges are the same if the cube is solvable.
|
368
|
short edgeParity()
|
369
|
{
|
370
|
int s = 0;
|
371
|
|
372
|
for (int i = Edge.BR; i >= Edge.UR+1; i--)
|
373
|
for (int j = i - 1; j >= Edge.UR; j--)
|
374
|
if (ep[j] > ep[i]) s++;
|
375
|
|
376
|
return (short) (s % 2);
|
377
|
}
|
378
|
|
379
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
380
|
// permutation of the UD-slice edges FR,FL,BL and BR
|
381
|
short getFRtoBR()
|
382
|
{
|
383
|
int a = 0, x = 0;
|
384
|
|
385
|
// compute the index a < (12 choose 4) and the permutation array perm.
|
386
|
for (int j = Edge.BR; j >= Edge.UR; j--)
|
387
|
if (Edge.FR <= ep[j] && ep[j] <= Edge.BR)
|
388
|
{
|
389
|
a += Cnk(11 - j, x + 1);
|
390
|
tmpEdge4[3 - x++] = ep[j];
|
391
|
}
|
392
|
|
393
|
int b = 0;
|
394
|
for (int j = 3; j > 0; j--)// compute the index b < 4! for the permutation in perm
|
395
|
{
|
396
|
int k = 0;
|
397
|
while (tmpEdge4[j] != j + 8)
|
398
|
{
|
399
|
rotateLeft(tmpEdge4, 0, j);
|
400
|
k++;
|
401
|
}
|
402
|
b = (j + 1) * b + k;
|
403
|
}
|
404
|
|
405
|
return (short) (24 * a + b);
|
406
|
}
|
407
|
|
408
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
409
|
void setFRtoBR(short idx)
|
410
|
{
|
411
|
int x;
|
412
|
int[] sliceEdge = { Edge.FR, Edge.FL, Edge.BL, Edge.BR };
|
413
|
int[] otherEdge = { Edge.UR, Edge.UF, Edge.UL, Edge.UB, Edge.DR, Edge.DF, Edge.DL, Edge.DB };
|
414
|
int b = idx % 24; // Permutation
|
415
|
int a = idx / 24; // Combination
|
416
|
|
417
|
for ( int e=Edge.UR; e<=Edge.BR; e++) ep[e] = Edge.DB;// Use UR to invalidate all edges
|
418
|
|
419
|
for (int j = 1, k; j < 4; j++)// generate permutation from index b
|
420
|
{
|
421
|
k = b % (j + 1);
|
422
|
b /= j + 1;
|
423
|
while (k-- > 0) rotateRight(sliceEdge, 0, j);
|
424
|
}
|
425
|
|
426
|
x = 3;// generate combination and set slice edges
|
427
|
|
428
|
for (int j = Edge.UR; j <= Edge.BR; j++)
|
429
|
if (a - Cnk(11 - j, x + 1) >= 0)
|
430
|
{
|
431
|
ep[j] = sliceEdge[3 - x];
|
432
|
a -= Cnk(11 - j, x-- + 1);
|
433
|
}
|
434
|
|
435
|
x = 0; // set the remaining edges UR..DB
|
436
|
|
437
|
for (int j = Edge.UR; j <= Edge.BR; j++)
|
438
|
if (ep[j] == Edge.DB)
|
439
|
ep[j] = otherEdge[x++];
|
440
|
|
441
|
}
|
442
|
|
443
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
444
|
// Permutation of all corners except DBL and DRB
|
445
|
short getURFtoDLF()
|
446
|
{
|
447
|
int a = 0, x = 0;
|
448
|
|
449
|
// compute the index a < (8 choose 6) and the corner permutation.
|
450
|
for (int j = Corner.URF; j <= Corner.DRB; j++)
|
451
|
if (cp[j] <= Corner.DLF)
|
452
|
{
|
453
|
a += Cnk(j, x + 1);
|
454
|
tmpCorner6[x++] = cp[j];
|
455
|
}
|
456
|
|
457
|
int b = 0;
|
458
|
|
459
|
for (int j = 5; j > 0; j--)// compute the index b < 6! for the permutation in corner6
|
460
|
{
|
461
|
int k = 0;
|
462
|
|
463
|
while (tmpCorner6[j] != j)
|
464
|
{
|
465
|
rotateLeft(tmpCorner6, 0, j);
|
466
|
k++;
|
467
|
}
|
468
|
b = (j + 1) * b + k;
|
469
|
}
|
470
|
|
471
|
return (short) (720 * a + b);
|
472
|
}
|
473
|
|
474
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
475
|
void setURFtoDLF(short idx)
|
476
|
{
|
477
|
int x;
|
478
|
|
479
|
int[] corner6 = { Corner.URF, Corner.UFL, Corner.ULB, Corner.UBR, Corner.DFR, Corner.DLF };
|
480
|
int[] otherCorner = { Corner.DBL, Corner.DRB };
|
481
|
int b = idx % 720; // Permutation
|
482
|
int a = idx / 720; // Combination
|
483
|
|
484
|
for ( int c=Corner.URF; c<=Corner.DRB; c++) cp[c] = Corner.DRB;// Use DRB to invalidate all corners
|
485
|
|
486
|
for (int j = 1, k; j < 6; j++)// generate permutation from index b
|
487
|
{
|
488
|
k = b % (j + 1);
|
489
|
b /= j + 1;
|
490
|
while (k-- > 0) rotateRight(corner6, 0, j);
|
491
|
}
|
492
|
|
493
|
x = 5;// generate combination and set corners
|
494
|
|
495
|
for (int j = Corner.DRB; j >= 0; j--)
|
496
|
if (a - Cnk(j, x + 1) >= 0)
|
497
|
{
|
498
|
cp[j] = corner6[x];
|
499
|
a -= Cnk(j, x-- + 1);
|
500
|
}
|
501
|
|
502
|
x = 0;
|
503
|
|
504
|
for (int j = Corner.URF; j <= Corner.DRB; j++)
|
505
|
if (cp[j] == Corner.DRB)
|
506
|
cp[j] = otherCorner[x++];
|
507
|
}
|
508
|
|
509
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
510
|
// Permutation of the six edges UR,UF,UL,UB,DR,DF.
|
511
|
int getURtoDF()
|
512
|
{
|
513
|
int a = 0, x = 0;
|
514
|
// compute the index a < (12 choose 6) and the edge permutation.
|
515
|
|
516
|
for (int j = Edge.UR; j <= Edge.BR; j++)
|
517
|
if (ep[j] <= Edge.DF)
|
518
|
{
|
519
|
a += Cnk(j, x + 1);
|
520
|
tmpEdge6[x++] = ep[j];
|
521
|
}
|
522
|
|
523
|
int b = 0;
|
524
|
|
525
|
for (int j = 5; j > 0; j--)// compute the index b < 6! for the permutation in edge6
|
526
|
{
|
527
|
int k = 0;
|
528
|
|
529
|
while (tmpEdge6[j] != j)
|
530
|
{
|
531
|
rotateLeft(tmpEdge6, 0, j);
|
532
|
k++;
|
533
|
}
|
534
|
b = (j + 1) * b + k;
|
535
|
}
|
536
|
return 720 * a + b;
|
537
|
}
|
538
|
|
539
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
540
|
void setURtoDF(int idx)
|
541
|
{
|
542
|
int x;
|
543
|
int[] edge6 = { Edge.UR, Edge.UF, Edge.UL, Edge.UB, Edge.DR, Edge.DF };
|
544
|
int[] otherEdge = { Edge.DL, Edge.DB, Edge.FR, Edge.FL, Edge.BL, Edge.BR };
|
545
|
int b = idx % 720; // Permutation
|
546
|
int a = idx / 720; // Combination
|
547
|
|
548
|
for ( int e=Edge.UR; e<=Edge.BR; e++) ep[e] = Edge.BR;// Use BR to invalidate all edges
|
549
|
|
550
|
for (int j = 1, k; j < 6; j++)// generate permutation from index b
|
551
|
{
|
552
|
k = b % (j + 1);
|
553
|
b /= j + 1;
|
554
|
while (k-- > 0) rotateRight(edge6, 0, j);
|
555
|
}
|
556
|
|
557
|
x = 5;// generate combination and set edges
|
558
|
|
559
|
for (int j = Edge.BR; j >= 0; j--)
|
560
|
if (a - Cnk(j, x + 1) >= 0)
|
561
|
{
|
562
|
ep[j] = edge6[x];
|
563
|
a -= Cnk(j, x-- + 1);
|
564
|
}
|
565
|
|
566
|
x = 0; // set the remaining edges DL..BR
|
567
|
|
568
|
for (int j = Edge.UR; j <= Edge.BR; j++)
|
569
|
if (ep[j] == Edge.BR)
|
570
|
ep[j] = otherEdge[x++];
|
571
|
}
|
572
|
|
573
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
574
|
// Permutation of the six edges UR,UF,UL,UB,DR,DF
|
575
|
public static int getURtoDF(short idx1, short idx2)
|
576
|
{
|
577
|
CubieCube a = new CubieCube();
|
578
|
CubieCube b = new CubieCube();
|
579
|
a.setURtoUL(idx1);
|
580
|
b.setUBtoDF(idx2);
|
581
|
|
582
|
for (int i = 0; i < 8; i++)
|
583
|
{
|
584
|
if (a.ep[i] != Edge.BR)
|
585
|
if (b.ep[i] != Edge.BR)// collision
|
586
|
return -1;
|
587
|
else
|
588
|
b.ep[i] = a.ep[i];
|
589
|
}
|
590
|
|
591
|
return b.getURtoDF();
|
592
|
}
|
593
|
|
594
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
595
|
// Permutation of the three edges UR,UF,UL
|
596
|
short getURtoUL()
|
597
|
{
|
598
|
int a = 0, x = 0;
|
599
|
// compute the index a < (12 choose 3) and the edge permutation.
|
600
|
for (int j = Edge.UR; j <= Edge.BR; j++)
|
601
|
if (ep[j] <= Edge.UL)
|
602
|
{
|
603
|
a += Cnk(j, x + 1);
|
604
|
tmpEdge3[x++] = ep[j];
|
605
|
}
|
606
|
|
607
|
int b = 0;
|
608
|
|
609
|
for (int j = 2; j > 0; j--)// compute the index b < 3! for the permutation in edge3
|
610
|
{
|
611
|
int k = 0;
|
612
|
while (tmpEdge3[j] != j)
|
613
|
{
|
614
|
rotateLeft(tmpEdge3, 0, j);
|
615
|
k++;
|
616
|
}
|
617
|
b = (j + 1) * b + k;
|
618
|
}
|
619
|
|
620
|
return (short) (6 * a + b);
|
621
|
}
|
622
|
|
623
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
624
|
void setURtoUL(short idx)
|
625
|
{
|
626
|
int x;
|
627
|
int[] edge3 = { Edge.UR, Edge.UF, Edge.UL };
|
628
|
int b = idx % 6; // Permutation
|
629
|
int a = idx / 6; // Combination
|
630
|
|
631
|
for (int e = Edge.UR; e <= Edge.BR; e++) ep[e] = Edge.BR;// Use BR to invalidate all edges
|
632
|
|
633
|
for (int j = 1, k; j < 3; j++)// generate permutation from index b
|
634
|
{
|
635
|
k = b % (j + 1);
|
636
|
b /= j + 1;
|
637
|
|
638
|
while (k-- > 0) rotateRight(edge3, 0, j);
|
639
|
}
|
640
|
|
641
|
x = 2;// generate combination and set edges
|
642
|
|
643
|
for (int j = Edge.BR; j >= 0; j--)
|
644
|
if (a - Cnk(j, x + 1) >= 0)
|
645
|
{
|
646
|
ep[j] = edge3[x];
|
647
|
a -= Cnk(j, x-- + 1);
|
648
|
}
|
649
|
}
|
650
|
|
651
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
652
|
// Permutation of the three edges UB,DR,DF
|
653
|
short getUBtoDF()
|
654
|
{
|
655
|
int a = 0, x = 0;
|
656
|
// compute the index a < (12 choose 3) and the edge permutation.
|
657
|
|
658
|
for (int j = Edge.UR; j <= Edge.BR; j++)
|
659
|
if (Edge.UB <= ep[j] && ep[j] <= Edge.DF)
|
660
|
{
|
661
|
a += Cnk(j, x + 1);
|
662
|
tmpEdge3[x++] = ep[j];
|
663
|
}
|
664
|
|
665
|
int b = 0;
|
666
|
|
667
|
for (int j = 2; j > 0; j--)// compute the index b < 3! for the permutation in edge3
|
668
|
{
|
669
|
int k = 0;
|
670
|
|
671
|
while (tmpEdge3[j] != Edge.UB + j)
|
672
|
{
|
673
|
rotateLeft(tmpEdge3, 0, j);
|
674
|
k++;
|
675
|
}
|
676
|
b = (j + 1) * b + k;
|
677
|
}
|
678
|
|
679
|
return (short) (6 * a + b);
|
680
|
}
|
681
|
|
682
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
683
|
void setUBtoDF(short idx)
|
684
|
{
|
685
|
int x;
|
686
|
int[] edge3 = { Edge.UB, Edge.DR, Edge.DF };
|
687
|
int b = idx % 6; // Permutation
|
688
|
int a = idx / 6; // Combination
|
689
|
|
690
|
for (int e = Edge.UR; e <= Edge.BR; e++) ep[e] = Edge.BR;// Use BR to invalidate all edges
|
691
|
|
692
|
for (int j = 1, k; j < 3; j++)// generate permutation from index b
|
693
|
{
|
694
|
k = b % (j + 1);
|
695
|
b /= j + 1;
|
696
|
|
697
|
while (k-- > 0) rotateRight(edge3, 0, j);
|
698
|
}
|
699
|
|
700
|
x = 2;// generate combination and set edges
|
701
|
|
702
|
for (int j = Edge.BR; j >= 0; j--)
|
703
|
if (a - Cnk(j, x + 1) >= 0)
|
704
|
{
|
705
|
ep[j] = edge3[x];
|
706
|
a -= Cnk(j, x-- + 1);
|
707
|
}
|
708
|
}
|
709
|
|
710
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
711
|
int getURFtoDLB()
|
712
|
{
|
713
|
int b = 0;
|
714
|
|
715
|
for (int i = 0; i < 8; i++) tmpCorner8[i] = cp[i];
|
716
|
|
717
|
for (int j = 7; j > 0; j--)// compute the index b < 8! for the permutation in perm
|
718
|
{
|
719
|
int k = 0;
|
720
|
while (tmpCorner8[j] != j)
|
721
|
{
|
722
|
rotateLeft(tmpCorner8, 0, j);
|
723
|
k++;
|
724
|
}
|
725
|
b = (j + 1) * b + k;
|
726
|
}
|
727
|
|
728
|
return b;
|
729
|
}
|
730
|
|
731
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
732
|
void setURFtoDLB(int idx)
|
733
|
{
|
734
|
int[] perm = { Corner.URF, Corner.UFL, Corner.ULB, Corner.UBR, Corner.DFR, Corner.DLF, Corner.DBL, Corner.DRB };
|
735
|
int k;
|
736
|
|
737
|
for (int j = 1; j < 8; j++)
|
738
|
{
|
739
|
k = idx % (j + 1);
|
740
|
idx /= j + 1;
|
741
|
while (k-- > 0) rotateRight(perm, 0, j);
|
742
|
}
|
743
|
|
744
|
int x = 7;// set corners
|
745
|
|
746
|
for (int j = 7; j >= 0; j--) cp[j] = perm[x--];
|
747
|
}
|
748
|
|
749
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
750
|
int getURtoBR()
|
751
|
{
|
752
|
int b = 0;
|
753
|
|
754
|
for (int i = 0; i < 12; i++) tmpEdge12[i] = ep[i];
|
755
|
|
756
|
for (int j = 11; j > 0; j--)// compute the index b < 12! for the permutation in perm
|
757
|
{
|
758
|
int k = 0;
|
759
|
|
760
|
while (tmpEdge12[j] != j)
|
761
|
{
|
762
|
rotateLeft(tmpEdge12, 0, j);
|
763
|
k++;
|
764
|
}
|
765
|
b = (j + 1) * b + k;
|
766
|
}
|
767
|
|
768
|
return b;
|
769
|
}
|
770
|
|
771
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
772
|
void setURtoBR(int idx)
|
773
|
{
|
774
|
int[] perm = { Edge.UR, Edge.UF, Edge.UL, Edge.UB, Edge.DR, Edge.DF, Edge.DL, Edge.DB, Edge.FR, Edge.FL, Edge.BL, Edge.BR };
|
775
|
int k;
|
776
|
|
777
|
for (int j = 1; j < 12; j++)
|
778
|
{
|
779
|
k = idx % (j + 1);
|
780
|
idx /= j + 1;
|
781
|
|
782
|
while (k-- > 0) rotateRight(perm, 0, j);
|
783
|
}
|
784
|
|
785
|
int x = 11;// set edges
|
786
|
|
787
|
for (int j = 11; j >= 0; j--) ep[j] = perm[x--];
|
788
|
}
|
789
|
|
790
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
791
|
// Check a cubiecube for solvability. Return the error code.
|
792
|
// 0: Cube is solvable
|
793
|
// -2: Not all 12 edges exist exactly once
|
794
|
// -3: Flip error: One edge has to be flipped
|
795
|
// -4: Not all corners exist exactly once
|
796
|
// -5: Twist error: One corner has to be twisted
|
797
|
// -6: Parity error: Two corners ore two edges have to be exchanged
|
798
|
int verify()
|
799
|
{
|
800
|
int sum = 0;
|
801
|
int[] edgeCount = new int[12];
|
802
|
|
803
|
for (int e = Edge.UR; e <= Edge.BR; e++) edgeCount[ep[e]]++;
|
804
|
|
805
|
for (int i = 0; i < 12; i++)
|
806
|
if (edgeCount[i] != 1)
|
807
|
return -2;
|
808
|
|
809
|
for (int i = 0; i < 12; i++)
|
810
|
sum += eo[i];
|
811
|
|
812
|
if (sum % 2 != 0)
|
813
|
return -3;
|
814
|
|
815
|
int[] cornerCount = new int[8];
|
816
|
|
817
|
for ( int c=Corner.URF; c<=Corner.DRB; c++) cornerCount[cp[c]]++;
|
818
|
|
819
|
for (int i = 0; i < 8; i++)
|
820
|
if (cornerCount[i] != 1)
|
821
|
return -4;// missing corners
|
822
|
|
823
|
sum = 0;
|
824
|
|
825
|
for (int i = 0; i < 8; i++)
|
826
|
sum += co[i];
|
827
|
|
828
|
if (sum % 3 != 0)
|
829
|
return -5;// twisted corner
|
830
|
|
831
|
if ((edgeParity() ^ cornerParity()) != 0)
|
832
|
return -6;// parity error
|
833
|
|
834
|
return 0;// cube ok
|
835
|
}
|
836
|
}
|