import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class EightPuzzleBFS {

    String asal, tujuan;
    Queue<Node> openQueue = new LinkedList<Node>();
    Map<String, Integer> map = new HashMap<String, Integer>();
    int nomor = 1;

    public EightPuzzleBFS(String asal, String tujuan) {
        this.asal = asal;
        this.tujuan = tujuan;
    }

    void up(Node node) {
        String str = node.getStr();
        int a = str.indexOf("0");
        if (a > 2) {
            String s = str.substring(0, a - 3) + "0" + str.substring(a - 2, a) + str.charAt(a - 3)
                    + str.substring(a + 1);
            Integer level = node.getLevel() + 1;
            addQueue(new Node(s, "up", level, node.getNomor(), node));
        }
    }

    void down(Node node) {
        String str = node.getStr();
        int a = str.indexOf("0");
        if (a < 6) {
            String s = str.substring(0, a) + str.substring(a + 3, a + 4) + str.substring(a + 1, a + 3) + "0"
                    + str.substring(a + 4);
            Integer level = node.getLevel() + 1;
            addQueue(new Node(s, "down", level, node.getNomor(), node));
        }
    }

    void left(Node node) {
        String str = node.getStr();
        int a = str.indexOf("0");
        if (a != 0 && a != 3 && a != 6) {
            String s = str.substring(0, a - 1) + "0" + str.charAt(a - 1) + str.substring(a + 1);
            Integer level = node.getLevel() + 1;
            addQueue(new Node(s, "left", level, node.getNomor(), node));
        }
    }

    void right(Node node) {
        String str = node.getStr();
        int a = str.indexOf("0");
        if (a != 2 && a != 5 && a != 8) {
            String s = str.substring(0, a) + str.charAt(a + 1) + "0" + str.substring(a + 2);
            Integer level = node.getLevel() + 1;
            addQueue(new Node(s, "right", level, node.getNomor(), node));
        }
    }

    public void bfs() {
        addQueue(new Node(asal, "", 0, 1, null));

        while (openQueue.peek() != null) {
            Node X = openQueue.remove();
            System.out.println(X);
            System.out.println();

            if (X.getStr().equals(tujuan)) {
                System.out.println("Solution Exists at Level " + X.getLevel() + " of the tree");
                printPath(X);
                break;
            } else {
                up(X);
                down(X);
                left(X);
                right(X);
            }
        }
    }

    void addQueue(Node node) {
        if (!map.containsKey(node.getStr())) {
            map.put(node.getStr(), node.getLevel());
            Node temp = new Node(node.getStr(), node.getOperator(), node.getLevel(), nomor, node.getParent());
            nomor++;
            openQueue.add(temp);
        }
    }

    void printGrid(String state) {
        String border = "  +---+---+---+";
        for (int i = 0; i < 9; i += 3) {
            char c1 = state.charAt(i);
            char c2 = state.charAt(i + 1);
            char c3 = state.charAt(i + 2);
            System.out.println(border);
            System.out.println(
                    "  | " + (c1 == '0' ? "_" : c1) + " | " + (c2 == '0' ? "_" : c2) + " | " + (c3 == '0' ? "_" : c3)
                            + " |");
        }
        System.out.println(border);
    }

    void printPath(Node goalNode) {
        List<Node> path = new ArrayList<Node>();
        Node current = goalNode;
        while (current != null) {
            path.add(current);
            current = current.getParent();
        }
        Collections.reverse(path);

        System.out.println();
        System.out.println("========================================");
        System.out.println(" Path dari Node Asal ke Node Tujuan");
        System.out.println("========================================");

        for (int i = 0; i < path.size(); i++) {
            Node node = path.get(i);
            if (i == 0) {
                System.out.println("Step " + i + " (Asal):");
            } else {
                System.out.println("Step " + i + " (Operator: " + node.getOperator() + "):");
            }
            System.out.println(node);
            printGrid(node.getStr());

            if (i < path.size() - 1) {
                System.out.println();
            }
        }

        System.out.println("========================================");
        System.out.println(" Total langkah: " + goalNode.getLevel());
        System.out.println("========================================");
    }

    public static void main(String[] args) {
        EightPuzzleBFS eight = new EightPuzzleBFS("283164705", "123804765");
        eight.bfs();
    }
}