[PYTHON] "How to count Fukashigi"

"How to count Fukashigi", the place where you passed the $ n \ times n $ square once The problem of counting the combinations of routes that move from the upper left to the lower right so as not to pass through. I created the most basic process of this self-avoiding walk, that is, the process of counting all combinations in a sister's expression with python.

However, I just created it, and as you can see in the video, the number of combinations increases as the number of squares increases, so this script is not practical at all (Graphillion for decent use. Use (: //github.com/takemaru/graphillion/wiki) etc.).

script

def saw(n, path):
    if -1 in path[-1] \
     or n in path[-1] \
     or path[-1] in path[:-2] : return 0 

    if path[-1]==(n-1,n-1) : return 1

    return saw(n,path+[(path[-1][0]+1, path[-1][1]+0)]) \
         + saw(n,path+[(path[-1][0]-1, path[-1][1]+0)]) \
         + saw(n,path+[(path[-1][0]+0, path[-1][1]+1)]) \
         + saw(n,path+[(path[-1][0]+0, path[-1][1]-1)]) 

n = 5
print(saw(n,[(0,0)]))

Output result

The saw (self-avoiding walk) function is given the number of vertical or horizontal nodes (* number of rectangles + 1 ) and the coordinates of the starting point. The starting point coordinates are given in the form of " list including tuples of starting point coordinates *".

The contents of the saw function are

If the latest coordinates (at the end of the list) are "* outside the range of squares " or " already visited * (coordinates existing in the list)", 0
If the latest coordinates (at the end of the list) are "* destination * (coordinates represented by tuple (n-1, n-1)) ", 1

As a result, the saw is recurred while adding the coordinates with the latest coordinates shifted by one vertically and horizontally to the list, and the returned numerical values are totaled. In other words, the total number of routes that have reached the destination and returned 1 is calculated.