5×5 Loopover pseudo-two-phase GN calculations

Phase1E.java

package loopsolver.fivetwophase;

import java.util.Arrays;

import loopsolver.BasicSolver5;
import loopsolver.IntList;
import loopsolver.Util;

public class Phase1E {

	private static boolean initialised = false;

	private static int[][] movePermutations = new int[40][];
	private static int[][] movePermutationsInv = new int[40][];
	static {
		for (int i = 0; i < 5; i++) {
			int[][] cycleRow = {{5*i+4, 5*i+3, 5*i+2, 5*i+1, 5*i+0}};
			movePermutations[i] = Util.generatePermutation(cycleRow, 25);
			int[][] cycleCol = {{i+20, i+15, i+10, i+5, i+0}};
			movePermutations[i+5] = Util.generatePermutation(cycleCol, 25);
		}
		for (int i = 0; i < 10; i++) {
			int[] p = movePermutations[i];
			int[] p2 = Util.compose(p, p);
			movePermutationsInv[i+30] = p;
			movePermutationsInv[i+20] = movePermutations[i+10] = p2;
			movePermutationsInv[i+10] = movePermutations[i+20] = Util.invert(p2);
			movePermutationsInv[i] = movePermutations[i+30] = Util.invert(p);
		}
	}

	private static final int ABCFGH_THRESHOLD = 5;

	private static int numAbcfghStates;
	private static int[] abcfghIndices;
	private static int[][] abcfghStates;
	private static int[][] abcfghMoveTable;
	private static byte[] ptableCombined;

	private static byte[] ptableAbcfgh;

	public static void initialise() {
		if (initialised) {return;}

		Phase1.initialise();
		ptableAbcfgh = Phase1.ptable;

		IntList indexList = new IntList();
		for (int i = 0; i < ptableAbcfgh.length; i++) {
			if (ptableAbcfgh[i] <= ABCFGH_THRESHOLD) {
				indexList.add(i);
			}
		}
		abcfghIndices = indexList.toArray();
		numAbcfghStates = abcfghIndices.length;
		abcfghStates = new int[numAbcfghStates][6];
		for (int i = 0; i < numAbcfghStates; i++) {
			int locs = Phase1.decode(abcfghIndices[i]);
			for (int j = 0; j < 6; j++) {
				abcfghStates[i][j] = (locs >> (5*j)) & 31;
			}
		}

		abcfghMoveTable = new int[numAbcfghStates][40];
		for (int i = 0; i < numAbcfghStates; i++) {
			for (int m = 0; m < 40; m++) {
				int[] locs = Util.compose(movePermutationsInv[m], abcfghStates[i]);
				int index = Phase1.encode(locs[0], locs[1], locs[2], locs[3], locs[4], locs[5]);
				if (ptableAbcfgh[index] > ABCFGH_THRESHOLD) {
					abcfghMoveTable[i][m] = -1; // -1 = illegal move
					continue;
				}
				int reducedIndex = Arrays.binarySearch(abcfghIndices, index);
				abcfghMoveTable[i][m] = reducedIndex;
			}
			for (int m = 10; m < 30; m++) {
				// for the double-tile moves, check if the intermediate state by moving one tile
				// is legal. (we don't allow "jumping over" illegal states.)
				if (m < 20) {
					if (abcfghMoveTable[i][m-10] == -1 && abcfghMoveTable[i][m] != -1) {
						abcfghMoveTable[i][m] = -1;
					}
				}
				else {
					if (abcfghMoveTable[i][m+10] == -1 && abcfghMoveTable[i][m] != -1) {
						abcfghMoveTable[i][m] = -1;
					}
				}
			}
		}

		ptableCombined = new byte[numAbcfghStates * 25*25*25];
		for (int i = 0; i < ptableCombined.length; i++) {ptableCombined[i] = -1;}
		ptableCombined[encodeReducedIndex(0,1,2,5,6,7) + numAbcfghStates * (10 + 25*11 + 25*25*12)] = 0;

		int distance = 0;
		while (true) {
			boolean changed = false;
			int count = 0;
			for (int index = 0; index < ptableCombined.length; index++) {
				if (ptableCombined[index] != distance) {continue;}
				count++;
				int abcfghIndex = index % numAbcfghStates;
				int klm = index / numAbcfghStates;
				for (int moveIndex = 30; moveIndex < 50; moveIndex++) {
					int adjustedMoveIndex = moveIndex % 40;
					if (abcfghMoveTable[abcfghIndex][adjustedMoveIndex] == -1) {continue;}
					int newAbcfghIndex = abcfghMoveTable[abcfghIndex][adjustedMoveIndex];
					int k = movePermutationsInv[adjustedMoveIndex][klm % 25];
					int l = movePermutationsInv[adjustedMoveIndex][klm / 25 % 25];
					int m = movePermutationsInv[adjustedMoveIndex][klm / 25 / 25];
					int newIndex = newAbcfghIndex + numAbcfghStates * (k + 25*l + 25*25*m);
					if (ptableCombined[newIndex] == -1) {
						changed = true;
						ptableCombined[newIndex] = (byte) (distance+1);
					}
				}
			}
			System.out.printf("distance %d: %d nodes\n", distance, count);
			distance++;
			if (!changed) {break;}
		}

		initialised = true;
	}

