Pathfinding in Java, stepping on each tile once

Question

I'm currently facing a problem with pathfinding on a map of tiles: I have an ArrayList<ArrayList<Byte>>, which determines if the tile at list.get(y).get(x) is blocked or not, and the starting position. Now I want to know if there is a path, starting at the origin, which goes over each non-blocked tile once, and if there is, I want the directions printed out, like 'NWWEW'. I already have got the part of checking if each non-blocked tile is connected to all others (thus, there should be only one area of connected non-blocked tiles) by using floodfill, but I still need an idea on how to go on with the 'path-but-each-tile-only-once'-thing.

If anyone has got any ideas or algorithms, I'd be thankful for answers

Edit: Alright, I think I've got it, but since the question was closed, I'll have to write the solution here:

(Thanks to @Jack for pointing me in the right direction) First of all, the program checks if the current tile is walkable; it'll then be marked as visited and the direction how it has been accessed is added to the directions-string. After that, I call this function recursively for each direction until the length of the total-directions-string is equal to the total number of accessible tiles on the whole map -1. If it's not equal, it removes the direction in which itself has been accessed and returns to the upper layer.

Code:

public static void findPath(int x, int y, String direction){

    if(pathFound)
        return;

    if(map.get(y).get(x) == 0){

        map.get(y).set(x, (byte) 1);

        directions += direction;

        findPath(x, y-1, "N");
        findPath(x, y+1, "S");
        findPath(x-1, y, "W");
        findPath(x+1, y, "O");

        if(directions.length() == totalFreeTiles-1){
            pathFound = true;
            return;
        }

        if(directions.length() > 0)
            directions = directions.substring(0, directions.length()-1);

        map.get(y).set(x, (byte) 0);

    }
}

Answer 1

You can achieve the goal by implementing a backtracking algorithm.

I would use two global variable: the resulting string (let's call it "direction" initialized to empty) and a matrix (let's call it "matrix") of a three-state type. That is:

• Tile not yet visited
• Tile already visited
• Tile blocked by starting parameter

Then implement a routine that given a tile and a direction used to reach it, explore adjacent tiles recursively. The routine should do this:

• If tile is already visited or blocked, then return
• If tile is visible mark the matrix[current-tile] as visited
• Update "direction" by adding the direction used to reach this tile
• If there are no more free tiles then print "direction" and you've won
• otherwise recursively call the routine on all 8 adjacent tiles
• then remove the last direction from "direction", mark matrix[current-tile] as not yet visited and return

As prototype of routine I suggest using indexes the matrix, so you can easily check for matrix borders