首页 / 技术问答 / Java问答列表 / 问答详情

Java 试着做一个2x2的魔方求解算法，我如何找到解路径(DFS)

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
    }

我实现的移动运行得很好，我知道这是因为如果我在每次移动后打印立方体的同时try 解决它，它就会判断出来.但由于某些原因，代码返回的解路径是不正确的，如果我试图在相同的立方体上使用相同的置乱来做解路径，它会得到更多的置乱.如果有人看到这个问题，请告诉我.

推荐答案

有几个问题:

  • 在Face(Face other)构造函数中，您不会创建一个完全独立于other.face数据的face字段.Arrays.copyOf产生shallow个副本，所以两个内部数组现在是shared乘以两个Face实例.当你开始在一个立方体上移动时，这会导致很大的 destruct --它会影响你访问的 map 中的其他实例(S).将该构造函数修复为如下所示:

    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实现的预期输出.

其他 comments

通过将起始位置也标记为已访问，您可以改进dfs算法.那么，在解决方案开始时，您将不会有四个相同的动作.

请注意，当多维数据集的方向恰好不同时，您的isGoal方法不会将其视为已求解，但实际上会将其视为已求解.对于我提供的hashCode和equals实现也是如此:当一个可以通过改变整个立方体的方向从另一个获得时，它们不认为两个立方体相等.立方体有24种不同的方向.

对于求解比您在main代码中创建的立方体更加混乱的立方体，DFS可能不是理想的搜索算法.您可能希望解算器将一些子目标作为目标，例如正确放置的一个角，然后是两个角，然后是三个角，等等.

Java相关问答推荐

为什么如果数组列表中有重复项，我的代码SOMETIMES不返回true？

Mat. n_Delete()和Mat. n_release的区别

ittext pdf延迟签名，签名无效

了解Android Studio中的调试器输出

有没有更快的方法在N个容器中删除重复项？

如何在Microronaut中将 map 读取为 map

搜索列表返回多个频道

如何在antlr4中跳过所有反斜杠-换行符而保留换行符？

如何在 spring 数据的MongoDB派生查询方法中使用$EXISTS

错误：未找到扩展元素在JBossEAP 7.2中安装FUSE时出错

在Oracle db中，当我们提供字符串而不是数字时，比较是如何工作的？

本机方法(JNI)总是编译的吗？

无法在Java中获取ElastiCache的AWS CloudWatch指标

多线程、并发和睡眠未按预期工作

Java泛型方法重载

使用StringBuilder和append方法创建字符串时Java字符串内部方法的问题

try 添加；按流派搜索；在Web应用程序上，但没有；I don’我不知道；It’这个代码错了

带有提取器的JavaFXObservableList会根据侦听器的存在而改变行为

Vaadin Flow：设置密码显示按钮属性

声纳覆盖范围为 0%，未生成 jacoco.xml

实用课程推荐
相关教程推荐
休闲君评测 |  TOOLFK工具网 |  古诗文网 |  良许Linux教程网 |  Python之禅 |  红色石头 |  入党申请书 | 

© 2020 Hi LearnFk 意见反馈 免责声明 关于我们 桂ICP备11002319号-3 友链&广告位+QQ: 1963612630