	private static int encodeReducedIndex(int... locs) {
		int index = Phase1.encode(locs[0], locs[1], locs[2], locs[3], locs[4], locs[5]);
		return Arrays.binarySearch(abcfghIndices, index);
	}

	private static void printStats(byte[] ptable) {
		int unreachable = 0;
		long[] counts = new long[256];
		for (int i = 0; i < ptable.length; i++) {
			if (ptable[i] == -1) unreachable++;
			else counts[ptable[i]]++;
		}
		System.out.printf("total states: %d (%d legal)\n", ptable.length, ptable.length-unreachable);
		long sum = 0;
		for (int i = 0; i < 256 && counts[i] > 0; i++) {
			System.out.printf("distance %d: %d nodes\n", i, counts[i]);
			sum += counts[i] * i;
		}
		System.out.printf("average distance: %.6f\n", (double)sum / (double)(ptable.length-unreachable));
	}

	public static void main(String[] args) {
		initialise();
		//printStats(ptableCombined);
		
		int[] histogram = new int[20];
		for (int i = 0; i < ptableCombined.length; i++) {
			if (ptableCombined[i] == 15) {
				int[] state = new int[25];
				for (int j = 0; j < 25; j++) {state[j] = 24;}
				int abcfghIndex = i % numAbcfghStates;
				int klm = i / numAbcfghStates;
				for (int j = 0; j < 6; j++) {
					state[abcfghStates[abcfghIndex][j]] = j/3*5 + j%3;
				}
				state[klm % 25] = 10;
				state[klm / 25 % 25] = 11;
				state[klm / 25 / 25] = 12;
				Phase1.prettyprint(state);
				int[] sol = Phase1.solve(state, 1);
				histogram[BasicSolver5.weightedLength(sol)]++;
			}
		}
		for (int i = 0; i < histogram.length; i++) {
			System.out.printf("%d\t%d\n", i, histogram[i]);
		}
	}

}

Phase2E.java

package loopsolver.fivetwophase;

import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.Random;

import loopsolver.IntList;
import loopsolver.Util;

public class Phase2E {

	private static boolean initialised = false;

	private static int[] encodeRow, decodeRow;
	private static int[] encodeBlock, decodeBlock;

	private static final int N_ROW = 192;
	private static final int N_BLOCK = 58574;
	private static final int N_BLOCKROW = N_BLOCK * N_ROW; // = 11246208

	//private static final int[] FIVE = {1, 5, 5*5, 5*5*5, 5*5*5*5, 5*5*5*5*5, 5*5*5*5*5*5};
	private static final int[] EIGHT = {1, 1<<3, 1<<6, 1<<9, 1<<12, 1<<15, 1<<18};

	private static byte[] ptable;

	private static final boolean[] KEEP = {
			false, false, false, true, true,
			false, false, false, true, true,
			false, false, false, true, true,
			true, true, true, true, true,
			true, true, true, true, true,
	};

	// translating from the move numbering here to what's used in the optimal solver
	private static final int[] MOVE_MAPPING = {
			3, 13, 23, 33, // 4U, 4U2, 4U2', 4U'
			4, 14, 24, 34, // 5U, 5U2, 5U2', 5U'
			8, 18, 28, 38, // 4L, 4L2, 4L2', 4L'
			9, 19, 29, 39, // 5L, 5L2, 5L2', 5L'
	};

	private static final int[] WEIGHTS = {1,2,2,1, 1,2,2,1, 1,2,2,1, 1,2,2,1};

	private static int[][] movePermutations;

	private static final int[] WHICH_ROW = {
			/*    */ 0, 1,
			/*    */ 2, 3,
			/*    */ 4, 5,
			6, 6, 6, 6, 6,
			7, 7, 7, 7, 7,
	};
	private static final int[] WHICH_COL = {
			/*    */ 6, 7,
			/*    */ 6, 7,
			/*    */ 6, 7,
			0, 2, 4, 6, 7,
			1, 3, 5, 6, 7,
	};

	private static byte[] ptableSeven;
	private static final int P16_7 = 57657600; // 16!/9!

	private static final int[] flipHV = {
			/*        */ 5,  4,
			/*        */ 3,  2,
			/*        */ 1,  0,
			13, 12, 11, 15, 14,
			8,   7,  6, 10,  9,
	};

	private static final int[] flipH = {
			/*        */ 1,  0,
			/*        */ 3,  2,
			/*        */ 5,  4,
			8,   7,  6, 10,  9,
			13, 12, 11, 15, 14,
	};

	private static final int[] flipV = Util.compose(flipHV, flipH);
	
	private static final int[] transpose = {
			/*     */ 6, 11,
			/*     */ 7, 12,
			/*     */ 8, 13,
			0, 2, 4,  9, 14,
			1, 3, 5, 10, 15,
	};
	
	private static final int[][] symmetries = {
			flipH, flipV, flipHV,
//			transpose,
//			Util.compose(transpose, flipH),
//			Util.compose(transpose, flipV),
//			Util.compose(transpose, flipHV)
			};
	private static final int[][] symmetriesInverse = {
			flipH, flipV, flipHV,
//			transpose,
//			symmetries[5],
//			symmetries[4],
//			symmetries[6],
	};

	private static int[][] lrlcStates, evenPermutations9;
	private static int[][] lrlcSolutions;
	private static int[] lrlcLengths;

