CODEWITHSUNDEEP
c++algorithmrecursiongraphbig-o
ordinary
ordinary

Reputation: 6133

Finding all paths through a 4x4 grid

how do you go about solving this problem ::

A robot is located at the top-left corner of a 4x4 grid. The robot can move either up, down, left, or right, but can not visit the same spot twice. The robot is trying to reach the bottom-right corner of the grid.

My ideas:

Backtracking solution where we go through the tree of all solutions and print once we reach goal cell. I implemented that but I'm not sure if it's correct or makes sense, or if it is even the right approach. I've posted code here and would much appreciate if someone could explain what's wrong with it.

Recursive solution where I start at start cell, and find the path to the goal cell from each of its neighboring cells recursively, with the base case being hitting the goal cell.

QUESTIONS:

1) Are these two ways of expressing the same idea?

2) Do these ideas even make sense?

3) What is the time complexity of each of these solutions? I think the second one is 4^n?

4) Does my backtracking code make sense?

5) Is there a much simpler way to do this?

Here is my code, which prints the correct number of paths for N = 4. Is it correct?

#define N 4
int counter = 0;
bool legal_move(int x, int y, int array[N+2][N+2]){
  bool ret = (array[x][y] == 1);
  array[x][y] = 0;
  return ret;
}

/*
void print_array(int array[N+2][N+2]){
  for(int i = 0; i < N+2; i++){
    for(int j = 0; j < N+2; j++)
      cout << array[i][j] << " ";
    cout << endl;
  }
  cout << endl << endl;
}
*/

void print_paths(int x, int y, int n, int m, int array[N+2][N+2]){
  if(x == n && y == m){
    print_array(array);
    counter++;
  }
  else {
    int dx = 1;
    int dy = 0;
    for(int i = 0; i < 4; i++){
      if(legal_move(x + dx, y + dy, array)){
        print_paths(x + dx, y + dy, n, m, array);
        array[x+dx][y+dy] = 1;
      }
      swap(dx,dy);
      if(i == 1)
        dx = -dx;
    }
  }
}

int main(){

  int array[N+2][N+2];

  for(int i = 1; i < N+1; i++)
    for(int j = 1; j < N+1; j++)
      array[i][j] = 1;

  for(int i = 0; i < N+2; i++)
    array[0][i] = array[i][0] = array[N+1][i] = array[i][N+1] = 0;

//print_array(array);
  array[1][1] = 0;  //Set start cell to be seen.
  print_paths(1,1,N,N,array);
  cout << counter << endl;
}

Upvotes: 1

Views: 2685

Answers (2)

anatolyg
anatolyg

Reputation: 28300

Here is a partial answer, which talks mostly about complexity (I think your code is correct, after the minor bugfix suggested by john, and backtracking is probably the simplest way to do what you want).

The time complexity seems something like O(3^n^2) to me - there are at most n^2 nodes, and at each node you want to check 3 possibilities. There are actually less nodes, because of the way backtracking works, but the complexity is at least O(2^(n^2/4)), so it's greater than any exponential. (the O in the last formula is actually a theta).

The below diagram describes this lower bound. Cells marked by ? have a "decision" in them - the robot may decide to go straight or turn. There are at least n^2/4 such cells, so the number of paths is at least 2^(n^2/4).

?->-?->-?->-V
| | | | | | |
>-^ >-^ >-^ V
            |
V-<-?-<-?-<-?
| | | | | | |
V ^-< ^-< ^-<
|
...

Upvotes: 1

john
john

Reputation: 88017

I think it's the same idea.

The problem with your code is that you haven't implemented 'but can not visit the same spot twice' correctly.

Suppose that your robot has gone from S to A by some path, and you are now examining whether to go to B adjacent to A. The test should be 'has the robot been to B before on the current path'. But what you have implemented is 'has the robot visited B before on any path'.

In other words you need to modify print_paths to take an extra parameter for the current path, and use that to implement the test correctly.

Upvotes: 1

Related Questions