Counting paths in a matrix - Backtracking

Question

Given an M*N matrix, I want to calculate the total number of possible paths from the upper-left cell (0,0) to the lower-right cell (m-1, n-1). Possible movements include up, down, right, and left. A path is considered valid only if it visits each cell c(i, j) exactly once. If going beyond the matrix boundaries or encountering a previously visited cell, the recursion is cut.

if (x < 0 || y < 0 || x >= m || y >= n || grid[x][y] == 1) {
        return;
    }

To limit the number of recursions, I thought of some obvious improvements:

• if reaching the final cell before visiting all cells, the path won't be valid;
• if reaching a border cell, i.e., a cell of the form (i, n-1) or (m-1, j), and the cells immediately above and below (or to the right and left) haven't been visited, then it will be impossible to form valid paths;
• Similarly, if encountering a previously visited cell and having the option to move in two different directions, that path will not be valid (indeed, we are dividing the matrix into two zones of unvisited cells)

I am trying to implement

void CountPath(int x, int y, int n, int m)

in C++ using backtracking, could you suggest me some ways to proceed?

My idea is to maintain a boolean matrix to represent the grid and, at each step, after checking various conditions, call CountPath(x, y, n, m) with modified parameters x, y based on the corresponding movement (setting the cell on which CountPath is called to 1).

EDIT: After doing some tests, I have come up with this code that seems to be working. I still have some issues determining the conditions under which the path encounters a point where it divides the matrix into two zones with unvisited cells. Note that I used a matrix of size N*M for this implementation.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
/*
    N*M matrix

0<=x<M
0<=y<N


*/


void CountPaths(int x, int y, int M, int N, ll &paths, vector<vector<bool>> &grid, int k)
{ 
    if (x == M-1 && y == N-1 && k == N*M){
        paths++;
        return;
    } // correct path

    if (x < 0 || y < 0 || x >= M || y >= N || grid[y][x] == true) {
        return;
    } // beyond boundaries

    if(x == M-1 && y == N-1 && k!=M*N) return; // c(n-1, m-1) - some grid[i][j]=0
    if (y == N-1 && 0<x && x<M-1 && !grid[y][x-1] && !grid[y][x+1]) return; // c(n-1, j)
    if (x == M-1 && 0<y && y<N-1 && !grid[y-1][x] && !grid[y+1][x]) return; // c(i, m-1)
    if (y == 0 && 0<x && x<M-1 && !grid[y][x-1] && !grid[y][x+1]) return; // c(0, j)
    if (x == 0 && 0<y && y<N-1 && !grid[y-1][x] && !grid[y+1][x]) return; // c(i, 0)


    grid[y][x] = 1;
    CountPaths(x + 1, y, N, M, paths, grid, k + 1); // right
    CountPaths(x, y + 1, N, M, paths, grid, k + 1); // down
    CountPaths(x - 1, y, N, M, paths, grid, k + 1); // left
    CountPaths(x, y - 1, N, M, paths, grid, k + 1); // up
    grid[y][x] = 0; // backtracking
}



int main(void){

    int N = 9; // row
    int M = 9; // column
    vector<vector<bool>> grid(N, vector<bool>(M, false));
    ll paths = 0;
    CountPaths(0, 0, M, N, paths, grid, 1);

   //freopen("output.txt", "w", stdout);
    cout << "Number of paths in a " << N << "x" << M << " matrix: " << paths << endl;


    return 0;
}

Answer 1

I can offer you a pseudocode, using guards and list comprehension for brevity and succinctness. It's a simple recursive algorithm.

I'm showing the square N*N case, which you can adapt for your more general rectangular case.

Paths(n) = paths(n, [(0,0)])
paths(n, [p, ...ps])
  | p == (n-1, n-1) = 
      length(ps)==(n^2-1) ? 1 : 0
  | outside?(n, p) = 0
  | member?(p, ps) = 0
  | otherwise = sum [ 
      paths(n, [q, p, ...ps])
      FOR q IN fourDirections(p) ]

Recursion is a problem-solving tool. Its approach is thinking in the small. We just do a simple partition step - here, realizing the 4 possible moves in the simplest terms - then, combine the recursively found results, again in the simplest terms, here, summing up the four results. Letting recursion take care of all the bookkeeping.

The key is designing the algorithm to be independent of other invocations, passing all the info it needs as the arguments. This way, maintaining validity needs no additional attention whatsoever.