A038496 -id:A038496 - cp's OEIS frontend

A140518 Number of simple paths from corner to corner of an n X n grid with king-moves allowed.

1, 5, 235, 96371, 447544629, 22132498074021, 10621309947362277575, 50819542770311581606906543, 2460791237088492025876789478191411, 1207644919895971862319430895789323709778193, 5996262208084349429209429097224046573095272337986011

Offset: 1

Don Knuth, Jul 26 2008

This graph is the "strong product" of P_n with P_n, where P_n is a path of length n. Sequence A007764 is what we get when we restrict ourselves to rook moves of unit length.

Computed using ZDDs (ZDD = "reduced, order, zero-suppressed binary decision diagram").

			For example, when n=8 this is the number of ways to move a king from a1 to h8 without occupying any cell twice.

Donald E. Knuth, The Art of Computer Programming, Vol. 4, fascicle 1, section 7.1.4, p. 117, Addison-Wesley, 2009.

Jens Weise, Evolutionary Many-Objective Optimisation for Pathfinding Problems, Ph. D. Dissertation, Otto von Guercke Univ., Magdeburg (Germany, 2022), see p. 53.

Main diagonal of A329118.
Cf. A140519, A158651, A234622, A007764, A038496.
Cf. A220638 (Hosoya index).

a(9)-a(11) from Andrew Howroyd, Apr 07 2016

A212715 Number of nonintersecting (or self-avoiding) knight paths joining opposite corners of an n X n grid.

Original entry on oeis.org

1, 0, 2, 138, 88920, 752404294

Offset: 1

Alex Ratushnyak, May 24 2012

			When n=3 this is the number of ways to move a knight from a1 to c3 without occupying any cell twice. Only two paths: a1-b3-c1-a2-c3 and a1-c2-a3-b1-c3.
When n=8 this is the number of ways to move a knight from a1 to h8 without occupying any cell twice.

Cf. A007764 : rook paths (with moves of unit length).
Cf. A038496 : bishop paths (with moves of unit length).
Cf. A140518 : king paths.

#include 
int WIDTH, HEIGHT;
char grid[16][16];
int calc_ways(int x, int y) {
    if (!((unsigned)x

cp's OEIS Frontend

A140518 Number of simple paths from corner to corner of an n X n grid with king-moves allowed.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions