Solving puzzle using BFS

input.txt

3
2 8 3
1 6 4
7 -1 5

1 2 3
8 -1 4
7 6 5

Main.java

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {
    public static boolean ReadFromFile = true; // do you wanna read from file
    public static boolean displaced = true; // displaced or manhattan
    public static int dimensions;
    static int start[][], goal[][];

    public static void main(String[] args) throws FileNotFoundException {
        getInput();

        new Puzzle(start, goal, null, displaced).run();

    }

    private static void getInput() throws FileNotFoundException {
        Scanner scanner;
        if (ReadFromFile) {
            File file = new File("src/input.txt"); // don't forget to edit
            scanner = new Scanner(file);
        } else {
            scanner = new Scanner(System.in);
        }
        if (!ReadFromFile)
            System.out.println("Enter Dimensions:");

        dimensions = scanner.nextInt();

        start = new int[dimensions][dimensions];
        goal = new int[dimensions][dimensions];
        if (!ReadFromFile)
            System.out.println("start state , -1 for space");
        for (int i = 0; i < dimensions; i++) {
            for (int j = 0; j < dimensions; j++) {
                start[i][j] = scanner.nextInt();
            }
        }
        if (!ReadFromFile)
            System.out.println("goal state , -1 for space");
        for (int i = 0; i < dimensions; i++) {
            for (int j = 0; j < dimensions; j++) {
                goal[i][j] = scanner.nextInt();
            }
        }
    }
}

Puzzle.java

import java.util.ArrayList;

public class Puzzle {
    static int goal[][];
    static boolean displaced;
    int current[][], cost, level, totalCost;
    String direction = "";
    Puzzle parent;
    ArrayList<Puzzle> cheldren = new ArrayList<>();

    public Puzzle(int[][] current, int[][] goal, Puzzle parent, boolean displaced) {
        this.current = current;
        this.goal = goal;
        this.parent = parent;
        this.displaced = displaced;
        this.cost = getCost();
        level = 0;
        totalCost = cost + level;

    }

    public Puzzle(int[][] current, Puzzle parent, String direction, int level, int totalCost) {
        this.current = current;
        this.parent = parent;
        this.cost = getCost();
        this.direction = direction;
        this.level = level + 1;
        this.totalCost = cost + this.level + totalCost;
    }

    public void run() {
        Puzzle p = this;
        while (!p.isItGoal()) {
            System.out.println(p);
            p.move();
            p = p.getChoice();
        }
        System.out.println(p);
    }

    public void move() {
        int spacePos[] = getSpacePos();
        moveLeft(current, spacePos);
        MoveUp(current, spacePos);
        moveDown(current, spacePos);
        moveRight(current, spacePos);

    }

    private void duplicateHandling(int[][] tmp, String direction) {
        Puzzle c = new Puzzle(tmp, this, direction, level, totalCost);
        Puzzle p = this;
        while (p.parent != null) {
            p = p.parent;
            if (p.equals(c)) return;
        }
        cheldren.add(c);
    }

    private void moveDown(int[][] current, int[] spacePos) {
        if (spacePos[0] != current.length - 1) {
            int tmp[][] = copyArray(current);
            tmp[spacePos[0]][spacePos[1]] = tmp[spacePos[0] + 1][spacePos[1]];
            tmp[spacePos[0] + 1][spacePos[1]] = -1;
            duplicateHandling(tmp, "down");
        }
    }

    private void MoveUp(int[][] current, int[] spacePos) {
        if (spacePos[0] != 0) {
            int tmp[][] = copyArray(current);
            tmp[spacePos[0]][spacePos[1]] = tmp[spacePos[0] - 1][spacePos[1]];
            tmp[spacePos[0] - 1][spacePos[1]] = -1;
            duplicateHandling(tmp, "up");
        }
    }

    private void moveRight(int[][] current, int[] spacePos) {
        if (spacePos[1] != current.length - 1) {
            int tmp[][] = copyArray(current);
            tmp[spacePos[0]][spacePos[1]] = tmp[spacePos[0]][spacePos[1] + 1];
            tmp[spacePos[0]][spacePos[1] + 1] = -1;
            duplicateHandling(tmp, "right");
        }
    }

    private void moveLeft(int[][] current, int[] spacePos) {
        if (spacePos[1] != 0) {
            int tmp[][] = copyArray(current);
            tmp[spacePos[0]][spacePos[1]] = tmp[spacePos[0]][spacePos[1] - 1];
            tmp[spacePos[0]][spacePos[1] - 1] = -1;
            duplicateHandling(tmp, "left");
        }
    }

