Backtracking pathinding problem in Python

Question

Recently, I've found out about backtracking and without much thinking started on the book from the guy who has shown some Sudoku backtracking tricks (https://www.youtube.com/watch?v=G_UYXzGuqvM&ab_channel=Computerphile. Unfortunately, I'm stuck with the first backtracking problem without the solution.

The problem is formulated accordingly: Use backtracking to calculate the number of all paths from the bottom left to the top right corner in a x * y-grid. This includes paths like https://i.sstatic.net/46YLb.jpg. Note that every point can only be visited once. Write a function np(x,y) that returns the number of paths in a x*y-grid. E.g. np(2,3) should return 38. Hint: Create a grid of booleans where you mark the positions already visited.

Whatever I change in this short block of code I'm landing nowhere near 38.

```
grid = [[0, 0,  0, 0,  0, 1],
        [0, 0,  0, 0,  0, 0],
        [0, 0,  0, 0,  0, 0],
        [1, 0,  0, 0,  0, 0]]

solution = 0
def number_of_paths(x, y):
    global solution
    global grid
    for i in range(0, x):
        for j in range(0, y):
            if grid[i][j] == 0:
                grid[i][j] = 1
                number_of_paths(x, y)
                grid[i][j] = 0
                solution += 1
    return




if __name__ == '__main__':
    number_of_paths(2, 3)
    print(grid)
    print(solution)```

That's a sample solution with solution with Sudoku solver.

```
grid = [[5, 3, 0, 0, 7, 0, 0, 0, 0], 
       [6, 0, 0, 1, 9, 5, 0, 0, 0],
       [0, 9, 8, 0, 0, 0, 0, 6, 0],
       [8, 0, 0, 0, 6, 0, 0, 0, 3],
       [4, 0, 0, 8, 0, 3, 0, 0, 1],
       [7, 0, 0, 0, 2, 0, 0, 0, 6],
       [0, 6, 0, 0, 0, 0, 2, 8, 0],
       [0, 0, 0, 4, 1, 9, 0, 0, 5], 
       [0, 0, 0, 0, 8, 0, 0, 7, 9]]

import numpy as np

def possible(y, x, n):
    global grid
    for i in range(0, 9):
        if grid[y][i] == n:
            return False
    for i in range(0, 9):
        if grid[i][x] == n:
            return False
    x0 = (x // 3) * 3
    y0 = (y // 3) * 3
    for i in range(0, 3):
        for j in range(0, 3):
            if grid[y0 + i][x0 + j] == n:
                return False
    return True

def solve():
    global grid
    for y in range(9):
        for x in range(9):
            if grid[y][x] == 0:
                for n in range(1, 10):
                    if possible(y, x, n):
                        grid[y][x] = n
                        solve()
                        # backtracking - bad choice
                        grid[y][x] = 0
                return
    print(np,matrix(grid))
    input("More?")```

Answer 1

A few suggestions:

1. You might want to use a set for a grid, adding a square as soon as it is visited, if it is not a member of the set yet.
2. The counter and the grid can be global but it would probably be easier for you to take them as arguments for the function at first. After the solution is clearer you can worry about those details.
3. You are going about the problem the wrong way. It would be good to have one function calculating the number of paths from the origin to the destination (by calling the function for the neighbors that have not been visited yet. Make sure you update the grid). On top of that you can have a function that calls the path function for every combination of origin and destination. A small tip: You do not have to calculate the same path in reverse direction! You can have a map of calculate sums of paths. If the opposite direction has been calculate, don't bother. Later, double the amount of paths by 2.

Good luck!