Calculate the number of paths in a grid from top left to bottom right

I need to calculate the number of paths from top left to right bottom where a valid path is path that crosses all the squares in the grid (and exactly once for every square)

I'm using the backtracking technique. Unfortunately, count is 0 in the end of the calculation. Printing t, I see that it never gets to n-1.

What's wrong with my algorithm?

n = 4
count = 0
m = [[False for x in range(n)] for y in range(n)] 

def num_of_paths(m, x, y, t):

    print(t)

    global count

    # check if we reached target
    if x == (n - 1) and y == (n - 1):
        if t < (n * n):
            # not on time, prune the tree here
            return 
        elif t == n * n:
            # completed a full path in the grid and on time
            count += 1 

    if t > n * n:
        return

    # Right
    if x + 1 < n and m[x + 1][y] == False:
        m[x + 1][y] = True
        num_of_paths(m, x + 1, y, t + 1)
        m[x + 1][y] = False

    # Left
    if x - 1 > 0 and m[x - 1][y] == False:
        m[x - 1][y] = True
        num_of_paths(m, x - 1, y, t + 1)
        m[x - 1][y] = False

    # Down
    if y + 1 < n and m[x][y + 1] == False:
        m[x][y + 1] = True
        num_of_paths(m, x, y + 1, t + 1)
        m[x][y + 1] = False

    # Up
    if y - 1 > 0 and m[x][y - 1] == False:
        m[x][y - 1] = True
        num_of_paths(m, x, y - 1, t + 1)
        m[x][y - 1] = False


num_of_paths(m, 0, 0, 0)
print(count)

There are the following issues:

• The starting cell is not marked with m[0][0] = True, so after going right, the algorithm will go left again, and actually visit that cell twice. To resolve this, you can move the code for managing the m values away from where you have it now (4 times) and apply it to the current cell (once). This includes the if m[..][..] check, and the assignments of True and False.
• The if conditions that relate to the left and up directions should compare the coordinate with >= 0, not with > 0: a zero value for a coordinate is still within range.
• t should start with 1, since you compare its value with n * n. Or else you should compare with n * n - 1. In my correction below I will start with t = 1.
• Not a real problem, but after doing count += 1 it would make sense to immediately return, since there is no possibility anymore to extend the path further.

Some other remarks:

• When n is even, there is no valid path, so even when corrected, the function is bound to return 0 in that case
• The number of paths this algorithm visits is exponential, O(2^n²). For n > 6, don't wait for it...

Here is a corrected version of your code. Comments should clarify what was changed and why:

n = 5
count = 0
m = [[False for x in range(n)] for y in range(n)] 

def num_of_paths(m, x, y, t):
    global count
    # Moved the "visited" check to here. No need to add `== True`.
    if m[x][y]: 
        return
    if x == (n - 1) and y == (n - 1):
        if t < (n * n):
            return 
        else: # Removed the unnecessary condition here
            count += 1 
            # Added a return here
            return
    # Removed an if-block of which the condition could never be true
    # Moved the "visited" marking to here:
    m[x][y] = True
    if x + 1 < n:
        num_of_paths(m, x + 1, y, t + 1)
    # Corrected "> 0" to ">= 0"
    if x - 1 >= 0:
        num_of_paths(m, x - 1, y, t + 1)
    if y + 1 < n:
        num_of_paths(m, x, y + 1, t + 1)
    # Corrected "> 0" to ">= 0"
    if y - 1 >= 0:
        num_of_paths(m, x, y - 1, t + 1)
    # Moved the "visited" unmarking to here:
    m[x][y] = False

# Corrected the last argument
num_of_paths(m, 0, 0, 1)
print(count)