使用Java在8拼图中应用不知情的搜索 [英] Applying uninformed search in 8 puzzle using Java

问题描述

大家好，我遇到了实施算法来创建8个拼图程序的问题，该程序使用了不知情的搜索来找到拼图的解决方案.到目前为止，使用DFS的进展甚微.

以下是我的代码:
主分类:

Hi guys, I am having a problem to implement an algorithm to create an 8 puzzle program that uses uninformed search to find the solution for the puzzle. So far I have only made little progress using DFS.

The following are my codes:
Main Class:

public class Main {
    public Main() {
    }

    public static void main(String args[]) {
        int startState[][] = {{6,2,5}, {1,8,0}, {7,4,3}}, goalState[][] = {{7,6,5}, {8,0,4}, {1,2,3}};

        System.out.println("Solving puzzle using DFS...");
        DFS dfs = new DFS(startState, goalState);
        dfs.search();
    }
}

DFS类:

DFS class:

import java.util.Stack;
import java.util.ArrayList;

public class DFS {
    private int moveCounter = 0;
    private Stack<Node> fringe = new Stack<Node>();
    private Node startState, goalState, currentState = new Node();
    private ArrayList<Node> closed = new ArrayList<Node>();

    public DFS(int start[][], int goal[][]) {
        startState = new Node(start);
        goalState = new Node(goal);
        fringe.push(startState);
    }

    private void succesor(Node currentState) {
        Node newState = new Node();
        Puzzle p = new Puzzle();

        newState = p.moveUp(currentState);

        if (newState != null) {
            fringe.push(newState);
        }

        newState = p.moveRight(currentState);

        if (newState != null) {
            fringe.push(newState);
        }

        newState = p.moveDown(currentState);

        if (newState != null) {
            fringe.push(newState);
        }

        newState = p.moveLeft(currentState);

        if (newState != null) {
            fringe.push(newState);
        }
    }

    public void search() {
        boolean found = false, exist = false, checkElement = true;
        Node tmpNode = new Node();

        currentState = fringe.pop();
        closed.add(currentState);
        succesor(currentState);

        for (int x = 1; x < 2 ; x++) {
            while (!found) {
                try {
                    currentState = fringe.pop();

                    for (int i = 0; i < closed.size(); i++) {
                        tmpNode = closed.get(i);

                        if (currentState.toString().equals(tmpNode.toString())) {
                            exist = true;
                            break;
                        }                        
                    }

                    if (!exist) {
                        moveCounter++;

                        if (currentState.getX(x) == goalState.getX(x) && currentState.getY(x) == goalState.getY(x)) {
                            found = true;
                            break;
                        }
                        else {
                            closed.add(currentState);
                            succesor(currentState);
                        }
                    }
                }
                catch (Exception e) {
                    System.out.println("No solutions found!");
                    break;
                }
            }
        }

        System.out.println("Number of step(s): " + moveCounter);
    }
}

节点类别:

Node Class:

public class Node {
    int state[][] = new int[3][3];
    
    public Node() {
    }
    
    public Node(int state[][]) {
        this.state = state;
    }
    
    public int getNum(int posX, int posY) {
        return state[posX][posY];
    }
    
    public void setNum(int num, int x, int y) {
        state[x][y] = num;
    }
    
    public int getX(int num) {
        int positionX = 0;

        for (int x = 0; x < 3; x++) {
            for (int y = 0; y < 3; y++) {
                if (state[x][y] == num) {
                    positionX = x;
                    break;
                }
            }
        }

        return positionX;
    }
    
    public int getY(int num) {
        int positionY = 0;

        for (int x = 0; x < 3; x++) {
            for (int y = 0; y < 3; y++) {
                if (state[x][y] == num) {
                    positionY = y;
                    break;
                }
            }
        }

        return positionY;
    }
    
    public void getCoordinate(int coordinate[], int num) {
        for (int x = 0; x < 3; x++) {
            for (int y = 0; y < 3; y++) {
                if (state[x][y] == num) {
                    coordinate[0] = x;
                    coordinate[1] = y;
                    break;
                }
            }
        }
    }
    
    public void getState(int state[][]) {
        state = this.state;
    }
    
    public String toString() {
        String output = "";

        for (int x = 0; x < 3; x++) {
            for (int y = 0; y < 3; y++) {
                output += state[x][y];
            }
            output += "\n";
        }

        return output;
    }
}

拼图类:

Puzzle Class:

public class Puzzle {    
    public Puzzle() {
    }
    
    private void swap(Node newState, int newPosition[]) {
        int emptyTile[] = new int[2], tmpNum;                

        newState.getCoordinate(emptyTile, 0);
        tmpNum = newState.getNum(newPosition[0], newPosition[1]);
        
        newState.setNum(0, newPosition[0], newPosition[1]);
        newState.setNum(tmpNum, emptyTile[0], emptyTile[1]);
    }
        
    public Node moveUp(Node currentState) {
        Node newState = new Node();
        newState = null;
        int newPosition[] = new int[2];

        if (currentState.getX(0) - 1 >= 0) {
            newState = currentState;
            newPosition[0] = newState.getX(0) - 1;
            newPosition[1] = newState.getY(0);

            swap(newState, newPosition);
        }

        return newState;
    }        
        
    public Node moveRight(Node currentState) {
        Node newState = new Node();
        newState = null;
        int newPosition[] = new int[2];

        if (currentState.getY(0) + 1 <= 2) {
            newState = currentState;
            newPosition[0] = newState.getX(0);
            newPosition[1] = newState.getY(0) + 1;

            swap(newState, newPosition);
        }

        return newState;
    }        
        
    public Node moveDown(Node currentState) {
        Node newState = new Node();
        newState = null;
        int newPosition[] = new int[2];

        if (currentState.getX(0) + 1 <= 2) {
            newState = currentState;
            newPosition[0] = newState.getX(0) + 1;
            newPosition[1] = newState.getY(0);

            swap(newState, newPosition);
        }

        return newState;
    }        
        
    public Node moveLeft(Node currentState) {
        Node newState = new Node();
        newState = null;
        int newPosition[] = new int[2];

        if (currentState.getY(0) - 1 >= 0) {
            newState = currentState;
            newPosition[0] = newState.getX(0);
            newPosition[1] = newState.getY(0) - 1;

            swap(newState, newPosition);
        }

        return newState;
    }        
}

我现在用上面的代码面临的问题是，每当程序弹出堆栈时，它都不会与交换函数方法(Puzzle类)中早先推入的值相符.

任何帮助将不胜感激.谢谢. :)

The problem that I am facing now with the above code is that whenever the program pops the stack it does not tally with the value that has been push earlier in the swap function method (Puzzle Class).

Any help will be appreciated. Thanks. :)

推荐答案

您已经走了这么远，而且您知道该怎么做.

只需执行理货.

You have come this far, and you know what to do.

Just implement the tally.

这篇关于使用Java在8拼图中应用不知情的搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！