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();
    }
}

 



Java 15 Puzzle Solver Using BFS
Tagged on:         

Leave a Reply

Your email address will not be published. Required fields are marked *

By continuing to use the site, you agree to the use of cookies. You can read more about it the Cookies&Privacy Policy Section Above. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this. You can read more about it the Cookies&Privacy Policy Section.

Close