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
}
我实施的动作工作得很好,而且我知道,因为如果我在每次动作后打印立方体时尝试解决它,它就会检查出来。但由于某种原因,代码返回的解决方案路径不正确,如果我尝试在同一个立方体上使用相同的加扰来执行解决方案路径,它会变得更加混乱。如果有人看到问题请告诉我。
有几个问题:
在
Face(Face other)
构造函数中,您没有创建完全独立于 face
数据的 other.face
字段。 Arrays.copyOf
制作一个 shallow 副本,因此两个内部数组现在由两个 Face
实例共享。当您开始在立方体上移动时,这会导致严重破坏 - 它将影响您访问的地图中的其他实例。将该构造函数修复为如下所示:
public Face(Face other) {
face = new char[][] {
Arrays.copyOf(other.face[0], 2),
Arrays.copyOf(other.face[1], 2)
};
}
条件
visitedStates.contains(newCube)
永远不会为真,因为 newCube
是一个新的对象引用,并且您尚未覆盖默认的 equals
和 hashCode
方法。以下是可能的实现:
在
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);
}
在
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);
}
解决了这两个问题后,您的代码将输出以下内容:
Solution found. Steps: FFFFU
这是您的
dfs
实施的预期输出。
您可以通过将起始位置标记为已访问来改进
dfs
算法。那么在解决方案开始时您将不会有四个相同的动作。
请注意,当立方体的方向恰好不同时,您的
isGoal
方法不会认为立方体已解决,但实际上会被视为已解决。我提供的 hashCode
和 equals
实现也是如此:当只需更改整个立方体的方向即可从另一个立方体获得一个立方体时,它们不认为两个立方体相等。立方体有 24 种不同的定向方式。
对于求解比您在
main
代码中创建的立方体更混乱的立方体,DFS 可能不是理想的搜索算法。您可能想让解算器针对一些子目标,例如正确放置的一个角,然后是两个,然后是三个,...等等。