Java finding full routes in NxN grid

Question

So I am trying to make an algorithm for finding full paths in NxN grid. For example in 1x1 grid there is 1 possible path, in 2x2 grid there is 1, in 3x3 there is 2 and in 4x4 there is 8. The idea is to find scenarios where we can fill every spot of the grid by moving.

I have made a recursive function for the job and here is the code:

public static int getRoutesHelp(int[][] table, int x, int y)
    {

        if(x > table.length-1 || x < 0 || y < 0 || y > table.length-1)
            return 0;

        if(table[x][y] == 1)
            return 0;

        table[x][y] = 1;

        if(isDeadEnd(table, x, y))
        {
            if(isTableFull(table))
                return 1;

        }
        else
        {
            int a = getRoutesHelp(table, x-1, y);
            int d = getRoutesHelp(table, x, y+1);
            int b = getRoutesHelp(table, x+1, y);
            int c = getRoutesHelp(table, x, y-1);
            return a+b+c+d;
        }

        return 0;
    }

    public static int getRoutes(int size)
    {
        int[][] table = new int[size][size];

        // init table

        for(int i = 0; i < size; i++)
        {
            for(int a = 0; a < size; a++)
            {
                table[i][a] = 0;
            }
        }


        return getRoutesHelp(table, 0 ,0);
    }

So basically I start from 0.0 and start moving to all possible directions and by repeating this I get the amount of successful routes. The problem is that after the assignment of int d the original table is somehow filled with 1 but it should be empty as far as I understand because java passes a copy of the table right? I've been fighting with this for like 4 hours and can't really find the problem so any help is appreciated. Empty slots in table are marked with 0 and filled slots with 1.

EDIT: I managed to fix the issue I had with the copying and now my other problem is that with 5x5 grid my algorithm returns 52 routes and it should be 86. So it works with 4x4 grid okay, but once I move further it breaks.

Added the isDeadEnd function here

public static boolean isDeadEnd(int[][] table, int x, int y)
    {

        int toCheck[] = new int[4];
        toCheck[0] = x-1; // left
        toCheck[1] = y-1; // top
        toCheck[2] = x+1; // right
        toCheck[3] = y+1; // bottom

        int valuesOfDirections[] = new int[4]; // left, top, right, bottom

        for(int i = 0; i < 4; i++)
        {
            int tarkastettava = toCheck[i];
            if(tarkastettava > table.length-1 || tarkastettava < 0)
            {
                valuesOfDirections[i] = 1;
            }
            else
            {
                if(i == 0 || i == 2)
                {
                    valuesOfDirections[i] = table[tarkastettava][y];
                }
                else
                {
                    valuesOfDirections[i] = table[x][tarkastettava];
                }
            }
        }

        for(int i = 0; i < 4; i++)
        {
            if(valuesOfDirections[i] == 0)
            {
                return false;
            }
        }

        return true;

    }

Array is reference type. So you have only one copy of your table. to fix your code you need to add `table[x][y] = 0` before returning from recursion — talex, Oct 17 '14 at 15:15
I tried using the .clone() also when passing the table but the same thing happened. What should I do to prevent this? — Samuli Lehtonen, Oct 17 '14 at 15:34
clone never really worked. You'll have to make copies of your table. If you manage it properly, there should never be more than one copy by level of recursion. Otherwise, you can consider backtracking. — njzk2, Oct 17 '14 at 15:57
I solved the clone problem by fully cloning it with my own function. — Samuli Lehtonen, Oct 17 '14 at 15:59

score 0 · Answer 1 · answered Oct 17 '14 at 16:01

Come to think of it, you probably can do a simple backtrack here:

table[x][y] = 1;

if(isDeadEnd(table, x, y)) {
    if(isTableFull(table))
        return 1;
    }
    table[x][y] = 0;
}

And later:

int res = a + b + c + d;
if (res == 0) {
    // backtrack here too
    table[x][y] = 0;
}
return res;

Java finding full routes in NxN grid

1 Answers1