"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

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

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

"How to count Fukashigi"
How to use xml.etree.ElementTree
How to use Python-shell
How to use tf.data
How to use virtualenv
Scraping 2 How to scrape
How to use Seaboan
How to use image-match
How to use shogun
How to install Python
How to read PyPI
How to install pip
How to use Virtualenv
How to use numpy.vectorize
How to update easy_install
How to install archlinux
How to use pytest_report_header
How to restart gunicorn
How to virtual host
How to debug selenium
How to use partial
How to use Bio.Phylo
How to read JSON
How to use SymPy
How to use x-means
How to use WikiExtractor.py
How to update Spyder
How to install BayesOpt
How to use virtualenv
How to use Matplotlib
How to use iptables
How to use numpy
How to use TokyoTechFes2015
How to use venv
How to use Pyenv
How to use list []
How to use python-kabusapi
How to install Nbextensions
How to use OptParse
How to count numbers in a specific range
How to use return
How to install Prover9
How to use dotenv
How to operate NumPy
How to use pyenv-virtualenv
How to use Go.mod
How to use imutils
How to use import
How to estimate kernel density
How to use Qt Designer
[IPython] How to Share IPython Notebook
How to install Python [Windows]
How to use search sorted
python3: How to use bottle (2)
Understand how to use django-filter
XPath Basics (2) -How to write XPath
How to use the generator
Tabpy 1.0 (2020-01 version) How to install
How to change Jupyter layout
How to call a function
How to update Python Tkinter to 8.6