	private static final boolean[] lrlckeep = {
			/*                */ false, true,
			/*                */ false, true,
			/*                */ false, true,
			false, false, false, false, true,
			true,  true,  true,  true,  true,
	};

	private static final int HALFFACT9 = Util.factorial(9)/2; // = 181440

	public static void initialise() {

		if (initialised) {return;}

		encodeRow = new int[EIGHT[5]];
		decodeRow = new int[N_ROW];
		for (int index = 0, j = 0; index < EIGHT[5]; index++) {
			int x0 = getOctalDigit(index, 0);
			int x1 = getOctalDigit(index, 1);
			int x2 = getOctalDigit(index, 2);
			int x3 = getOctalDigit(index, 3);
			int x4 = getOctalDigit(index, 4);
			int counts = (1 << (x0*4)) + (1 << (x1*4)) + (1 << (x2*4)) + (1 << (x3*4)) + (1 << (x4*4));
			if (
					(counts & 15) > 1 || ((counts >>> 4) & 15) > 1 || ((counts >>> 8) & 15) > 1 ||
					((counts >>> 12) & 15) > 1 || ((counts >>> 16) & 15) > 1 || ((counts >>> 20) & 15) > 1
					) {continue;}
			if (x0 < x1 || x1 < x2 || x2 < x3 || x3 < x4) {
				int y4 = Integer.numberOfTrailingZeros(counts)/4;
				counts -= 1 << (y4*4);
				int y3 = Integer.numberOfTrailingZeros(counts)/4;
				counts -= 1 << (y3*4);
				int y2 = Integer.numberOfTrailingZeros(counts)/4;
				counts -= 1 << (y2*4);
				int y1 = Integer.numberOfTrailingZeros(counts)/4;
				counts -= 1 << (y1*4);
				int y0 = Integer.numberOfTrailingZeros(counts)/4;
				int indexSorted = y0 + (y1<<3) + (y2<<6) + (y3<<9) + (y4<<12);
				encodeRow[index] = encodeRow[indexSorted];
				//System.out.printf("raw:    %d %d %d %d %d\nsorted: %d %d %d %d %d\nindex: %d\n\n",x0,x1,x2,x3,x4,y0,y1,y2,y3,y4,encodeRow[index]);
			}
			else {
				encodeRow[index] = j;
				decodeRow[j] = index;
				//System.out.printf("%d %d %d %d %d %d\n", x0, x1, x2, x3, x4, j);
				j++;
			}
		}

		encodeBlock = new int[EIGHT[6]];
		decodeBlock = new int[N_BLOCK];
		for (int index = 0, j = 0; index < EIGHT[6]; index++) {
			int x0 = getOctalDigit(index, 0);
			int x1 = getOctalDigit(index, 1);
			int x2 = getOctalDigit(index, 2);
			int x3 = getOctalDigit(index, 3);
			int x4 = getOctalDigit(index, 4);
			int x5 = getOctalDigit(index, 5);
			int counts = (1 << (x0*4)) + (1 << (x1*4)) + (1 << (x2*4)) + (1 << (x3*4)) + (1 << (x4*4)) + (1 << (x5*4));
			if (
					(counts & 15) > 1 || ((counts >>> 4) & 15) > 1 || ((counts >>> 8) & 15) > 1 ||
					((counts >>> 12) & 15) > 1 || ((counts >>> 16) & 15) > 1 || ((counts >>> 20) & 15) > 1 ||
					((counts >>> 24) & 15) > 5 || ((counts >>> 28) & 15) > 5
					) {continue;}
			//int left = x0 + (x2<<6) + (x4<<12);
			//int right = x1 + (x3<<6) + (x5<<12); // = (index-left) / 8
			//if (left < right) {
			//	encodeBlock[index] = encodeBlock[right + 8*left];
			//}
			else {
				encodeBlock[index] = j;
				decodeBlock[j] = index;
				//System.out.printf("%d %d %d %d %d %d %d\n", x0, x1, x2, x3, x4, x5, j);
				j++;
			}
		}

		ptable = new byte[N_BLOCKROW];
		for (int i = 0; i < ptable.length; i++) {ptable[i] = -1;}
		int solvedIndex = encodeBlock[0543210]
				+ N_BLOCK * encodeRow[066666];
		ptable[solvedIndex] = 0;

		{
			int distance = 0;
			while (true) {
				boolean changed = false;
				@SuppressWarnings("unused")
				int count = 0;
				for (int index = 0; index < N_BLOCKROW; index++) {
					if (ptable[index] != distance) {continue;}
					count++;

					int blockIndex = index % N_BLOCK;
					int rowIndex = index / N_BLOCK;
					int block = decodeBlock[blockIndex];
					int row3 = decodeRow[rowIndex];
					int row4 = 0;
					int counts = 0x55111111;
					for (int i = 0; i < 6; i++) {
						counts -= 1 << (((block / EIGHT[i]) % 8) * 4);
					}
					for (int i = 0; i < 5; i++) {
						counts -= 1 << (((row3 / EIGHT[i]) % 8) * 4);
					}
					for (int i = 0; i < 5; i++) {
						int value = Integer.numberOfTrailingZeros(counts)/4;
						counts -= 1 << (4*value);
						row4 += value * EIGHT[4-i]; // doesn't really matter whether we use i or 4-i here
					}
					if (counts != 0) {
						System.out.print(index);
						System.out.println("something happened");
					}
					int row0 = block % EIGHT[2];
					int row1 = (block / EIGHT[2]) % EIGHT[2];
					int row2 = block / EIGHT[4];
					for (int i0 = 0; i0 < 2; i0++) {
						int i1 = i0, i2 = i0;
						int x0 = getOctalDigit(row0, i0);
						int x1 = getOctalDigit(row1, i1);
						int x2 = getOctalDigit(row2, i2);
						for (int i3 = 0; i3 < 5; i3++) {
							int x3 = getOctalDigit(row3, i3);
							for (int i4 = 0; i4 < 5; i4++) {
								int x4 = getOctalDigit(row4, i4);

								int blockUp = setOctalDigit(row0, i0, x1)
										+ EIGHT[2]*setOctalDigit(row1, i1, x2)
										+ EIGHT[4]*setOctalDigit(row2, i2, x3);
								int rowUp = setOctalDigit(row3, i3, x4);
								int indexUp = encodeBlock[blockUp] + N_BLOCK * encodeRow[rowUp];
								if (ptable[indexUp] == -1) {
									ptable[indexUp] = (byte) (distance+1);
									changed = true;
								}

								int blockDown = setOctalDigit(row0, i0, x4)
										+ EIGHT[2]*setOctalDigit(row1, i1, x0)
										+ EIGHT[4]*setOctalDigit(row2, i2, x1);
								int rowDown = setOctalDigit(row3, i3, x2);
								int indexDown = encodeBlock[blockDown] + N_BLOCK * encodeRow[rowDown];
								if (ptable[indexDown] == -1) {
									ptable[indexDown] = (byte) (distance+1);
									changed = true;
								}
							}
						}
					}
				}
				//System.out.printf("distance %d: %d nodes\n", distance, count);
				distance++;
				if (!changed) {break;}
			}
		}
		/* WD pruning table distribution:
		 * distance 0: 1 nodes
		 * distance 1: 4 nodes
		 * distance 2: 51 nodes
		 * distance 3: 556 nodes
		 * distance 4: 5601 nodes
		 * distance 5: 46030 nodes
		 * distance 6: 268903 nodes
		 * distance 7: 701515 nodes
		 * distance 8: 361993 nodes
		 * distance 9: 43550 nodes
		 * distance 10: 2036 nodes
		 * distance 11: 82 nodes
		 * distance 12: 6 nodes
		 */

		movePermutations = new int[16][];
		movePermutations[0] = new int[]{0,1, 2,3, 4,5, 10,6,7,8,9, 11,12,13,14,15};
		movePermutations[4] = new int[]{0,1, 2,3, 4,5, 6,7,8,9,10, 15,11,12,13,14};
		movePermutations[8] = new int[]{14,1, 0,3, 2,5, 6,7,8,4,10, 11,12,13,9,15};
		movePermutations[12] = new int[]{0,15, 2,1, 4,3, 6,7,8,9,5, 11,12,13,14,10};
		for (int m = 0; m < 16; m += 4) {
			int[] p = movePermutations[m];
			int[] p2 = Util.compose(p, p);
			int[] p3 = Util.invert(p2);
			int[] p4 = Util.invert(p);
			movePermutations[m+1] = p2;
			movePermutations[m+2] = p3;
			movePermutations[m+3] = p4;
		}

		ptableSeven = new byte[P16_7];
		for (int i = 0; i < P16_7; i++) {ptableSeven[i] = -1;}
		ptableSeven[partialPermutationToIndex(0x6789420)] = 0;
		{
			int distance = 0;
			while (true) {
				boolean changed = false;
				int count = 0;
				for (int index = 0; index < P16_7; index++) {
					if (ptableSeven[index] != distance) {continue;}
					count++;
					long p = indexToPartialPermutation(index);
					for (int m = 0; m < 16; m += 4) {
						int newIndex = partialPermutationToIndex(Util.compose16(movePermutations[m], p) & 0xfffffff);
						if (ptableSeven[newIndex] == -1) {
							ptableSeven[newIndex] = (byte) (distance+1);
							changed = true;
						}
						newIndex = partialPermutationToIndex(Util.compose16(movePermutations[m+3], p) & 0xfffffff);
						if (ptableSeven[newIndex] == -1) {
							ptableSeven[newIndex] = (byte) (distance+1);
							changed = true;
						}
					}
				}
				System.out.printf("distance %d: %d nodes\n", distance, count);
				distance++;
				if (!changed) {break;}
			}
		}

		evenPermutations9 = new int[HALFFACT9][];
		lrlcStates = new int[HALFFACT9][];
		lrlcSolutions = new int[HALFFACT9][];
		lrlcLengths = new int[HALFFACT9];
		for (int i = 0; i < HALFFACT9; i++) {
			long p9packed = indexToEvenPermutation9(i);
			int[] p9 = new int[9];
			for (int j = 0; j < 9; j++) {p9[j] = (int) ((p9packed >> (4*j)) & 15);}
			evenPermutations9[i] = p9;
			int[] p = Util.unreducePermutation(p9, lrlckeep);
			lrlcStates[i] = p;
			int[] sol = solve(p, 0);
			lrlcSolutions[i] = sol;
			lrlcLengths[i] = weightedLength(sol);
		}

		initialised = true;
	}