    private int[][] copyArray(int[][] current) {
        int tmp[][] = new int[current.length][current.length];
        for (int i = 0; i < tmp.length; i++) {
            for (int j = 0; j < tmp.length; j++) {
                tmp[i][j] = current[i][j];
            }
        }
        return tmp;
    }

    private int[] getSpacePos() {
        for (int i = 0; i < current.length; i++) {
            for (int j = 0; j < current.length; j++) {
                if (current[i][j] == -1) return new int[]{i, j};
            }
        }
        return null;
    }

    private int getCost() {
        int sum = 0;
        if (displaced) {
            sum = calculateDisplaced(sum);
        } else {
            sum = calculateManhattan(sum);
        }
        return sum;
    }

    private int calculateManhattan(int sum) {
        for (int i = 0; i < current.length; i++) {
            for (int j = 0; j < current.length; j++) {
                if (current[i][j] != goal[i][j] && current[i][j] != -1) {
                    sum += getGoalDiff(current[i][j], i, j);
                }
            }
        }
        return sum;
    }

    private int calculateDisplaced(int sum) {
        for (int i = 0; i < current.length; i++) {
            for (int j = 0; j < current.length; j++) {
                if (current[i][j] != goal[i][j] && current[i][j] != -1) sum++;
            }
        }
        return sum;
    }

    private int getGoalDiff(int value, int ci, int cj) {
        for (int i = 0; i < current.length; i++) {
            for (int j = 0; j < current.length; j++) {
                if (value == goal[i][j]) return Math.abs(i - ci) + Math.abs(j - cj);
            }
        }
        return 0;
    }

    @Override
    public String toString() {
        String tmp = direction + "\n";
        for (int i = 0; i < current.length; i++) {
            for (int j = 0; j < current.length; j++) {
                tmp += " " + current[i][j];
            }
            tmp += "\n";
        }
        return tmp + "cost:" + cost + ", level:" + level + ", total Cost: " + totalCost + "\n";
    }

    public boolean isItGoal() {
        for (int i = 0; i < current.length; i++) {
            for (int j = 0; j < current.length; j++) {
                if (current[i][j] != goal[i][j]) return false;
            }
        }
        return true;
    }

    public Puzzle getChoice() {
        ArrayList<Puzzle> count = getLeastCost();
        Puzzle puzzle = handleEqualCosts(count);
        while (!count.contains(puzzle) && puzzle.parent != null) {
            puzzle = puzzle.parent;
        }
        return puzzle;

    }

    private ArrayList<Puzzle> getLeastCost() {
        ArrayList<Puzzle> count = new ArrayList<>();
        for (Puzzle p : cheldren
                ) {
            costsComparison(count, p);
        }
        return count;

    }

    private void costsComparison(ArrayList<Puzzle> count, Puzzle p) {
        if (count.size() == 0 || p.cost == count.get(0).cost) {
            count.add(p);
        } else if (p.cost < count.get(0).cost) {
            count.clear();
            count.add(p);
        }
    }

    private Puzzle handleEqualCosts(ArrayList<Puzzle> count) {
        if (count.size() == 1) {
            return count.get(0);
        } else {
            count.forEach(Puzzle::move);
            ArrayList<Puzzle> tCount = new ArrayList<>();
            for (Puzzle p : count
                    ) {
                for (Puzzle pp : p.cheldren
                        ) {
                    costsComparison(tCount, pp);
                }
            }
            return tCount.get(0);
        }

    }

    @Override
    public boolean equals(Object obj) {
        for (int i = 0; i < current.length; i++) {
            for (int j = 0; j < current.length; j++) {
                if (current[i][j] != ((Puzzle) obj).current[i][j]) return false;
            }
        }
        return true;
    }
}

SampleOutput.txt

manhattan :
 2 8 3
 1 6 4
 7 -1 5
cost:5, level:0, total Cost: 5

up
 2 8 3
 1 -1 4
 7 6 5
cost:4, level:1, total Cost: 9

up
 2 -1 3
 1 8 4
 7 6 5
cost:3, level:2, total Cost: 13

left
 -1 2 3
 1 8 4
 7 6 5
cost:2, level:3, total Cost: 17

right
 1 2 3
 8 -1 4
 7 6 5
cost:0, level:5, total Cost: 25

_________________________
displaced:

 2 8 3
 1 6 4
 7 -1 5
cost:4, level:0, total Cost: 4

up
 2 8 3
 1 -1 4
 7 6 5
cost:3, level:1, total Cost: 7

up
 2 -1 3
 1 8 4
 7 6 5
cost:3, level:2, total Cost: 11

left
 -1 2 3
 1 8 4
 7 6 5
cost:2, level:3, total Cost: 15

right
 1 2 3
 8 -1 4
 7 6 5
cost:0, level:5, total Cost: 23