I am working on a cube solver at the moment and it uses breadth first search to find the shortest solution to the 2x2x2 rubiks cube solver. The thing is that in the search there are duplicate positions that get hit and my goal is to know how many of them I have and "prune" them out later.(I know how to avoid the duplicates but that is irrelevant to this post). Here is what it should look like
That is from an old version of the code which works with the hashCode and equals but I am trying to get the new version to work with it. I think the reason is because in the old version I override equals and hashCode, but in the new one I can't seem to do that because I am no longer comparing objects, rather arrays (that is guess). The current version isn't picking up duplicates due to this. It says there are no duplicates but that is incorrect.
here is what the hashCode and equals is like for the old version which detects duplicates.
private Cube() {
cube = new int[][] {
{ 0, 0, 0, 0 },
{ 1, 1, 1, 1 },
{ 2, 2, 2, 2 },
{ 3, 3, 3, 3 },
{ 4, 4, 4, 4 },
{ 5, 5, 5, 5 }
};
cube = scanCube(cube);
cube = print_cube(cube);
}
private Cube(Cube other) {
cube = new int[other.cube.length][];
for (int i = 0; i < other.cube.length; i++) {
cube[i] = Arrays.copyOf(other.cube[i], other.cube[i].length);
}
}
public boolean isSolved() {
for (int i = 0; i < cube.length; i++) {
for (int k = 1; k < cube[i].length; k++) {
if (cube[i][0] != cube[i][k]) {
return false;
}
}
}
return true;
}
@Override
public boolean equals(Object other) {
return other instanceof Cube && Arrays.deepEquals(((Cube) other).cube, cube);
}
@Override
public int hashCode() {
return Arrays.deepHashCode(cube);
}`
Here is the current version.
public static void main(String[] args) {
int[][] cube = new int[][] {
{ 0, 0, 0, 0 },
{ 1, 1, 1, 1 },
{ 2, 2, 2, 2 },
{ 3, 3, 3, 3 },
{ 4, 4, 4, 4 },
{ 5, 5, 5, 5 }
};
cube = scanCube(cube);
cube = print_cube(cube);
solve(cube);
}
private static boolean isSolved(int [][] cube) {
for (int i = 0; i < cube.length; i++) {
for (int k = 1; k < cube[i].length; k++) {
if (cube[i][0] != cube[i][k]) {
return false;
}
}
}
return true;
}
public static int[][] copyCube(int [][] cube){
int [][] copy = new int [6][4];
for(int i = 0; i < 6; i++ ){
copy[i] = cube[i].clone();
}
return copy;
}
public static boolean equals(int[][] other, int[][] cube) {
return Arrays.deepEquals(other, cube);
}
public int hashCode(int [][] cube) {
return Arrays.deepHashCode(cube);
}
In the search method is where duplicates are determined. Here is the code for the old one.
static public void solve(Cube c) {
Set<Cube> cubesFound = new HashSet<Cube>();
cubesFound.add(c);
Stack<Cube> s = new Stack<Cube>();
s.push(c);
Set<Stack<Cube>> initialPaths = new HashSet<Stack<Cube>>();
initialPaths.add(s);
solve(initialPaths, cubesFound);
}
static public void solve(Set<Stack<Cube>> livePaths, Set<Cube> cubesFoundSoFar) {
System.out.println("livePaths size:" + livePaths.size());
int numDupes = 0;
Set<Stack<Cube>> newLivePaths = new HashSet<Stack<Cube>>();
for (Stack<Cube> currentPath : livePaths) {
Set<Cube> nextStates = currentPath.peek().getNextStates();
for (Cube next : nextStates) {
if (currentPath.size() > 1 && next.isSolved()) {
currentPath.push(next);
System.out.println("Path length:" + currentPath.size());
System.out.println("Path:" + currentPath);
System.exit(0);
} else if (!cubesFoundSoFar.contains(next)) {
Stack<Cube> newCurrentPath = new Stack<Cube>();
newCurrentPath.addAll(currentPath);
newCurrentPath.push(next);
newLivePaths.add(newCurrentPath);
cubesFoundSoFar.add(next);
} else {
numDupes += 1;
}
}
}
System.out.println("Duplicates found " + numDupes + ".");
solve(newLivePaths, cubesFoundSoFar);
}
And the new one.
static private void solve(int[][] cube) {
int[][][] s = new int[12][6][4];
s[0] = cube;
Set<int[][][]> initialPaths = new HashSet<int[][][]>();
initialPaths.add(s);
Set<int[][]> cubesFound = new HashSet<int[][]>();
cubesFound.add(cube);
solve(initialPaths, cubesFound, 1);
}
static private void solve(Set<int[][][]> livePaths,Set<int[][]> cubesFoundSoFar, int iterationCount) {
System.out.println("livePaths size:" + livePaths.size());
Set<int[][][]> newLivePaths = new HashSet<int[][][]>();
int counter = 0;
int recordDepth = 0;
int duplicates = 0;
for(int[][][] currentPath : livePaths) {
Set<int [][]> nextStates = getNextStates(currentPath[iterationCount-1]);
for (int[][] next : nextStates) {
if (isSolved(next)) {
currentPath[iterationCount] = next;
int maxSteps = -1;
System.out.println("Path:" );
for(int i = 0; i < currentPath.length; i++) {
if(currentPath[i] != null) {
maxSteps = i;
System.out.println(toString(currentPath[i]));
}else {
break;
}
}
System.out.println("Path length:" + maxSteps);
System.exit(0);
} else if(!cubesFoundSoFar.contains(next)){
int[][][] newCurrentPath = new int[12][6][4];
newCurrentPath = currentPath.clone();
newCurrentPath[iterationCount] = next;
newLivePaths.add(newCurrentPath);
counter ++;
cubesFoundSoFar.add(next);
} else {
duplicates += 1;
}
}
}
//System.out.println(" Set.size(): "+newLivePaths.size());
String storeStates = "positions.txt";
try {
PrintWriter outputStream = new PrintWriter(storeStates);
outputStream.println(storeStates);
for(int[][][] s:newLivePaths) {
outputStream.println(toString(s[iterationCount]));
}
outputStream.close();
} catch (FileNotFoundException e) {
System.err.println("Fatal: could not open cache file for cube positions. exiting.");
e.printStackTrace();
System.exit(1);
}
System.out.println("Duplicates found "+ duplicates + ".");
solve(newLivePaths, cubesFoundSoFar, iterationCount+1);
}