	private static long indexToPartialPermutation(int ind) {
		// partial permutation of 7 items out of 16
		long p = 0, P = 0;
		for (int i = 10; i < 16; i++) {
			p |= ind % i;
			p <<= 4;
			ind /= i;
		}
		p |= ind;

		long unused = 0xfedcba9876543210L;
		for (int i = 0; i < 7; i++) {
			long a = (p >> (4*i)) & 15;
			long a4 = a << 2;
			P |= ((unused >> a4) & 15) << (4*i);
			unused = (unused & ((1L << a4) - 1)) | ((unused >> (a4+4)) << a4);
			// this can potentially leave junk in the top nibble but when that
			// happens, 15 is already used so it's fine.
		}

		return P;
	}

	private static int partialPermutationToIndex(long p) {
		long unused = 0xfedcba9876543210L;
		int ind = 0;
		int f = 57657600;
		//System.out.printf("%16x\n", unused);
		for (int i = 16; i > 9; i--) {
			f /= i;
			long a = p & 15;
			long a4 = a << 2;
			p >>>= 4;
			ind += ((unused >>> a4) & 15) * f;
			unused -= 0x1111_1111_1111_1110L << a4;
			// this constant is all 1s, except the last digit.
			// logically, it probably makes more sense to shift all 1s by (a4+4), but
			// then you run into the insane specification that says shifting by 64 is
			// the same as shifting by zero because only the lowest 6 bits of the shift
			// are used.
			//System.out.printf("%16x\n", unused);
		}
		return ind;
	}

