A215577 - OEIS

%I #4 Aug 16 2012 16:31:10

%S 1,18,340812,1553113040

%N 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 When n<3 there are n^3 cells available, otherwise n^3 - (n-2)^3.

%C The length of the step is 1. The length of the path varies.

%o (C)

%o #include <stdio.h>    // GCC -O3

%o char grid[4][4][4];

%o long long SIZE;

%o long long calc_ways(long long x, long long y, long long z) {

%o     long long n;

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

%o     if (x+y+z==SIZE*3-3) return 1;

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

%o     n=0;

%o     if (x>0)        n =calc_ways(x-1,y,z);  // go left

%o     if (x<SIZE-1)   n+=calc_ways(x+1,y,z);  // right

%o     if (y>0)        n+=calc_ways(x,y-1,z);  // down

%o     if (y<SIZE-1)   n+=calc_ways(x,y+1,z);  // up

%o     if (z>0)        n+=calc_ways(x,y,z-1);  // level down

%o     if (z<SIZE-1)   n+=calc_ways(x,y,z+1);  // level up

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

%o     return n;

%o }

%o int main()

%o {

%o   for (SIZE=1; SIZE<=4; ++SIZE) {

%o     int x,y,z;

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

%o     for (x=1; x<SIZE-1; ++x)

%o       for (y=1; y<SIZE-1; ++y)

%o         for (z=1; z<SIZE-1; ++z)

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

%o     printf("%llu, ",calc_ways(0,0,0));

%o   }

%o }

%Y Cf. A007764, A059783.

%K nonn,walk,more

%O 1,2

%A _Alex Ratushnyak_, Aug 16 2012