public class Cube extends Face{
Face Up, Down, Left, Right, Back, Front;
int numberOfTurns = 0;
public Cube(){ //make Cube
this.Up = new Face('W');
this.Down = new Face('Y');
this.Left = new Face('O');
this.Right = new Face('R');
this.Front = new Face('G');
this.Back = new Face('B');
}
public Cube copy() {
// Create a new Cube with copied faces
Cube copyCube = new Cube();
copyCube.Up = new Face(this.Up);
copyCube.Down = new Face(this.Down);
copyCube.Left = new Face(this.Left);
copyCube.Right = new Face(this.Right);
copyCube.Front = new Face(this.Front);
copyCube.Back = new Face(this.Back);
copyCube.numberOfTurns = this.numberOfTurns;
return copyCube;
}
public boolean isGoal() {
if ((isFaceAllColor(Back, 'B')==true) && (isFaceAllColor(Front, 'G')==true)&&(isFaceAllColor(Right, 'R')==true)
&&(isFaceAllColor(Left, 'O')==true)&& (isFaceAllColor(Down, 'Y')==true)&&(isFaceAllColor(Up, 'W')==true))
{
return true;
}
else return false;
}
private boolean isFaceAllColor(Face face, char color) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
if (Character.valueOf(color).equals(Character.valueOf(face.getColor(i, j)))!=true) {
return false;
}
}
}
return true;
}
public void move(String move) {
switch (move) {
case "F":
F();
break;
case "U":
U();
break;
case "R":
R();
break;
case "B":
B();
break;
case "L":
L();
break;
case "D":
D();
break;
case "Fi":
Fi();
break;
case "Ui":
Ui();
break;
case "Ri":
Ri();
break;
case "Bi":
Bi();
break;
case "Li":
Li();
break;
case "Di":
Di();
break;
}
}
char[] tempArray = new char[2];
char Temp;
private void TurnFaceClockwise(Face f) {
char temp = f.face[0][0];
f.face[0][0] = f.face[1][0];
f.face[1][0] = f.face[1][1];
f.face[1][1] = f.face[0][1];
f.face[0][1] = temp;
}
public void R(){ // R
TurnFaceClockwise(Right);
tempArray[0] = Down.face[0][1]; //store right column
tempArray[1] = Down.face[1][1];
Down.face[0][1] = Back.face[1][0];
Down.face[1][1] = Back.face[0][0];
Back.face[1][0] = Up.face[0][1];
Back.face[0][0] = Up.face[1][1];
Up.face[0][1] = Front.face[0][1];
Up.face[1][1] = Front.face[1][1];
Front.face[0][1] = tempArray[0];
Front.face[1][1] = tempArray[1];
}
public void L(){ // L
TurnFaceClockwise(Left);
tempArray[0] = Down.face[1][0]; //store left column
tempArray[1] = Down.face[0][0];
Down.face[0][0] = Front.face[0][0];
Down.face[1][0] = Front.face[1][0];
Front.face[0][0] = Up.face[0][0];
Front.face[1][0] = Up.face[1][0];
Up.face[1][0] = Back.face[0][1];
Up.face[0][0] = Back.face[1][1];
Back.face[0][1] = tempArray[0];
Back.face[1][1] = tempArray[1];
}
public void U(){ // U
TurnFaceClockwise(Up);
tempArray[0] = Front.face[0][0]; //store Front Row
tempArray[1] = Front.face[0][1];
Front.face[0][0] = Right.face[0][0];
Front.face[0][1] = Right.face[0][1];
Right.face[0][0] = Back.face[0][0];
Right.face[0][1] = Back.face[0][1];
Back.face[0][0] = Left.face[0][0];
Back.face[0][1] = Left.face[0][1];
Left.face[0][0] = tempArray[0];
Left.face[0][1] = tempArray[1];
}
public void D(){ // D
TurnFaceClockwise(Down);
tempArray[0] = Front.face[1][0]; //store Front bottom Row
tempArray[1] = Front.face[1][1];
Front.face[1][0] = Left.face[1][0];
Front.face[1][1] = Left.face[1][1];
Left.face[1][0] = Back.face[1][0];
Left.face[1][1] = Back.face[1][1];
Back.face[1][0] = Right.face[1][0];
Back.face[1][1] = Right.face[1][1];
Right.face[1][0] = tempArray[0];
Right.face[1][1] = tempArray[1];
}
public void F(){ // F
TurnFaceClockwise(Front);
tempArray[0] = Up.face[1][0]; //store Up bottom Row
tempArray[1] = Up.face[1][1];
Up.face[1][0] = Left.face[1][1];
Up.face[1][1] = Left.face[0][1];
Left.face[0][1] = Down.face[0][0];
Left.face[1][1] = Down.face[0][1];
Down.face[0][0] = Right.face[1][0];
Down.face[0][1] = Right.face[0][0];
Right.face[0][0] = tempArray[0];
Right.face[1][0] = tempArray[1];
}
public void B(){ // B
TurnFaceClockwise(Back);
tempArray[0] = Up.face[0][0]; //store Up Top Row
tempArray[1] = Up.face[0][1];
Up.face[0][0] = Right.face[0][1];
Up.face[0][1] = Right.face[1][1];
Right.face[0][1] = Down.face[1][1];
Right.face[1][1] = Down.face[1][0];
Down.face[1][1] = Left.face[1][0];
Down.face[1][0] = Left.face[0][0];
Left.face[0][0] = tempArray[1];
Left.face[1][0] = tempArray[0];
}
public void Bi() {
for(int i=0;i<3;i++) {
B();
}
}
public void Ri() {
for(int i=0;i<3;i++) {
R();
}
}
public void Ui() {
for(int i=0;i<3;i++) {
U();
}
}
public void Li() {
for(int i=0;i<3;i++) {
L();
}
}
public void Di() {
for(int i=0;i<3;i++) {
D();
}
}
public void Fi() {
for(int i=0;i<3;i++) {
F();
}
}
}
public class Face {
char[][] face; //face
public Face(){ //make empty face
face = new char[2][2];
}
public Face(char s){ //make face with color
face = new char[2][2];
for(int i=0; i<2; i++){
for(int j=0; j<2; j++){
face[i][j] = s;
}
}
}
public Face(Face other) {
// Copy the face array
this.face = Arrays.copyOf(other.face, other.face.length);
}
public char getColor(int x, int y){
return face[x][y];
}
}
public class CubeSolver {
private static Set<Cube> visitedStates = new HashSet<>();
private static StringBuilder solutionSteps = new StringBuilder();
public static void main(String[] args) {
Cube b=new Cube();
b.Ui();
CubeSolver.solveDFShelper(b, 10); // Set the desired depth limit for the search
}
public static void solveDFShelper(Cube cube, int maxDepth) {
String[] moves = {"F", "U", "L", "R", "D", "B", "Li", "Ui", "Bi", "Di", "Ri", "Fi"};
visitedStates.clear();
solutionSteps.setLength(0);
boolean solutionFound = dfs(cube, maxDepth, moves); // Use the maxDepth parameter here
if (solutionFound) {
System.out.println("Solution found. Steps: " + solutionSteps.toString());
} else {
System.out.println("No solution found.");
}
}
public static boolean dfs(Cube cube, int depthLimit, String[] moves) {
if (cube.isGoal()) {
return true; // Found a solution
}
if (depthLimit == 0) {
return false; // Reached depth limit without finding a solution
}
for (String move : moves) {
Cube newCube = cube.copy();
newCube.move(move);
//System.out.println(move + " :" + newCube.getCubeColorsAsString());
if (!visitedStates.contains(newCube)) {
visitedStates.add(newCube);
solutionSteps.append(move); // Append the entire move at once
if (dfs(newCube, depthLimit - 1, moves)) {
return true; // Solution found
}
solutionSteps.setLength(solutionSteps.length() - move.length()); // Backtrack
visitedStates.remove(newCube); // Backtrack
}
}
return false; // No solution found at this depth
}
the moves i implemented work fine ,and i know that because if i try to solve it while printing the cube after every move , it checks out . but for some reason the solution path that the code returns is not right , if i try to do the solution path on the same cube withy the same scramble it gets scrambled even more . if anyone sees the problem please tell me.
There are a few issues:
In the Face(Face other) constructor, you're not creating a face field that is completely independent from the other.face data. Arrays.copyOf makes a shallow copy, and so the two inner arrays are now shared by the two Face instances. This leads to havoc when you start making moves on a cube -- it will impact other instance(s) that are in your visited map. Fix that constructor to something like this:
public Face(Face other) {
face = new char[][] {
Arrays.copyOf(other.face[0], 2),
Arrays.copyOf(other.face[1], 2)
};
}
The condition visitedStates.contains(newCube) will never be true, as newCube is a new object reference, and you haven't overridden the default equals and hashCode methods. Here are possible implementations:
In Cube:
@Override
public boolean equals(Object other) {
if (!(other instanceof Cube)) return false;
Cube otherCube = (Cube) other;
return Up.equals(otherCube.Up) &&
Down.equals(otherCube.Down) &&
Left.equals(otherCube.Left) &&
Right.equals(otherCube.Right) &&
Back.equals(otherCube.Back) &&
Front.equals(otherCube.Front);
}
@Override
public int hashCode() {
return Objects.hash(Up, Down, Left, Right, Back, Front);
}
And in Face:
@Override
public boolean equals(Object other) {
return other instanceof Face && Arrays.deepEquals(face, ((Face) other).face);
}
@Override
public int hashCode() {
return Arrays.deepHashCode(face);
}
With these two problems fixed, your code will output this:
Solution found. Steps: FFFFU
This is the expected output of your dfs implementation.
You could improve on the dfs algorithm, by marking the starting position also as visited. Then you will not have four of the same moves at the start of the solution.
Be aware that your isGoal method does not consider a cube solved when it just happens to be oriented differently, but would actually be considered solved. The same is true for the hashCode and equals implementations I provided: they don't consider two cubes equal when one can be obtained from the other by just changing the orientation of the whole cube. There are 24 different ways a cube can be oriented.
For solving cubes that are more scrambled than the one you created in your main code, DFS might not be the ideal search algorithm. You might want to have the solver target some sub-targets, such as one corner that is placed correctly, then two, then three, ...etc.