	private static long indexToEvenPermutation9(int ind) {
		ind *= 2;
		long p = 0, P = 0;
		int parity = 0;
		for (int i = 2; i < 9; i++) {
			int x = ind % i;
			parity ^= (x & 1);
			p |= ind % i;
			p <<= 4;
			ind /= i;
		}
		p |= ind;
		parity ^= (ind & 1);
		p ^= parity << 28;

		long unused = 0x876543210L;
		for (int i = 0; i < 9; i++) {
			long a = (p >> (4*i)) & 15;
			long a4 = a << 2;
			P |= ((unused >> a4) & 15) << (4*i);
			unused = (unused & ((1L << a4) - 1)) | ((unused >> (a4+4)) << a4);
		}

		return P;
	}

	private static int evenPermutation9ToIndex(long p) {
		long unused = 0x876543210L;
		int ind = 0;
		int f = 181440;
		//System.out.printf("%16x\n", unused);
		for (int i = 9; i > 2; i--) {
			// skip the last two because they're uniquely determined by parity
			f /= i;
			long a = p & 15;
			long a4 = a << 2;
			p >>>= 4;
			ind += ((unused >>> a4) & 15) * f;
			unused -= 0x111111110L << a4;
			//System.out.printf("%16x\n", unused);
		}
		return ind;
	}

	private static int evenPermutation9ToIndex(int[] p) {
		long unused = 0x876543210L;
		int ind = 0;
		int f = 181440;
		//System.out.printf("%16x\n", unused);
		for (int i = 9, j = 0; i > 2; i--, j++) {
			// skip the last two because they're uniquely determined by parity
			f /= i;
			long a = p[j];
			long a4 = a << 2;
			ind += ((unused >>> a4) & 15) * f;
			unused -= 0x111111110L << a4;
			//System.out.printf("%16x\n", unused);
		}
		return ind;
	}

	@SuppressWarnings("unused")
	private static void testPermutation9Functions() {
		for (int i = 0; i < 181440; i++) {
			int[] reference = Util.indexToPermutation(i*2, 9);
			if (Util.permutationParity(reference) == 1) {
				reference = Util.indexToPermutation(i*2+1, 9);
			}
			long p = indexToEvenPermutation9(i);
			int roundtrip = evenPermutation9ToIndex(p);
			int roundtrip2 = evenPermutation9ToIndex(reference);
			for (int j = 0; j < 9; j++) {
				if (((p >> (4*j)) & 15) != reference[j] || i != roundtrip || i != roundtrip2) {
					System.out.printf("%d [%d %d %d %d %d %d %d %d %d] %09x %d %d\n",
							i,
							reference[0], reference[1], reference[2],
							reference[3], reference[4], reference[5],
							reference[6], reference[7], reference[8],
							p,
							roundtrip,
							roundtrip2);
					return;
				}
			}
		}
	}

	private static int setOctalDigit(int n, int i, int x) {
		return (n & ~(7 << (3*i))) | (x << (3*i));
	}

	private static int getOctalDigit(int n, int i) {
		return (n >>> (3*i)) & 7;
	}

	private static int[] reducePermutation(int[] fullBoard) {
		// input is a permutation corresponding to the whole 5x5 board; throw out the ABCFGHKLM
		// block because we don't care about that in this phase
		return Util.reducePermutation(fullBoard, KEEP);
	}

	private static int heuristicVertical(int[] state) {
		int block = WHICH_ROW[state[0]] | (WHICH_ROW[state[1]]<<3)
				| (WHICH_ROW[state[2]]<<6) | (WHICH_ROW[state[3]]<<9)
				| (WHICH_ROW[state[4]]<<12) | (WHICH_ROW[state[5]]<<15);
		int row = WHICH_ROW[state[6]] | (WHICH_ROW[state[7]]<<3) | (WHICH_ROW[state[8]]<<6)
				| (WHICH_ROW[state[9]]<<9) | (WHICH_ROW[state[10]]<<12);
		int h = ptable[encodeBlock[block] + N_BLOCK * encodeRow[row]];
		return h;
	}

