Skip to content

Instantly share code, notes, and snippets.

@LucasAlfare

LucasAlfare/sq12phase_FullCube.java

Created August 5, 2016 02:50
Show Gist options
  • Save LucasAlfare/660e5ffc7a4566d1f5d91362a41d5497 to your computer and use it in GitHub Desktop.
Save LucasAlfare/660e5ffc7a4566d1f5d91362a41d5497 to your computer and use it in GitHub Desktop.
Download ZIP
Square-1 "solver". I don't know how this works as well, so I'm saving this here to study along time. All credits to Cheng Shuang, or Chuang Cheng, I always make his name wrong, sorry. :(
Raw
sq12phase_FullCube.java
package cs.sq12phase;
import java.util.*;
public class FullCube implements Comparable<FullCube> {
int ul = 0x011233;
int ur = 0x455677;
int dl = 0x998bba;
int dr = 0xddcffe;
int ml = 0;
public int compareTo(FullCube f) {
if (ul != f.ul) {
return ul - f.ul;
}
if (ur != f.ur) {
return ur - f.ur;
}
if (dl != f.dl) {
return dl - f.dl;
}
if (dr != f.dr) {
return dr - f.dr;
}
return ml - f.ml;
}
FullCube(String s) {
//TODO
}
public FullCube() {
}
static Random r = new Random();
public static FullCube randomCube() {
return randomCube(r);
}
public static FullCube randomCube(Random r) {
int shape = Shape.ShapeIdx[r.nextInt(3678)];
FullCube f = new FullCube();
int corner = 0x01234567 << 1 | 0x11111111;
int edge = 0x01234567 << 1;
int n_corner = 8, n_edge = 8;
int rnd, m;
for (int i = 0; i < 24; i++) {
if (((shape >> i) & 1) == 0) {//edge
rnd = r.nextInt(n_edge) << 2;
f.setPiece(23 - i, (edge >> rnd) & 0xf);
m = (1 << rnd) - 1;
edge = (edge & m) + ((edge >> 4) & ~m);
--n_edge;
} else {//corner
rnd = r.nextInt(n_corner) << 2;
f.setPiece(23 - i, (corner >> rnd) & 0xf);
f.setPiece(22 - i, (corner >> rnd) & 0xf);
m = (1 << rnd) - 1;
corner = (corner & m) + ((corner >> 4) & ~m);
--n_corner;
++i;
}
}
f.ml = r.nextInt(2);
return f;
}
void copy(FullCube c) {
this.ul = c.ul;
this.ur = c.ur;
this.dl = c.dl;
this.dr = c.dr;
this.ml = c.ml;
}
/**
* @param move
* 0 = twist
* [1, 11] = top move
* [-1, -11] = bottom move
* for example, 6 == (6, 0), 9 == (-3, 0), -4 == (0, 4)
*/
void doMove(int move) {
move <<= 2;
if (move > 24) {
move = 48 - move;
int temp = ul;
ul = (ul >> move | ur << (24 - move)) & 0xffffff;
ur = (ur >> move | temp << (24 - move)) & 0xffffff;
} else if (move > 0) {
int temp = ul;
ul = (ul << move | ur >> (24 - move)) & 0xffffff;
ur = (ur << move | temp >> (24 - move)) & 0xffffff;
} else if (move == 0) {
int temp = ur;
ur = dl;
dl = temp;
ml = 1 - ml;
} else if (move >= -24) {
move = -move;
int temp = dl;
dl = (dl << move | dr >> (24 - move)) & 0xffffff;
dr = (dr << move | temp >> (24 - move)) & 0xffffff;
} else if (move < -24) {
move = 48 + move;
int temp = dl;
dl = (dl >> move | dr << (24 - move)) & 0xffffff;
dr = (dr >> move | temp << (24 - move)) & 0xffffff;
}
}
private byte pieceAt(int idx) {
int ret;
if (idx < 6) {
ret = ul >> ((5 - idx) << 2);
} else if (idx < 12) {
ret = ur >> ((11 - idx) << 2);
} else if (idx < 18) {
ret = dl >> ((17 - idx) << 2);
} else {
ret = dr >> ((23 - idx) << 2);
}
return (byte) (ret & 0x0f);
}
public void setPiece(int idx, int value) {
if (idx < 6) {
ul &= ~(0xf << ((5 - idx) << 2));
ul |= value << ((5 - idx) << 2);
} else if (idx < 12) {
ur &= ~(0xf << ((11 - idx) << 2));
ur |= value << ((11 - idx) << 2);
} else if (idx < 18) {
dl &= ~(0xf << ((17 - idx) << 2));
dl |= value << ((17 - idx) << 2);
} else if (idx < 24) {
dr &= ~(0xf << ((23 - idx) << 2));
dr |= value << ((23 - idx) << 2);
} else {
ml = value;
}
}
int[] arr = new int[16];
int getParity() {
int cnt = 0;
arr[0] = pieceAt(0);
for (int i = 1; i < 24; i++) {
if (pieceAt(i) != arr[cnt]) {
arr[++cnt] = pieceAt(i);
}
}
int p = 0;
for (int a = 0; a < 16; a++) {
for (int b = a + 1 ; b < 16 ; b++) {
if (arr[a] > arr[b]) {
p ^= 1;
}
}
}
return p;
}
boolean isTwistable() {
return pieceAt(0) != pieceAt(11)
&& pieceAt(5) != pieceAt(6)
&& pieceAt(12) != pieceAt(23)
&& pieceAt(17) != pieceAt(18);
}
int getShapeIdx() {
int urx = ur & 0x111111;
urx |= urx >> 3;
urx |= urx >> 6;
urx = (urx & 0xf) | ((urx >> 12) & 0x30);
int ulx = ul & 0x111111;
ulx |= ulx >> 3;
ulx |= ulx >> 6;
ulx = (ulx & 0xf) | ((ulx >> 12) & 0x30);
int drx = dr & 0x111111;
drx |= drx >> 3;
drx |= drx >> 6;
drx = (drx & 0xf) | ((drx >> 12) & 0x30);
int dlx = dl & 0x111111;
dlx |= dlx >> 3;
dlx |= dlx >> 6;
dlx = (dlx & 0xf) | ((dlx >> 12) & 0x30);
return Shape.getShape2Idx(getParity() << 24 | ulx << 18 | urx << 12 | dlx << 6 | drx);
}
void print() {
System.out.println(Integer.toHexString(ul));
System.out.println(Integer.toHexString(ur));
System.out.println(Integer.toHexString(dl));
System.out.println(Integer.toHexString(dr));
}
byte[] prm = new byte[8];
void getSquare(Square sq) {
for (int a = 0; a < 8; a++) {
prm[a] = (byte) (pieceAt(a * 3 + 1) >> 1);
}
//convert to number
sq.cornperm = Square.get8Perm(prm);
int a, b;
//Strip top layer edges
sq.topEdgeFirst = pieceAt(0) == pieceAt(1);
a = sq.topEdgeFirst ? 2 : 0;
for (b = 0; b < 4; a += 3, b++) {
prm[b] = (byte)(pieceAt(a) >> 1);
}
sq.botEdgeFirst = pieceAt(12) == pieceAt(13);
a = sq.botEdgeFirst ? 14 : 12;
for ( ; b < 8; a += 3, b++) {
prm[b] = (byte)(pieceAt(a) >> 1);
}
sq.edgeperm = Square.get8Perm(prm);
sq.ml = ml;
}
}
Raw
sq12phase_Search.java
package cs.sq12phase;
public class Search {
int[] move = new int[100];
FullCube c = null;
FullCube d = new FullCube("");
int length1;
int maxlen2;
String sol_string;
static int getNParity(int idx, int n) {
int p = 0;
for (int i = n - 2; i >= 0; i--) {
p ^= idx % (n - i);
idx /= (n - i);
}
return p & 1;
}
static {
Shape.init();
Square.init();
}
public String solution(FullCube c) {
this.c = c;
sol_string = null;
int shape = c.getShapeIdx();
for (length1 = Shape.ShapePrun[shape]; length1 < 100; length1++) {
maxlen2 = Math.min(31 - length1, 17);
if (phase1(shape, Shape.ShapePrun[shape], length1, 0, -1)) {
break;
}
}
return sol_string;
}
public String solutionOpt(FullCube c, int maxl) {
this.c = c;
sol_string = null;
int shape = c.getShapeIdx();
for (length1 = Shape.ShapePrunOpt[shape]; length1 <= maxl; length1++) {
if (phase1Opt(shape, Shape.ShapePrunOpt[shape], length1, 0, -1)) {
break;
}
}
return sol_string;
}
boolean phase1Opt(int shape, int prunvalue, int maxl, int depth, int lm) {
if (maxl == 0) {
return isSolvedInPhase1();
}
//try each possible move. First twist;
if (lm != 0) {
int shapex = Shape.TwistMove[shape];
int prunx = Shape.ShapePrunOpt[shapex];
if (prunx < maxl) {
move[depth] = 0;
if (phase1Opt(shapex, prunx, maxl - 1, depth + 1, 0)) {
return true;
}
}
}
//Try top layer
int shapex = shape;
if (lm <= 0) {
int m = 0;
while (true) {
m += Shape.TopMove[shapex];
shapex = m >> 4;
m &= 0xf;
if (m >= 12) {
break;
}
int prunx = Shape.ShapePrunOpt[shapex];
if (prunx > maxl) {
break;
} else if (prunx == maxl) {
continue;
}
move[depth] = m;
if (phase1Opt(shapex, prunx, maxl - 1, depth + 1, 1)) {
return true;
}
}
}
shapex = shape;
//Try bottom layer
if (lm <= 1) {
int m = 0;
while (true) {
m += Shape.BottomMove[shapex];
shapex = m >> 4;
m &= 0xf;
if (m >= 12) {
break;
}
int prunx = Shape.ShapePrunOpt[shapex];
if (prunx > maxl) {
break;
} else if (prunx < maxl) {
move[depth] = -m;
if (phase1Opt(shapex, prunx, maxl - 1, depth + 1, 2)) {
return true;
}
}
}
}
return false;
}
boolean phase1(int shape, int prunvalue, int maxl, int depth, int lm) {
if (prunvalue == 0 && maxl < 4) {
return maxl == 0 && init2();
}
//try each possible move. First twist;
if (lm != 0) {
int shapex = Shape.TwistMove[shape];
int prunx = Shape.ShapePrun[shapex];
if (prunx < maxl) {
move[depth] = 0;
if (phase1(shapex, prunx, maxl - 1, depth + 1, 0)) {
return true;
}
}
}
//Try top layer
int shapex = shape;
if (lm <= 0) {
int m = 0;
while (true) {
m += Shape.TopMove[shapex];
shapex = m >> 4;
m &= 0xf;
if (m >= 12) {
break;
}
int prunx = Shape.ShapePrun[shapex];
if (prunx > maxl) {
break;
} else if (prunx < maxl) {
move[depth] = m;
if (phase1(shapex, prunx, maxl - 1, depth + 1, 1)) {
return true;
}
}
}
}
shapex = shape;
//Try bottom layer
if (lm <= 1) {
int m = 0;
while (true) {
m += Shape.BottomMove[shapex];
shapex = m >> 4;
m &= 0xf;
if (m >= 6) {
break;
}
int prunx = Shape.ShapePrun[shapex];
if (prunx > maxl) {
break;
} else if (prunx < maxl) {
move[depth] = -m;
if (phase1(shapex, prunx, maxl - 1, depth + 1, 2)) {
return true;
}
}
}
}
return false;
}
int count = 0;
Square sq = new Square();
boolean isSolvedInPhase1() {
d.copy(c);
for (int i = 0; i < length1; i++) {
d.doMove(move[i]);
}
boolean isSolved = d.ul == 0x011233 && d.ur == 0x455677 && d.dl == 0x998bba && d.dr == 0xddcffe && d.ml == 0;
if (isSolved) {
sol_string = move2string(length1);
}
return isSolved;
}
boolean init2() {
d.copy(c);
for (int i = 0; i < length1; i++) {
d.doMove(move[i]);
}
assert Shape.ShapePrun[d.getShapeIdx()] == 0;
d.getSquare(sq);
int edge = sq.edgeperm;
int corner = sq.cornperm;
int ml = sq.ml;
int prun = Math.max(Square.SquarePrun[sq.edgeperm << 1 | ml], Square.SquarePrun[sq.cornperm << 1 | ml]);
for (int i = prun; i < maxlen2; i++) {
if (phase2(edge, corner, sq.topEdgeFirst, sq.botEdgeFirst, ml, i, length1, 0)) {
sol_string = move2string(i + length1);
return true;
}
}
return false;
}
int[] pruncomb = new int[100];
String move2string(int len) {
//TODO whether to invert the solution or not should be set by params.
StringBuffer s = new StringBuffer();
int top = 0, bottom = 0;
for (int i = len - 1; i >= 0; i--) {
int val = move[i];
if (val > 0) {
val = 12 - val;
top = (val > 6) ? (val - 12) : val;
} else if (val < 0) {
val = 12 + val;
bottom = (val > 6) ? (val - 12) : val;
} else {
if (top == 0 && bottom == 0) {
s.append(" / ");
} else {
s.append('(').append(top).append(",").append(bottom).append(") / ");
}
top = 0;
bottom = 0;
}
}
if (top == 0 && bottom == 0) {
} else {
s.append('(').append(top).append(",").append(bottom).append(")");
}
return s.toString();
}
boolean phase2(int edge, int corner, boolean topEdgeFirst, boolean botEdgeFirst, int ml, int maxl, int depth, int lm) {
if (maxl == 0 && !topEdgeFirst && botEdgeFirst) {
assert edge == 0 && corner == 0 && ml == 0;
return true;
}
//try each possible move. First twist;
if (lm != 0 && topEdgeFirst == botEdgeFirst) {
int edgex = Square.TwistMove[edge];
int cornerx = Square.TwistMove[corner];
if (Square.SquarePrun[edgex << 1 | (1 - ml)] < maxl && Square.SquarePrun[cornerx << 1 | (1 - ml)] < maxl) {
move[depth] = 0;
if (phase2(edgex, cornerx, topEdgeFirst, botEdgeFirst, 1 - ml, maxl - 1, depth + 1, 0)) {
return true;
}
}
}
//Try top layer
if (lm <= 0) {
boolean topEdgeFirstx = !topEdgeFirst;
int edgex = topEdgeFirstx ? Square.TopMove[edge] : edge;
int cornerx = topEdgeFirstx ? corner : Square.TopMove[corner];
int m = topEdgeFirstx ? 1 : 2;
int prun1 = Square.SquarePrun[edgex << 1 | ml];
int prun2 = Square.SquarePrun[cornerx << 1 | ml];
while (m < 12 && prun1 <= maxl && prun1 <= maxl) {
if (prun1 < maxl && prun2 < maxl) {
move[depth] = m;
if (phase2(edgex, cornerx, topEdgeFirstx, botEdgeFirst, ml, maxl - 1, depth + 1, 1)) {
return true;
}
}
topEdgeFirstx = !topEdgeFirstx;
if (topEdgeFirstx) {
edgex = Square.TopMove[edgex];
prun1 = Square.SquarePrun[edgex << 1 | ml];
m += 1;
} else {
cornerx = Square.TopMove[cornerx];
prun2 = Square.SquarePrun[cornerx << 1 | ml];
m += 2;
}
}
}
if (lm <= 1) {
boolean botEdgeFirstx = !botEdgeFirst;
int edgex = botEdgeFirstx ? Square.BottomMove[edge] : edge;
int cornerx = botEdgeFirstx ? corner : Square.BottomMove[corner];
int m = botEdgeFirstx ? 1 : 2;
int prun1 = Square.SquarePrun[edgex << 1 | ml];
int prun2 = Square.SquarePrun[cornerx << 1 | ml];
while (m < (maxl > 6 ? 6 : 12) && prun1 <= maxl && prun1 <= maxl) {
if (prun1 < maxl && prun2 < maxl) {
move[depth] = -m;
if (phase2(edgex, cornerx, topEdgeFirst, botEdgeFirstx, ml, maxl - 1, depth + 1, 2)) {
return true;
}
}
botEdgeFirstx = !botEdgeFirstx;
if (botEdgeFirstx) {
edgex = Square.BottomMove[edgex];
prun1 = Square.SquarePrun[edgex << 1 | ml];
m += 1;
} else {
cornerx = Square.BottomMove[cornerx];
prun2 = Square.SquarePrun[cornerx << 1 | ml];
m += 2;
}
}
}
return false;
}
}
Raw
sq12phase_SearchTest.java
package cs.sq12phase;
import java.util.Random;
public class SearchTest {
static void scramble(FullCube f, int moves, java.util.Random gen) {
int shape = f.getShapeIdx();
int m = 0;
for (int i = 0; i < moves; i++) {
int r = gen.nextInt(3);
if (r == 0) {
shape = Shape.TwistMove[shape];
f.doMove(0);
m = 0;
} else if (r == 1) {
m = Shape.TopMove[shape];
shape = m >> 4;
m &= 0xf;
f.doMove(m);
} else if (r == 2) {
m = Shape.BottomMove[shape];
shape = m >> 4;
m &= 0xf;
m = -m;
f.doMove(m);
}
assert shape == f.getShapeIdx();
// System.out.println(m);
// System.out.println("\t\t" + Shape.ShapePrunOpt[shape]);
}
}
/*
public static void main(String[] args) {
long t = System.nanoTime();
new Search().solution(new FullCube(""));
System.out.println((System.nanoTime() - t) / 1e9 + " seconds to initialize");
t = System.nanoTime();
Search s = new Search();
java.util.Random gen = new java.util.Random(4L);
FullCube f;
long tt = System.nanoTime();
int MAXL = 15;
for (int i = 0; i < 1; i++) {
f = new FullCube();
scramble(f, 15, gen);
String str = s.solutionOpt(f, MAXL);
// System.out.print(s.length1 + " ");
System.out.print(String.format("AvgTime: %6.3f ms\r", (System.nanoTime() - t) / 1e6 / (i + 1)));
}
System.out.println();
for (int x = 0; x < 1; x++) {
System.out.println(s.solution(FullCube.randomCube()));
System.out.print(String.format("AvgTime: %6.3f ms\r", (System.nanoTime() - t) / 1e6 / (x + 1)));
}
System.out.println();
}
*/
}
Raw
sq12phase_Shape.java
package cs.sq12phase;
import java.util.Arrays;
class Shape {
//1 = corner, 0 = edge.
static int[] halflayer = {0x00, 0x03, 0x06, 0x0c, 0x0f, 0x18, 0x1b, 0x1e,
0x30, 0x33, 0x36, 0x3c, 0x3f
};
static int[] ShapeIdx = new int[3678];
static int[] ShapePrun = new int[3768 * 2];
static int[] ShapePrunOpt = new int[3768 * 2];
static int[] TopMove = new int[3678 * 2];
static int[] BottomMove = new int[3678 * 2];
static int[] TwistMove = new int[3678 * 2];
private Shape() {}
int top;
int bottom;
int parity;
static int getShape2Idx(int shp) {
int ret = Arrays.binarySearch(ShapeIdx, shp & 0xffffff) << 1 | shp >> 24;
return ret;
}
int getIdx() {
int ret = Arrays.binarySearch(ShapeIdx, top << 12 | bottom) << 1 | parity;
return ret;
}
void setIdx(int idx) {
parity = idx & 1;
top = ShapeIdx[idx >> 1];
bottom = top & 0xfff;
top >>= 12;
}
int topMove() {
int move = 0;
int moveParity = 0;
do {
if ((top & 0x800) == 0) {
move += 1;
top = top << 1;
} else {
move += 2;
top = (top << 2) ^ 0x3003;
}
moveParity = 1 - moveParity;
} while ((Integer.bitCount(top & 0x3f) & 1) != 0);
if ((Integer.bitCount(top) & 2) == 0) {
parity ^= moveParity;
}
return move;
}
int bottomMove() {
int move = 0;
int moveParity = 0;
do {
if ((bottom & 0x800) == 0) {
move += 1;
bottom = bottom << 1;
} else {
move += 2;
bottom = (bottom << 2) ^ 0x3003;
}
moveParity = 1 - moveParity;
} while ((Integer.bitCount(bottom & 0x3f) & 1) != 0);
if ((Integer.bitCount(bottom) & 2) == 0) {
parity ^= moveParity;
}
return move;
}
void twistMove() {
int temp = top & 0x3f;
int p1 = Integer.bitCount(temp);
int p3 = Integer.bitCount(bottom & 0xfc0);
parity ^= 1 & ((p1 & p3) >> 1);
top = (top & 0xfc0) | ((bottom >> 6) & 0x3f);
bottom = (bottom & 0x3f) | temp << 6;
}
static boolean inited = false;
static void init() {
if (inited) {
return;
}
int count = 0;
for (int i = 0; i < 13 * 13 * 13 * 13; i++) {
int dr = halflayer[i % 13];
int dl = halflayer[i / 13 % 13];
int ur = halflayer[i / 13 / 13 % 13];
int ul = halflayer[i / 13 / 13 / 13];
int value = ul << 18 | ur << 12 | dl << 6 | dr;
if (Integer.bitCount(value) == 16) {
ShapeIdx[count++] = value;
}
}
// System.out.println(count);
Shape s = new Shape();
for (int i = 0; i < 3678 * 2; i++) {
s.setIdx(i);
TopMove[i] = s.topMove();
TopMove[i] |= s.getIdx() << 4;
s.setIdx(i);
BottomMove[i] = s.bottomMove();
BottomMove[i] |= s.getIdx() << 4;
s.setIdx(i);
s.twistMove();
TwistMove[i] = s.getIdx();
}
for (int i = 0; i < 3768 * 2; i++) {
ShapePrun[i] = -1;
ShapePrunOpt[i] = -1;
}
//0 110110110110 011011011011
//1 110110110110 110110110110
//1 011011011011 011011011011
//0 011011011011 110110110110
ShapePrun[getShape2Idx(0x0db66db)] = 0;
ShapePrun[getShape2Idx(0x1db6db6)] = 0;
ShapePrun[getShape2Idx(0x16db6db)] = 0;
ShapePrun[getShape2Idx(0x06dbdb6)] = 0;
ShapePrunOpt[new FullCube().getShapeIdx()] = 0;
int done = 4;
int done0 = 0;
int depth = -1;
while (done != done0) {
done0 = done;
++depth;
// System.out.println(done);
for (int i = 0; i < 3768 * 2; i++) {
if (ShapePrun[i] == depth) {
// try top
int m = 0;
int idx = i;
do {
idx = TopMove[idx];
m += idx & 0xf;
idx >>= 4;
if (ShapePrun[idx] == -1) {
++done;
ShapePrun[idx] = depth + 1;
}
} while (m != 12);
// try bottom
m = 0;
idx = i;
do {
idx = BottomMove[idx];
m += idx & 0xf;
idx >>= 4;
if (ShapePrun[idx] == -1) {
++done;
ShapePrun[idx] = depth + 1;
}
} while (m != 12);
// try twist
idx = TwistMove[i];
if (ShapePrun[idx] == -1) {
++done;
ShapePrun[idx] = depth + 1;
}
}
}
}
done = 1;
done0 = 0;
depth = -1;
while (done != done0) {
done0 = done;
++depth;
// System.out.println(done);
for (int i = 0; i < 3768 * 2; i++) {
if (ShapePrunOpt[i] == depth) {
// try top
int m = 0;
int idx = i;
do {
idx = TopMove[idx];
m += idx & 0xf;
idx >>= 4;
if (ShapePrunOpt[idx] == -1) {
++done;
ShapePrunOpt[idx] = depth + 1;
}
} while (m != 12);
// try bottom
m = 0;
idx = i;
do {
idx = BottomMove[idx];
m += idx & 0xf;
idx >>= 4;
if (ShapePrunOpt[idx] == -1) {
++done;
ShapePrunOpt[idx] = depth + 1;
}
} while (m != 12);
// try twist
idx = TwistMove[i];
if (ShapePrunOpt[idx] == -1) {
++done;
ShapePrunOpt[idx] = depth + 1;
}
}
}
}
inited = true;
}
}
Raw
sq12phase_Square.java
package cs.sq12phase;
class Square {
int edgeperm; //number encoding the edge permutation 0-40319
int cornperm; //number encoding the corner permutation 0-40319
boolean topEdgeFirst; //true if top layer starts with edge left of seam
boolean botEdgeFirst; //true if bottom layer starts with edge right of seam
int ml; //shape of middle layer (+/-1, or 0 if ignored)
static byte[] SquarePrun = new byte[40320 * 2]; //pruning table; #twists to solve corner|edge permutation
static char[] TwistMove = new char[40320]; //transition table for twists
static char[] TopMove = new char[40320]; //transition table for top layer turns
static char[] BottomMove = new char[40320]; //transition table for bottom layer turns
private static int[] fact = {1, 1, 2, 6, 24, 120, 720, 5040};
static void set8Perm(byte[] arr, int idx) {
int val = 0x76543210;
for (int i = 0; i < 7; i++) {
int p = fact[7 - i];
int v = idx / p;
idx -= v * p;
v <<= 2;
arr[i] = (byte) ((val >> v) & 07);
int m = (1 << v) - 1;
val = (val & m) + ((val >> 4) & ~m);
}
arr[7] = (byte)val;
}
static char get8Perm(byte[] arr) {
int idx = 0;
int val = 0x76543210;
for (int i = 0; i < 7; i++) {
int v = arr[i] << 2;
idx = (8 - i) * idx + ((val >> v) & 07);
val -= 0x11111110 << v;
}
return (char)idx;
}
static int[][] Cnk = new int[12][12];
static int get8Comb(byte[] arr) {
int idx = 0, r = 4;
for (int i = 0; i < 8; i++) {
if (arr[i] >= 4) {
idx += Cnk[7 - i][r--];
}
}
return idx;
}
static boolean inited = false;
static void init() {
if (inited) {
return;
}
for (int i = 0; i < 12; i++) {
Cnk[i][0] = 1;
Cnk[i][i] = 1;
for (int j = 1; j < i; j++) {
Cnk[i][j] = Cnk[i - 1][j - 1] + Cnk[i - 1][j];
}
}
byte[] pos = new byte[8];
byte temp;
for (int i = 0; i < 40320; i++) {
//twist
set8Perm(pos, i);
temp = pos[2]; pos[2] = pos[4]; pos[4] = temp;
temp = pos[3]; pos[3] = pos[5]; pos[5] = temp;
TwistMove[i] = get8Perm(pos);
//top layer turn
set8Perm(pos, i);
temp = pos[0]; pos[0] = pos[1]; pos[1] = pos[2]; pos[2] = pos[3]; pos[3] = temp;
TopMove[i] = get8Perm(pos);
//bottom layer turn
set8Perm(pos, i);
temp = pos[4]; pos[4] = pos[5]; pos[5] = pos[6]; pos[6] = pos[7]; pos[7] = temp;
BottomMove[i] = get8Perm(pos);
}
for (int i = 0; i < 40320 * 2; i++) {
SquarePrun[i] = -1;
}
SquarePrun[0] = 0;
int depth = 0;
int done = 1;
while (done < 40320 * 2) {
boolean inv = depth >= 11;
int find = inv ? -1 : depth;
int check = inv ? depth : -1;
++depth;
OUT:
for (int i = 0; i < 40320 * 2; i++) {
if (SquarePrun[i] == find) {
int idx = i >> 1;
int ml = i & 1;
//try twist
int idxx = TwistMove[idx] << 1 | (1 - ml);
if (SquarePrun[idxx] == check) {
++done;
SquarePrun[inv ? i : idxx] = (byte) (depth);
if (inv) {
continue OUT;
}
}
//try turning top layer
idxx = idx;
for (int m = 0; m < 4; m++) {
idxx = TopMove[idxx];
if (SquarePrun[idxx << 1 | ml] == check) {
++done;
SquarePrun[inv ? i : (idxx << 1 | ml)] = (byte) (depth);
if (inv) {
continue OUT;
}
}
}
assert idxx == idx;
//try turning bottom layer
for (int m = 0; m < 4; m++) {
idxx = BottomMove[idxx];
if (SquarePrun[idxx << 1 | ml] == check) {
++done;
SquarePrun[inv ? i : (idxx << 1 | ml)] = (byte) (depth);
if (inv) {
continue OUT;
}
}
}
}
}
// System.out.print(depth);
// System.out.print('\t');
// System.out.println(done);
}
inited = true;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment