cp's OEIS Frontend

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

%I A212715 #6 May 25 2012 14:28:37
%S A212715 1,0,2,138,88920,752404294
%N A212715 Number of nonintersecting (or self-avoiding) knight paths joining opposite corners of an n X n grid.
%e A212715 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 A212715 When n=8 this is the number of ways to move a knight from a1 to h8 without occupying any cell twice.
%o A212715 (C)
%o A212715 #include <stdio.h>
%o A212715 int WIDTH, HEIGHT;
%o A212715 char grid[16][16];
%o A212715 int calc_ways(int x, int y) {
%o A212715     if (!((unsigned)x<WIDTH && (unsigned)y<HEIGHT)) return 0;
%o A212715     if (grid[x][y]) return 0;
%o A212715     if (x+y==WIDTH+HEIGHT-2) return 1;
%o A212715     grid[x][y]=1;
%o A212715     int n;
%o A212715     n =calc_ways(x-2,y-1);
%o A212715     n+=calc_ways(x-2,y+1);
%o A212715     n+=calc_ways(x-1,y-2);
%o A212715     n+=calc_ways(x-1,y+2);
%o A212715     n+=calc_ways(x+1,y-2);
%o A212715     n+=calc_ways(x+1,y+2);
%o A212715     n+=calc_ways(x+2,y-1);
%o A212715     n+=calc_ways(x+2,y+1);
%o A212715     grid[x][y]=0;
%o A212715     return n;
%o A212715 }
%o A212715 int main(int argc, char **argv)
%o A212715 {
%o A212715   for (int i=1; i<8; ++i) {
%o A212715     WIDTH=HEIGHT=i;
%o A212715     memset(grid, 0, sizeof(grid));
%o A212715     printf("%2d : %d\n",i,calc_ways(0,0));
%o A212715   }
%o A212715 }
%Y A212715 Cf. A007764 : rook paths (with moves of unit length).
%Y A212715 Cf. A038496 : bishop paths (with moves of unit length).
%Y A212715 Cf. A140518 : king paths.
%K A212715 nonn,walk
%O A212715 1,3
%A A212715 _Alex Ratushnyak_, May 24 2012