	private static int heuristicHorizontal(int[] state) {
		int block = WHICH_COL[state[6]] | (WHICH_COL[state[11]]<<3)
				| (WHICH_COL[state[7]]<<6) | (WHICH_COL[state[12]]<<9)
				| (WHICH_COL[state[8]]<<12) | (WHICH_COL[state[13]]<<15);
		int col = WHICH_COL[state[0]] | (WHICH_COL[state[2]]<<3) | (WHICH_COL[state[4]]<<6)
				| (WHICH_COL[state[9]]<<9) | (WHICH_COL[state[14]]<<12);
		int h = ptable[encodeBlock[block] + N_BLOCK * encodeRow[col]];
		return h;
	}

	private static int heuristicWD(int[] state) {
		return heuristicVertical(state) + heuristicHorizontal(state);
	}

	private static int heuristicSeven(int[] state) {
		return ptableSeven[partialPermutationToIndex(
				state[0] | (state[2]<<4) | (state[4]<<8) |
				(state[9]<<12) | (state[8]<<16) | (state[7]<<20) |
				(state[6]<<24)
				)];
	}

	private static int heuristicSeven(int[] state, int[] buf) {
		int h0 = heuristicSeven(state);
		Util.doubleCompose(flipHV, state, flipHV, buf);
		int h3 = heuristicSeven(buf);
		return Math.max(h0, h3);
	}

	private static int heuristic(int[] state, int[] buf) {
		return Math.max(heuristicWD(state), heuristicSeven(state, buf));
	}

	public static void printStatsSampled() {
		Random random = new SecureRandom();
		int[] histogram = new int[22];
		int samples = 100000000;
		int weightedSum = 0;
		int[] p = new int[16];
		for (int s = 0; s < samples; s++) {
			for (int i = 0; i < 16; i++) {
				int r = random.nextInt(i+1);
				p[i] = p[r];
				p[r] = i;
			}
			if (Util.permutationParity(p) == 1) {int t = p[0]; p[0] = p[1]; p[1] = t;}
			int h = /*Math.max(*/heuristicVertical(p)/*, heuristicVertical(Util.invert(p)))*/;
			histogram[h]++;
			weightedSum += h;
		}
		System.out.printf("total samples: %d\n", samples);
		for (int i = 0; i < histogram.length; i++) {
			System.out.printf("distance %d: %d samples\n", i, histogram[i]);
		}
		System.out.printf("average distance: %.6f\n", (double) weightedSum / (double) samples);
	}

	private static boolean allowAsConsecutiveMoves(int m, int mm) {
		return (m & 8) != (mm & 8) || (m & 4) < (mm & 4);
		// if they're on different axes, or if the first move is (strictly) smaller
	}

	public static int[] solve(int[] state, int verbosity) {
		return solve(state, 0, 9999, verbosity);
	}

	public static int[] solve(int[] state, int depthStart, int depthEnd, int verbosity) {
		if (state.length == 25) {state = reducePermutation(state);}
		//int[] invState = Util.invert(state);
		int[] buf = new int[16];
		int bound = Math.max(depthStart, heuristic(state, buf));
		if (verbosity > 0) {
			System.out.printf("initial depth %d\n", bound);
		}
		long timer = System.nanoTime();
		while (bound <= depthEnd) {
			if (verbosity > 0) {
				System.out.printf("elapsed: %.4f\nsearching depth %d\n", (System.nanoTime()-timer)/1e9, bound);
			}
			IntList sol = search(
					state,
					bound,
					heuristicVertical(state),
					heuristicHorizontal(state),
					-1,
					new int[bound+1][16],
					new int[16]);
			if (sol != null) {
				sol.reverse();
				int[] test = state;
				for (int i = 0; i < sol.size(); i++) {
					test = Util.compose(test, movePermutations[sol.get(i)]);
				}
				for (int i = 0; i < 16; i++) {
					if (test[i] != i) {
						System.out.println("solving error");
					}
				}
				if (verbosity > 0) {
					System.out.printf("solved in %.4f seconds\n", (System.nanoTime()-timer)/1e9);
				}
				return sol.toArray();
			}
			bound++;
		}
		return null;
	}

	private static IntList search(int[] state, int bound, int hv, int hh, int last, int[][] stateStack, int[] buf) {
		int h = hv + hh;
		if (h > bound) {return null;}
		h = Math.max(h, heuristicSeven(state, buf));
		if (h > bound) {return null;}
		if (h == 0) {return new IntList();}
		int[] newState = stateStack[bound];
		for (int m = 0; m < 16; m++) {
			if (last != -1 && !allowAsConsecutiveMoves(last, m)) {continue;}
			Util.compose(state, movePermutations[m], newState);
			IntList sol = ((m < 8) ?
					search(newState, bound-WEIGHTS[m], hv, heuristicHorizontal(newState), m, stateStack, buf) :
						search(newState, bound-WEIGHTS[m], heuristicVertical(newState), hh, m, stateStack, buf));
			if (sol != null) {
				sol.add(m);
				return sol;
			}
		}
		return null;
	}

