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

1, 0, 2, 138, 88920, 752404294

Offset

1,3

Links

Table of n, a(n) for n=1..6.

Example

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.

Prog

(C)
#include <stdio.h>
int WIDTH, HEIGHT;
char grid[16][16];
int calc_ways(int x, int y) {
    if (!((unsigned)x<WIDTH && (unsigned)y<HEIGHT)) return 0;
    if (grid[x][y]) return 0;
    if (x+y==WIDTH+HEIGHT-2) return 1;
    grid[x][y]=1;
    int n;
    n =calc_ways(x-2, y-1);
    n+=calc_ways(x-2, y+1);
    n+=calc_ways(x-1, y-2);
    n+=calc_ways(x-1, y+2);
    n+=calc_ways(x+1, y-2);
    n+=calc_ways(x+1, y+2);
    n+=calc_ways(x+2, y-1);
    n+=calc_ways(x+2, y+1);
    grid[x][y]=0;
    return n;
}
int main(int argc, char **argv)
{
  for (int i=1; i<8; ++i) {
    WIDTH=HEIGHT=i;
    memset(grid, 0, sizeof(grid));
    printf("%2d : %d\n", i, calc_ways(0, 0));
  }
}

Crossrefs

Cf. A007764 : rook paths (with moves of unit length).

Cf. A038496 : bishop paths (with moves of unit length).

Cf. A140518 : king paths.

Sequence in context: A087619 A157072 A051029 * A329594 A084560 A054681

Adjacent sequences: A212712 A212713 A212714 * A212716 A212717 A212718

Keyword

nonn,walk

Author

Alex Ratushnyak, May 24 2012

Status

approved