A212715 - OEIS

%I #6 May 25 2012 14:28:37

%S 1,0,2,138,88920,752404294

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

%e 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.

%e When n=8 this is the number of ways to move a knight from a1 to h8 without occupying any cell twice.

%o (C)

%o #include <stdio.h>

%o int WIDTH, HEIGHT;

%o char grid[16][16];

%o int calc_ways(int x, int y) {

%o     if (!((unsigned)x<WIDTH && (unsigned)y<HEIGHT)) return 0;

%o     if (grid[x][y]) return 0;

%o     if (x+y==WIDTH+HEIGHT-2) return 1;

%o     grid[x][y]=1;

%o     int n;

%o     n =calc_ways(x-2,y-1);

%o     n+=calc_ways(x-2,y+1);

%o     n+=calc_ways(x-1,y-2);

%o     n+=calc_ways(x-1,y+2);

%o     n+=calc_ways(x+1,y-2);

%o     n+=calc_ways(x+1,y+2);

%o     n+=calc_ways(x+2,y-1);

%o     n+=calc_ways(x+2,y+1);

%o     grid[x][y]=0;

%o     return n;

%o }

%o int main(int argc, char **argv)

%o {

%o   for (int i=1; i<8; ++i) {

%o     WIDTH=HEIGHT=i;

%o     memset(grid, 0, sizeof(grid));

%o     printf("%2d : %d\n",i,calc_ways(0,0));

%o   }

%o }

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

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

%Y Cf. A140518 : king paths.

%K nonn,walk

%O 1,3

%A _Alex Ratushnyak_, May 24 2012