	public static String stringifySequence(int[] seq) {
		String[] moveNames = {
				"4U", "4U2", "4U2'", "4U'",
				"5U", "5U2", "5U2'", "5U'",
				"4L", "4L2", "4L2'", "4L'",
				"5L", "5L2", "5L2'", "5L'",
		};
		StringBuilder out = new StringBuilder();
		for (int i = 0; i < seq.length; i++) {
			out.append(moveNames[seq[i]]);
			out.append(" ");
		}
		return out.toString().trim();
	}

	public static int weightedLength(int[] seq) {
		int w = 0;
		for (int i = 0; i < seq.length; i++) {
			w += WEIGHTS[seq[i]];
		}
		return w;
	}

	public static int[] convertToStandardMoveSequence(int[] seq) {
		int[] out = new int[seq.length];
		for (int i = 0; i < seq.length; i++) {
			out[i] = MOVE_MAPPING[seq[i]];
		}
		return out;
	}

	public static int[] invertMoveSequence(int[] seq) {
		int[] out = new int[seq.length];
		for (int i = 0; i < seq.length; i++) {
			out[i] = seq[seq.length-1-i] ^ 3;
		}
		return out;
	}

	public static void prettyprint(int[] state) {
		int[] fullBoard = Util.unreducePermutation(state, KEEP);
		for (int r = 0; r < 5; r++) {
			for (int c = 0; c < 5; c++) {
				int x = fullBoard[5*r+c];
				System.out.print((char) ('A' + x));
				if (c != 4) {System.out.print(' ');}
			}
			System.out.println();
		}
	}

	private static int[] randomState(Random random) {
		int[] p = new int[16];
		for (int i = 0; i < 16; i++) {
			int r = random.nextInt(i+1);
			p[i] = p[r];
			p[r] = i;
		}
		if (Util.permutationParity(p) == 1) {int t = p[0]; p[0] = p[1]; p[1] = t;}
		return p;
	}

	private static int[][] findOptimalDINSRQPSolutions(int cosetIndex) {
		// guaranteed to return solutions written using *only* single moves
		// (so array length = actual STM length)
		ArrayList<int[]> sols = new ArrayList<int[]>();
		long p = indexToPartialPermutation(cosetIndex);
		// this has the *locations* of the DINSRQP pieces, in nibbles 0..6 (inclusive, resp.)
		int length = ptableSeven[cosetIndex]; // this has the exact sol length in STM
		if (length == 0) {
			return new int[][]{{}};
		}
		dinsrqpSearch(p, length, 0, new int[length], sols);
		int[][] out = new int[sols.size()][];
		for (int i = 0; i < sols.size(); i++) {out[i] = sols.get(i);}
		return out;
	}

	private static void dinsrqpSearch(long p, int bound, int depth, int[] moveStack, ArrayList<int[]> sols) {
		int h = ptableSeven[partialPermutationToIndex(p)];
		if (depth + h > bound) {return;}
		if (depth == bound) {
			sols.add(moveStack.clone());
			return;
		}
		for (int m = 0; m < 8; m++) {
			int moveIndex = (m << 1) | (m & 1); // the last two bits of a single-tile move are always 00 or 11
			int[] mp = movePermutations[moveIndex ^ 3]; // xoring with 3 gives the inverse move
			long q = Util.compose16(mp, p) & 0xfffffff;
			moveStack[depth] = moveIndex;
			dinsrqpSearch(q, bound, depth+1, moveStack, sols);
		}
	}

	private static int[] quickSolve(int[] state) {
		// roughly 6 microseconds per solve
		IntList sol = new IntList();
		// phase A: solve DINSRQP
		int[] invState = Util.invert(state);
		long p = invState[0] | (invState[2]<<4) | (invState[4]<<8) |
				(invState[9]<<12) | (invState[8]<<16) | (invState[7]<<20) |
				(invState[6]<<24);
		long packedState = 0;
		for (int i = 0; i < 16; i++) {packedState |= ((long) state[i]) << (4*i);}
		int distance = ptableSeven[partialPermutationToIndex(p)];
		while (distance > 0) {
			for (int m = 0; m < 8; m++) {
				int moveIndex = (m << 1) | (m & 1);
				int[] mp = movePermutations[moveIndex ^ 3];
				long q = Util.compose16(mp, p) & 0xfffffff;
				int d = ptableSeven[partialPermutationToIndex(q)];
				if (d < distance) {
					distance = d;
					sol.add(moveIndex);
					packedState = Util.compose16(packedState, movePermutations[moveIndex]);
					p = q;
				}
			}
		}
		// phase B: solve the rest
		int[] intermediateState = new int[16];
		for (int i = 0; i < 16; i++) {
			intermediateState[i] = (int) ((packedState >> (4*i)) & 15);
		}
		int[] p9 = Util.reducePermutation(intermediateState, lrlckeep);
		sol.addAll(lrlcSolutions[Util.permutationToIndex(p9)/2]);

		return sol.toArray();
	}
	
	private static int quickSolveLength(int[] state, int threshold) {
		int[] tmp = new int[16], inv = Util.invert(state);
		int[] sol = quickSolve(state);
		int length = weightedLength(sol);
		if (length <= threshold) {return length;}
		length = Math.min(length, weightedLength(quickSolve(inv)));
		if (length <= threshold) {return length;}
		for (int s = 0; s < 3; s++) {
			// the only symmetries to check here are horizontal flip, vertical flip, rotate 180
			int[] sym = symmetries[s], syminv = symmetriesInverse[s];
			Util.doubleCompose(syminv, state, sym, tmp);
			length = Math.min(length, weightedLength(quickSolve(tmp)));
			if (length <= threshold) {return length;}
			Util.doubleCompose(syminv, inv, sym, tmp);
			length = Math.min(length, weightedLength(quickSolve(tmp)));
			if (length <= threshold) {return length;}
		}
		return length;
	}
	
