cp's OEIS Frontend

A215577 Number of nonintersecting (or self-avoiding) rook paths joining opposite corner cells of an n X n X n grid, avoiding cells that are not on the surface.

%I A215577 #4 Aug 16 2012 16:31:10
%S A215577 1,18,340812,1553113040
%N A215577 Number of nonintersecting (or self-avoiding) rook paths joining opposite corner cells of an n X n X n grid, avoiding cells that are not on the surface.
%C A215577 When n<3 there are n^3 cells available, otherwise n^3 - (n-2)^3.
%C A215577 The length of the step is 1. The length of the path varies.
%o A215577 (C)
%o A215577 #include <stdio.h>    // GCC -O3
%o A215577 char grid[4][4][4];
%o A215577 long long SIZE;
%o A215577 long long calc_ways(long long x, long long y, long long z) {
%o A215577     long long n;
%o A215577     if (grid[x][y][z]) return 0;
%o A215577     if (x+y+z==SIZE*3-3) return 1;
%o A215577     grid[x][y][z]=1;
%o A215577     n=0;
%o A215577     if (x>0)        n =calc_ways(x-1,y,z);  // go left
%o A215577     if (x<SIZE-1)   n+=calc_ways(x+1,y,z);  // right
%o A215577     if (y>0)        n+=calc_ways(x,y-1,z);  // down
%o A215577     if (y<SIZE-1)   n+=calc_ways(x,y+1,z);  // up
%o A215577     if (z>0)        n+=calc_ways(x,y,z-1);  // level down
%o A215577     if (z<SIZE-1)   n+=calc_ways(x,y,z+1);  // level up
%o A215577     grid[x][y][z]=0;
%o A215577     return n;
%o A215577 }
%o A215577 int main()
%o A215577 {
%o A215577   for (SIZE=1; SIZE<=4; ++SIZE) {
%o A215577     int x,y,z;
%o A215577     memset(grid, 0, sizeof(grid));
%o A215577     for (x=1; x<SIZE-1; ++x)
%o A215577       for (y=1; y<SIZE-1; ++y)
%o A215577         for (z=1; z<SIZE-1; ++z)
%o A215577           grid[x][y][z]=1;
%o A215577     printf("%llu, ",calc_ways(0,0,0));
%o A215577   }
%o A215577 }
%Y A215577 Cf. A007764, A059783.
%K A215577 nonn,walk,more
%O A215577 1,2
%A A215577 _Alex Ratushnyak_, Aug 16 2012