Tool to calculate all paths on a lattice graphe (square grid graph). A path is a series of directions (north, south, east, west) to connect two points on a grid.
Lattice Path - dCode
Tag(s) : Graph Theory
dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day!
A suggestion ? a feedback ? a bug ? an idea ? Write to dCode!
The information on this page is for a square grid and is not valid on triangular grids (or other non square lattice graphs).
The calculation of the number of paths (of length $ a + b $) on a grid of size (a x b) (limited to a north-south direction and a west-east direction) uses combinatorics tools such as the binomial coefficient $ \binom{a+b}{a} $
The north direction N consists of moving up one unit along the ordinate (0,1).
The east direction E consists of moving one unit to the right along the abscissa (1,0).
Example: To go from the point $ (0, 0) $ to the point $ (2, 2) $ (which corresponds to a 2x2 grid) using only north and east. (N,N,E,E), (N,E,N,E), (N,E,E,N), (E,N,E,N), (E,N,N,E), (E,E,N,N) so 6 paths and is computed $ \binom{4}{2} = 6 $
A grid graph is the name given to a bounded grid (with borders).
To generate the list of all paths, use the permutation generator.
Example: N,N,N,E has 4 distinct permutations: (N,N,N,E) (N,N,E,N) (E,N,N,N) (N,E,N,N)
dCode retains ownership of the online 'Lattice Path' tool source code. Except explicit open source licence (indicated CC / Creative Commons / free), any 'Lattice Path' algorithm, applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any 'Lattice Path' function (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and no data download, script, copy-paste, or API access for 'Lattice Path' will be for free, same for offline use on PC, tablet, iPhone or Android ! dCode is free and online.
Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!
Thanks to your feedback and relevant comments, dCode has developed the best 'Lattice Path' tool, so feel free to write! Thank you!