DFS method not producing expected output

Question

So the goal is to print all possible numbers whose digits can be formed by a sequence of adjacent characters on a board using dfs. By adjacent I mean next to each other, either vertically, horizontally or diagonally. There are 8 total movement directions. Ex: the board below

1 2
3 4

To make it simpler let's say that we always have to start at row0 column0, which is 1. So the possible numbers are: 1, 12, 13, 14, 123, 124, 132, 134, 142, 143, 1234, etc (this case is pretty trivial because all numbers are directly adjacent to each other) So I have the following code:

static char[][] grid;
static int rows;
static int columns;

public static void main(String[] args) {
    //test grid. made it small so that solutions are easy to count
    grid = new char[][]{
            new char[]{'1', '2'},
            new char[]{'3', '4'},
    };
    rows = grid.length;
    columns = grid[0].length;
    dfs(0, 0, new boolean[rows][columns], new StringBuilder());
}

public static void dfs(int row, int col, boolean[][] visited, StringBuilder builder){
    visited[row][col] = true;
    builder.append(grid[row][col]);
    System.out.println(builder.toString());
    //the 2 loops are for the 8 movement directions
    for(int x = -1; x <= 1; x++){
        for(int y = -1; y <= 1; y++){
            //index bounds check
            if((row + x >= 0) && (row + x < rows) && (col + y >= 0) && (col + y < columns)){
                if(!visited[row + x][col + y]){
                    dfs(row + x, col + y, visited, builder);
                    // I tried changing it so that it passes a COPY of 'visited' and 'builder',
                    // but output still the same
                    dfs(row + x, col + y, Arrays.copyOf(visited, visited.length), new StringBuilder(builder));
                }

            }
        }
    }
}

My code's output is not right. Here's what it prints:

1
12
123
1234

Those numbers are part of the solution, but are a lot more numbers than that. The error probably has something to do with passing the same object into the recursive dfs() call, but I tried changing it so that it only copies the object, and it still gives the same output. Any ideas?

Answer 1

You should be able to do achieve the expected output without creating a copy of the visited matrix.

The important thing is to set visited[row][col] to false after each COMPLETE visit down a path.

Example:

Let's say you've traversed '12' and now have '3' and '4' left to visit. In the current state, visited matrix's values for '1' and '2' are set to true and for '3' and '4' are set to false. Once you have finished generating all strings that begin with '12', you will start looking at all strings beginning with '13'.

But look at what happens here! You had set the visited value of '2' to true, and so no future strings containing '2' will ever be generated.

This is why you must set visited[row][col] to false after you are done generating all paths from that point onward.

To truly understand this, trace your code with pen and paper and you will remember it better.

Note:

In reality, in the example described above, you will never generate strings beginning with '13' because visited[1][1] would have been set to true before and so 3 would have never been reached again. I ignored that fact to illustrate a point.

Why do I suggest not making a deep copy of visited each recursive call? Simple, to save time and space. Each call will take O(m*n) space and time to generate and store a new visited matrix.

Here is one variant of the correct code:

import java.util.*;

public class DFS{

    static char[][] grid;
    static int rows;
    static int columns;

    public static void main(String[] args) {
        //test grid. made it small so that solutions are easy to count
        grid = new char[][]{
                new char[]{'1', '2'},
                new char[]{'3','4'},
        };
        rows = grid.length;
        columns = grid[0].length;
        ArrayList<String>list = new ArrayList<>();
        dfs(0, 0, new boolean[rows][columns], new StringBuilder());
        //System.out.println(list);
    }

    public static void dfs(int row, int col, boolean[][] visited, StringBuilder builder){
        visited[row][col] = true;
        builder.append(grid[row][col]);
        System.out.println(builder);

        for(int x = -1; x <= 1; x++){
            for(int y = -1; y <= 1; y++){
                //index bounds check
                if((row + x >= 0) && (row + x < rows) && (col + y >= 0) && (col + y < columns)){
                    if(!visited[row + x][col + y]){
                        dfs(row + x, col + y, visited, builder);
                    }

                }
            }
        }
        visited[row][col]=false;
        builder.deleteCharAt(builder.length()-1);
    }
}

EDIT: I forgot to highlight the last line of code added where I delete the last character of the current StringBuilder. This is the backtracking bit so that after all '12xx' strings are generated, you delete '2', replace it with '3' and now start exploring the '13xx' family of strings.