Find the number of all possible path in a grid, from (0, 0) to (n, n)-CodePudding

I don't know how to find the number of all possible path in a grid, from a Point A to a Point B. The point A is on (0,0) and the point B is on (n,n). A can move up, down, right, and left, and can't move on visited points. While A moving, A(x,y) = (x,y|(0=<x=<n)∩(0=<y=<n)).

CodePudding user response：

I would suggest solving this with naive recursion.

Keep a set visted of places that you have visited. And in pseudo-code that is deliberately not any particular language:

function recursive_call(i, j, visited=none)
    if visited is none then
        visited = set()
    end if
    if i = n and j = n then
        return  1
    else if (i, j) in visited or not in grid then
        return 0
    else
        total = 0
        add (i, j) to visited
        for direction in directions:
            (new_i, new_j) = move(i, j, direction)
            total  = recursive_call(new_i, new_j, visited)
        remove (i, j) from visited
        return total
    end if
end function

CodePudding user response：

You can solve this problem with recursive backtracking, but there's another approach which I think is more interesting.

If we work out the first few cases by hand we find that:

A 1x1 square has 1 path
A 2x2 square has 2 paths
A 3x3 square has 12 paths

If we then go to OEIS (the Online Encyclopedia of Integer Sequences) and put in the search phrase "1,2,12 paths", the very first result is A007764 which is entitled "Number of nonintersecting (or self-avoiding) rook paths joining opposite corners of an n X n grid".

Knowing what integer sequence you're looking for unlocks significant mathematical resources, including source code to generate the sequence, related sequences, and best-known values.

The known values of the sequence are:

1 1
2 2
3 12
4 184
5 8512
6 1262816
7 575780564
8 789360053252
9 3266598486981642
10 41044208702632496804
11 1568758030464750013214100
12 182413291514248049241470885236
13 64528039343270018963357185158482118
14 69450664761521361664274701548907358996488
15 227449714676812739631826459327989863387613323440
16 2266745568862672746374567396713098934866324885408319028
17 68745445609149931587631563132489232824587945968099457285419306
18 6344814611237963971310297540795524400449443986866480693646369387855336
19 1782112840842065129893384946652325275167838065704767655931452474605826692782532
20 1523344971704879993080742810319229690899454255323294555776029866737355060592877569255844
21 3962892199823037560207299517133362502106339705739463771515237113377010682364035706704472064940398
22 31374751050137102720420538137382214513103312193698723653061351991346433379389385793965576992246021316463868
23 755970286667345339661519123315222619353103732072409481167391410479517925792743631234987038883317634987271171404439792
24 55435429355237477009914318489061437930690379970964331332556958646484008407334885544566386924020875711242060085408513482933945720
25 12371712231207064758338744862673570832373041989012943539678727080484951695515930485641394550792153037191858028212512280926600304581386791094
26 8402974857881133471007083745436809127296054293775383549824742623937028497898215256929178577083970960121625602506027316549718402106494049978375604247408
27 17369931586279272931175440421236498900372229588288140604663703720910342413276134762789218193498006107082296223143380491348290026721931129627708738890853908108906396

You can generate the first few terms yourself on paper or via recursive backtracking, per the other answer.