Java 15 Puzzle Solver Using BFS

Simple Java program to solve 3/8/15/… puzzles using Breadth First Search(BFS) path finding algorithm.

------- BEFORE -------
0 1 3 4 
5 2 6 8 
13 10 7 11 
14 9 15 12 

------- AFTER -------
1 2 3 4 
5 6 7 8 
9 10 11 12 
13 14 15 0 

Path: RDRDLDLURRRD
Path length: 12
Solved in: 1132.652ms

puzzleToSolve.txt

4 4
6 1 3 4
5 2 11 7
0 9 10 8
13 14 15 12

Main.java

// © 2019 TheFlyingKeyboard and released under MIT License
// theflyingkeyboard.net
public class Main {

    public static void main(String[] args) {
        PuzzleLoader puzzleLoader = new PuzzleLoader();
        Puzzle puzzle;
        int[][] correctPuzzle;
        int[][] puzzleToSolve;

        puzzleToSolve = puzzleLoader.load("puzzleToSolve.txt");
        correctPuzzle = generateCorrectPuzzle(puzzleToSolve.length, puzzleToSolve[0].length);

        puzzle = new Puzzle(puzzleToSolve, correctPuzzle);

        System.out.println("------- BEFORE -------");
        System.out.println(puzzle);

        long timeStart;
        long timeStop;

        SolverBFS solverBFS = new SolverBFS();
        Puzzle.DIRECTION[] strategy = {Puzzle.DIRECTION.RIGHT, Puzzle.DIRECTION.DOWN, Puzzle.DIRECTION.UP, Puzzle.DIRECTION.LEFT};

        timeStart = System.nanoTime();

        Puzzle solvedPuzzle = solverBFS.solve(puzzle, strategy);

        timeStop = System.nanoTime();

        System.out.println("------- AFTER -------");
        System.out.println(solvedPuzzle);

        System.out.println("Path: " + solvedPuzzle.getPath());
        System.out.println("Path length: " + solvedPuzzle.getPath().length());
        System.out.println("Solved in: " + ((timeStop - timeStart) / 1000) / 1000.0 + "ms");
    }

    private static int[][] generateCorrectPuzzle(int xSize, int ySize) {
        int[][] correctPuzzle = new int[ySize][xSize];
        int counter = 1;

        for (int y = 0; y < ySize; ++y) {
            for (int x = 0; x < xSize; ++x) {
                correctPuzzle[y][x] = counter;

                ++counter;
            }
        }

        correctPuzzle[ySize - 1][xSize - 1] = 0;

        return correctPuzzle;
    }
}

PuzzleLoader.java

import java.io.BufferedReader;
import java.io.FileReader;

// © 2019 TheFlyingKeyboard and released under MIT License
// theflyingkeyboard.net

public class PuzzleLoader {

    public int[][] load(String fileName) {
        int[][] puzzle;

        BufferedReader br;
        String line;
        String cvsSplitBy = " ";

        try {
            br = new BufferedReader(new FileReader(fileName));

            line = br.readLine();
            String[] size = line.split(cvsSplitBy);

            puzzle = new int[Integer.parseInt(size[0])][Integer.parseInt(size[1])];

            int puzzleLine = 0;

            while ((line = br.readLine()) != null) {
                String[] tiles = line.split(cvsSplitBy);

                for (int i = 0; i < puzzle[0].length; ++i) {
                    puzzle[puzzleLine][i] = Integer.parseInt(tiles[i]);
                }

                ++puzzleLine;
            }

            br.close();

            return puzzle;
        } catch (Exception e) {
            e.printStackTrace();
        }

        return null;
    }
}

SolverBFS.java

import java.util.LinkedList;
import java.util.Queue;

// © 2019 TheFlyingKeyboard and released under MIT License
// theflyingkeyboard.net

public class SolverBFS {
    private final Queue<Puzzle> frontiers = new LinkedList<>();

