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).

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.

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 source code of the script Lattice Path online. Except explicit open source licence (indicated Creative Commons / free), any algorithm, applet, snippet, software (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any function (convert, solve, decrypt, encrypt, decipher, cipher, decode, code, translate) written in any informatic langauge (PHP, Java, C#, Python, Javascript, Matlab, etc.) which dCode owns rights will not be released for free. To download the online Lattice Path script for offline use on PC, iPhone or Android, ask for price quote on contact page !

Source : https://www.dcode.fr/lattice-path

© 2020 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaches. dCode

Feedback

▲