complexity of brute force array traversal

If I have a 4x4 grid for example and I want to start at an arbitrary cell (i,j) and then want to travel down every path without crossing over on myself, what is the complexity (big o) of this? I have written the following code:

traverse(int[][]grid, int i, int j, boolean[][] visited){
    for(int x = -1; x<=1; x++){
       for(int y=-1; y<=1; y++){
           if(inBounds(grid, i+x, j+y), !visited[i+x][j+y]){
              traverse(grid, i+x, j+y, copyOfAndSet(visited, i+x, j+y));
           }
       }
    }
}

assume inBounds exists and copyOfAndSet exists and is O(1) (not O(n*n)) as I have implemented this with bitwis开发者_运维技巧e operations but for clarity have used an array of booleans here.

What is the running time of the algorithm above on a NxN grid.

Thanks

First of all your algorithm can traverse diagonally, I'm not sure that's what you wanted... second: it should first visit the starting node (do a copyOfAndSet), but your algorithm first moves to the direction (-1, -1).

When traversing the array the algorithm visits every node and in every node it checks the 9 neighbours (it should check 8 BTW, (0, 0) doesn't make sense). For the NxN grid this is 9*N*N or simply O(N^2) If copyOfAndSet does actually copy the array then it's N*N work for each cell so it's O(N^4).

If I understand your question, you want to enumerate all self avoiding walks on a 2D grid. (You said "travel down every path without crossing over on myself")

You can find several papers about this by googling for these keywords.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.5913

The problem seems to be #P-complete, according to the paper.