This program primary effort is the pathfinding of an 8x8 grid without the use of Java Collection Framework.

The starting cell is at the top left corner and the end is the bottom left corner. All valid moving directions are Up, Down, Left and Right.

A path is only valid when all cells has been visited and only visited once, so a path has 63 moves.

This program accepts user input to act as a constraint and finds all possible paths based on the input.

The inputs are:

• U for Up
• D for Down
• L for Left
• R for Right
• "*" for all of the above

And example input would be:

Input: "*****DR******R******R********************R*D************L******" Total paths: 5739 

My approach to the algorithm is a naive one with DFS, backtracking and pruning for early invalid moves. I've also implemented Multithreading for faster runtime.

However, for the case where every direction is permitted in the 63 moves, the runtime is really long.

My hope is for help on the optimization of the algorithm or perhaps a different approach that ensures a fast runtime when pathfinding all possible paths.

import java.util.Scanner; public class Main { private static final int GRID_SIZE = 8; private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // U, D, L, R private static final char[] DIRECTION_CHARS = {'U', 'D', 'L', 'R'}; private static final int TOTAL_CELLS = GRID_SIZE * GRID_SIZE; private static final int THREAD_COUNT = Runtime.getRuntime().availableProcessors(); private static volatile long totalPaths = 0; private static String pathConstraints = ""; private static volatile boolean isRunning = true; private static long startTime = 0; private static Thread[] workers; private static long[] visitedRows = new long[GRID_SIZE]; private static final long[] POSITION_MASKS = new long[GRID_SIZE]; private static final byte[][][] VALID_MOVES = new byte[GRID_SIZE][GRID_SIZE][]; private static final byte[][][] PRIORITIZED_MOVES = new byte[GRID_SIZE][GRID_SIZE][]; static { for (int i = 0; i < GRID_SIZE; i++) { POSITION_MASKS[i] = 1L << i; } initializeValidMoves(); initializePrioritizedMoves(); } private static void initializeValidMoves() { for (int row = 0; row < GRID_SIZE; row++) { for (int col = 0; col < GRID_SIZE; col++) { int validCount = 0; byte[] temp = new byte[4]; for (byte dir = 0; dir < DIRECTIONS.length; dir++) { int newRow = row + DIRECTIONS[dir][0]; int newCol = col + DIRECTIONS[dir][1]; if (isValidCell(newRow, newCol)) { temp[validCount++] = dir; } } VALID_MOVES[row][col] = new byte[validCount]; System.arraycopy(temp, 0, VALID_MOVES[row][col], 0, validCount); } } } private static void initializePrioritizedMoves() { for (int row = 0; row < GRID_SIZE; row++) { for (int col = 0; col < GRID_SIZE; col++) { byte[] validMoves = VALID_MOVES[row][col]; byte[] prioritized = new byte[validMoves.length]; System.arraycopy(validMoves, 0, prioritized, 0, validMoves.length); // Sort moves by priority for (int i = 0; i < prioritized.length - 1; i++) { for (int j = 0; j < prioritized.length - i - 1; j++) { if (getMovePriority(row, col, prioritized[j]) > getMovePriority(row, col, prioritized[j + 1])) { // Swap byte temp = prioritized[j]; prioritized[j] = prioritized[j + 1]; prioritized[j + 1] = temp; } } } PRIORITIZED_MOVES[row][col] = prioritized; } } } private static int getMovePriority(int currentRow, int currentCol, byte direction) { int newRow = currentRow + DIRECTIONS[direction][0]; int newCol = currentCol + DIRECTIONS[direction][1]; // Calculate the Manhattan distance to the end (7,0) int distanceToEnd = Math.abs(newRow - (GRID_SIZE - 1)) + Math.abs(newCol - 0); // Prioritise Down and Left moves int directionBonus = 0; if (DIRECTION_CHARS[direction] == 'D') directionBonus -= 2; if (DIRECTION_CHARS[direction] == 'L') directionBonus -= 1; return distanceToEnd + directionBonus; } public static class PathFinderTask extends Thread { private final int threadId; private final int startRow; private final int startCol; private final int secondRow; // Adding the position of the 2nd move private final int secondCol; private final int totalThreads; private long pathCount = 0; private final long[] localVisited; public PathFinderTask(int id, int totalThreads, int startRow, int startCol, int secondRow, int secondCol) { this.threadId = id; this.totalThreads = totalThreads; this.startRow = startRow; this.startCol = startCol; this.secondRow = secondRow; this.secondCol = secondCol; this.localVisited = new long[GRID_SIZE]; } @Override public void run() { System.out.println("Thread " + threadId + " starting at positions (" + startRow + "," + startCol + ") -> (" + secondRow + "," + secondCol + ")"); long threadStartTime = System.currentTimeMillis(); // Initialize the initial state with 3 cells that has been passed setLocalVisited(0, 0, true); setLocalVisited(startRow, startCol, true); setLocalVisited(secondRow, secondCol, true); findPathsParallel(3, secondRow, secondCol); // Starting from the 3rd move synchronized(PathFinderTask.class) { totalPaths += pathCount; } long threadEndTime = System.currentTimeMillis(); System.out.println("Thread " + threadId + " completed in " + (threadEndTime - threadStartTime) / 1000.0 + "s. Found " + pathCount + " paths"); } private void setLocalVisited(int row, int col, boolean value) { if (value) { localVisited[row] |= POSITION_MASKS[col]; } else { localVisited[row] &= ~POSITION_MASKS[col]; } } private boolean isLocalCellVisited(int row, int col) { return (localVisited[row] & POSITION_MASKS[col]) != 0; } private void findPathsParallel(int steps, int row, int col) { if (!isRunning) return; if (steps == TOTAL_CELLS) { if (row == GRID_SIZE - 1 && col == 0) { pathCount++; if (pathCount % 1000 == 0) { System.out.println("Thread " + threadId + " found " + pathCount + " paths"); checkAndPrintTime(); } } return; } if (!isPathViableParallel(steps, row, col)) { return; } for (byte dirIndex : PRIORITIZED_MOVES[row][col]) { int newRow = row + DIRECTIONS[dirIndex][0]; int newCol = col + DIRECTIONS[dirIndex][1]; if (!isLocalCellVisited(newRow, newCol)) { char dirChar = DIRECTION_CHARS[dirIndex]; char allowedMove = getConstraint(steps - 1); if (allowedMove == '*' || allowedMove == dirChar) { setLocalVisited(newRow, newCol, true); findPathsParallel(steps + 1, newRow, newCol); setLocalVisited(newRow, newCol, false); } } } } private boolean isPathViableParallel(int steps, int row, int col) { if (row == GRID_SIZE - 1 && col == 0 && steps < TOTAL_CELLS) { return false; } int remainingMoves = TOTAL_CELLS - steps; int distanceToEnd = Math.abs(row - (GRID_SIZE - 1)) + Math.abs(col); if (distanceToEnd > remainingMoves) { return false; } return !hasIsolatedCellsParallel(); } private boolean hasIsolatedCellsParallel() { int unvisitedCount = countUnvisitedCellsParallel(); if (unvisitedCount == 0) return false; long[] tempVisited = new long[GRID_SIZE]; int connectedCells = optimizedFloodFillParallel(tempVisited, findUnvisitedRowParallel(), findUnvisitedColParallel(), unvisitedCount); return connectedCells != unvisitedCount; } private int countUnvisitedCellsParallel() { int count = 0; for (int row = 0; row < GRID_SIZE; row++) { for (int col = 0; col < GRID_SIZE; col++) { if (!isLocalCellVisited(row, col)) { count++; } } } return count; } private int findUnvisitedRowParallel() { for (int row = 0; row < GRID_SIZE; row++) { for (int col = 0; col < GRID_SIZE; col++) { if (!isLocalCellVisited(row, col)) { return row; } } } return -1; } private int findUnvisitedColParallel() { for (int row = 0; row < GRID_SIZE; row++) { for (int col = 0; col < GRID_SIZE; col++) { if (!isLocalCellVisited(row, col)) { return col; } } } return -1; } private int optimizedFloodFillParallel(long[] tempVisited, int row, int col, int unvisitedCount) { if (row < 0 || row >= GRID_SIZE || col < 0 || col >= GRID_SIZE || isLocalCellVisited(row, col) || (tempVisited[row] & POSITION_MASKS[col]) != 0) { return 0; } tempVisited[row] |= POSITION_MASKS[col]; int count = 1; for (int[] dir : DIRECTIONS) { count += optimizedFloodFillParallel(tempVisited, row + dir[0], col + dir[1], unvisitedCount); if (count == unvisitedCount) break; } return count; } } private static boolean isValidCell(int row, int col) { return row >= 0 && row < GRID_SIZE && col >= 0 && col < GRID_SIZE; } private static char getConstraint(int index) { return index < pathConstraints.length() ? pathConstraints.charAt(index) : '*'; } private static void checkAndPrintTime() { long currentTime = System.currentTimeMillis(); long elapsedSeconds = (currentTime - startTime) / 1000; // Print progress every 10 seconds if (elapsedSeconds > 0 && elapsedSeconds % 10 == 0) { synchronized(PathFinderTask.class) { System.out.println("Time elapsed: " + elapsedSeconds + "s, Paths found: " + totalPaths); } } // Limit the maximum runtime to 5 minutes if (currentTime - startTime > 300000) { // 5 minutes System.out.println("Search time exceeded 5 minutes. Stopping..."); isRunning = false; } } private static int calculateTotalMoves() { int count = 0; for (byte dir1 = 0; dir1 < DIRECTIONS.length; dir1++) { int firstRow = DIRECTIONS[dir1][0]; int firstCol = DIRECTIONS[dir1][1]; if (isValidCell(firstRow, firstCol)) { for (byte dir2 = 0; dir2 < DIRECTIONS.length; dir2++) { int secondRow = firstRow + DIRECTIONS[dir2][0]; int secondCol = firstCol + DIRECTIONS[dir2][1]; if (isValidCell(secondRow, secondCol) && (secondRow != 0 || secondCol != 0)) { count++; } } } } return count; } private static void populateMoves(int[][] moves) { int moveIndex = 0; for (byte dir1 = 0; dir1 < DIRECTIONS.length; dir1++) { int firstRow = DIRECTIONS[dir1][0]; int firstCol = DIRECTIONS[dir1][1]; if (isValidCell(firstRow, firstCol)) { for (byte dir2 = 0; dir2 < DIRECTIONS.length; dir2++) { int secondRow = firstRow + DIRECTIONS[dir2][0]; int secondCol = firstCol + DIRECTIONS[dir2][1]; if (isValidCell(secondRow, secondCol) && (secondRow != 0 || secondCol != 0)) { moves[moveIndex][0] = firstRow; moves[moveIndex][1] = firstCol; moves[moveIndex][2] = secondRow; moves[moveIndex][3] = secondCol; moveIndex++; } } } } } private static void userInterface() { Scanner scanner = new Scanner(System.in); System.out.println("Enter path constraints (63 characters of U/D/L/R/* or press Enter for no constraints):"); pathConstraints = scanner.nextLine().trim(); final int maxThreads = Runtime.getRuntime().availableProcessors() * 2; final int totalMoves = calculateTotalMoves(); final int[][] moves = new int[totalMoves][4]; populateMoves(moves); final int numThreads = Math.min(totalMoves, maxThreads); workers = new Thread[numThreads]; startTime = System.currentTimeMillis(); isRunning = true; totalPaths = 0; for (int i = 0; i < numThreads; i++) { final int threadIndex = i; workers[i] = new Thread(() -> { for (int j = threadIndex; j < totalMoves; j += numThreads) { PathFinderTask task = new PathFinderTask( threadIndex, numThreads, moves[j][0], moves[j][1], moves[j][2], moves[j][3] ); task.start(); try { task.join(); } catch (InterruptedException e) { Thread.currentThread().interrupt(); return; } } }); workers[i].start(); } try { for (Thread worker : workers) { worker.join(); } } catch (InterruptedException e) { System.out.println("Search interrupted!"); return; } long endTime = System.currentTimeMillis(); System.out.println("Total paths found: " + totalPaths); System.out.println("Time taken: " + (endTime - startTime) / 1000.0 + " seconds"); } public static void main(String[] args) { userInterface(); } }