    public Puzzle solve(Puzzle puzzleToSolve, Puzzle.DIRECTION[] strategy) {
        frontiers.add(puzzleToSolve);

        while (!frontiers.isEmpty()) {
            Puzzle puzzle = frontiers.poll();

            if (puzzle.isSolved()) {
                return puzzle;
            }

            for (int i = 0; i < strategy.length; i++) {
                if (puzzle.canMove(strategy[i])) {
                    Puzzle newPuzzle = new Puzzle(puzzle);
                    newPuzzle.move(strategy[i]);

                    frontiers.add(newPuzzle);
                }
            }
        }

        return null;
    }
}

Puzzle.java

// © 2019 TheFlyingKeyboard and released under MIT License
// theflyingkeyboard.net
import java.util.Arrays;

public class Puzzle {
    public enum DIRECTION {UP, DOWN, LEFT, RIGHT}

    private final int[][] puzzle;
    private int[][] correctPuzzle;
    private String path = "";

    private int zeroX, zeroY;

    public Puzzle(int[][] puzzle, int[][] correctPuzzle) {
        this.puzzle = puzzle;
        this.correctPuzzle = correctPuzzle;

        findZeroTile();
    }

    public Puzzle(Puzzle newPuzzle) {
        puzzle = new int[newPuzzle.puzzle.length][newPuzzle.puzzle[0].length];

        for (int i = 0; i < puzzle.length; i++) {
            puzzle[i] = Arrays.copyOf(newPuzzle.puzzle[i], puzzle[i].length);
        }

        correctPuzzle = newPuzzle.correctPuzzle;

        zeroX = newPuzzle.zeroX;
        zeroY = newPuzzle.zeroY;

        path = newPuzzle.path;
    }

    public boolean isSolved() {
        for (int y = 0; y < puzzle.length; ++y) {
            for (int x = 0; x < puzzle[y].length; ++x) {
                if (puzzle[y][x] != correctPuzzle[y][x]) {
                    return false;
                }
            }
        }

        return true;
    }

    public boolean canMove(DIRECTION direction) {

        switch (direction) {
            case UP:
                if (zeroY != 0) {
                    return true;
                }

                break;
            case DOWN:
                if (zeroY != puzzle.length - 1) {
                    return true;
                }

                break;
            case LEFT:
                if (zeroX != 0) {
                    return true;
                }

                break;
            case RIGHT:
                if (zeroX != puzzle[zeroY].length - 1) {
                    return true;
                }

                break;
        }

        return false;
    }

    public void move(DIRECTION direction) {
        switch (direction) {
            case UP:
                swap(zeroY, zeroX, (zeroY - 1), zeroX);
                path += "U";

                break;
            case DOWN:
                swap(zeroY, zeroX, (zeroY + 1), zeroX);
                path += "D";

                break;
            case LEFT:
                swap(zeroY, zeroX, zeroY, (zeroX - 1));
                path += "L";

                break;
            case RIGHT:
                swap(zeroY, zeroX, zeroY, (zeroX + 1));
                path += "R";

                break;
        }
    }

    private void swap(int y1, int x1, int y2, int x2) {
        int previous = getTile(y1, x1);

        setTile(y1, x1, getTile(y2, x2));
        setTile(y2, x2, previous);

        zeroY = y2;
        zeroX = x2;
    }

    private void setTile(int y, int x, int tile) {
        puzzle[y][x] = tile;
    }

    private int getTile(int y, int x) {
        return puzzle[y][x];
    }

    private void findZeroTile() {
        for (int y = 0; y < puzzle.length; ++y) {
            for (int x = 0; x < puzzle[y].length; ++x) {
                if (puzzle[y][x] == 0) {
                    zeroY = y;
                    zeroX = x;
                }
            }
        }
    }

    public String getPath() {
        return path;
    }

    public int[][] getPuzzle() {
        return puzzle;
    }

    @Override
    public String toString() {
        StringBuilder output = new StringBuilder();

        for (int y = 0; y < puzzle.length; ++y) {
            for (int x = 0; x < puzzle[y].length; ++x) {
                output.append(puzzle[y][x]).append(" ");
            }

            output.append(System.lineSeparator());
        }

        return output.toString();
    }
}