"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.).
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)]))
8512
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
0
(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.
Recommended Posts