	public static void solveAllPositionsUnderThreshold(int threshold) {
		solveAllPositionsUnderThreshold(threshold, 0, P16_7);
	}
	
	public static void solveAllPositionsUnderThreshold(int threshold, int start, int end) {
		// threshold: try to solve every position in at most this many moves;
		// report and increase the threshold every time a counterexample is found
		// note: it doesn't make sense to set threshold to 23 or lower since 24-move states exist
		// start/end: inclusive/exclusive range of coset indices to search through
		int numCosetsChecked = 0;
		long numAltSolved = 0, numTwoPhaseSolved = 0, numOptimalSolved = 0;
		long time = System.nanoTime(), startTime = time;
		for (int cosetIndex = start; cosetIndex < end; cosetIndex++) {
			if (ptableSeven[cosetIndex] + 16 <= threshold) {continue;}
			// solving LRLC always takes <= 16 moves, so if the coset is at distance x,
			// then every position in the coset is at distance <= x+16.
			int[][] solutions = findOptimalDINSRQPSolutions(cosetIndex);
			int numSolutions = solutions.length;
			int[][] relPermutations = new int[numSolutions][];
			int[] referenceSolution = solutions[0];
			int[] referenceSolutionPermutation = new int[16];
			for (int i = 0; i < 16; i++) {referenceSolutionPermutation[i] = i;}
			for (int i = 0; i < referenceSolution.length; i++) {
				referenceSolutionPermutation = Util.compose(
						referenceSolutionPermutation,
						movePermutations[referenceSolution[i]]);
			}
			int[] reference = Util.invert(referenceSolutionPermutation);
			for (int i = 0; i < numSolutions; i++) {
				int[] rel = reference;
				for (int m : solutions[i]) {
					rel = Util.compose(rel, movePermutations[m]);
				}
				relPermutations[i] = Util.reducePermutation(rel, lrlckeep);
			}
			
			p9loop: for (int p9index = 0; p9index < HALFFACT9; p9index++) {
				if (ptableSeven[cosetIndex] + lrlcLengths[p9index] <= threshold) {continue;}
				int[] p9 = evenPermutations9[p9index];
				for (int[] relPermutation : relPermutations) {
					// check if there's a different optimal solution to DINSRQP that
					// leads to a total solution length under the threshold
					int otherIndex = evenPermutation9ToIndex(Util.compose(p9, relPermutation));
					if (ptableSeven[cosetIndex] + lrlcLengths[otherIndex] <= threshold) {
						numAltSolved++;
						continue p9loop;
					}
				}
				// all optimal solutions to DINSRQP lead to long solutions; try extending to a 4x4
				// block with the other rows/columns
				int[] state = Util.compose(Util.unreducePermutation(p9, lrlckeep), reference);
				int l = quickSolveLength(state, threshold);
				if (l <= threshold) {
					numTwoPhaseSolved++;
					continue;
				}
				// if that still doesn't work, feed it to the optimal solver
				int[] optimalSolution = solve(state, 0);
				l = weightedLength(optimalSolution);
				if (l <= threshold) {
					numOptimalSolved++;
					continue;
				}
				// optimal is longer than threshold; report this and increase threshold
				System.out.printf("increasing threshold from %d to %d\n", threshold, l);
				prettyprint(state);
				System.out.println(stringifySequence(optimalSolution));
				threshold = l;
			}
			
			numCosetsChecked++;
			if (System.nanoTime() - time > 100_000_000_000l) {
				// report a status update if it has been a while since the last
				time = System.nanoTime();
				System.out.printf("elapsed: %.6f\n", (time-startTime)/1e9);
				System.out.printf("cosets checked: %d (%d skipped, %d total)\n",
						numCosetsChecked,
						cosetIndex+1 - numCosetsChecked,
						cosetIndex+1);
				System.out.printf("%d alt solves, %d two-phase solves, %d optimal solves\n", numAltSolved, numTwoPhaseSolved, numOptimalSolved);
				System.out.printf("current threshold: %d\n", threshold);
				System.gc();
			}
		}
		time = System.nanoTime();
		System.out.printf("elapsed: %.6f (finished)\n", (time-startTime)/1e9);
		System.out.printf("cosets checked: %d (%d skipped, %d total)\n",
				numCosetsChecked,
				end - numCosetsChecked,
				end);
		System.out.printf("%d alt solves, %d two-phase solves, %d optimal solves\n", numAltSolved, numTwoPhaseSolved, numOptimalSolved);
		System.out.printf("current threshold: %d\n", threshold);
	}

	public static void main(String[] args) {
		initialise();

		long startTime = System.nanoTime();

		Random random = new Random();
		random.setSeed(12345);
		
		//testPermutation9Functions();
		if (args.length == 0) {
			solveAllPositionsUnderThreshold(28, 694740, P16_7);
		}
		else {
			solveAllPositionsUnderThreshold(Integer.parseInt(args[0]), Integer.parseInt(args[1]), Integer.parseInt(args[2]));
		}
	}

}