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
I’ve tried implementing this same algorithm but instead I loaded the 2D array myself and the while loop in the BFS class appears to never break. I’m not sure if the .poll() is outputting the correct behaviour but I’m still looking into debugging this. If there are any suggestions as to what the behaviour could be attributed by, please let me know.