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.

1, 18, 340812, 1553113040

Offset

1,2

Comments

When n<3 there are n^3 cells available, otherwise n^3 - (n-2)^3.

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

Links

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

Prog

(C)
#include <stdio.h>    // GCC -O3
char grid[4][4][4];
long long SIZE;
long long calc_ways(long long x, long long y, long long z) {
    long long n;
    if (grid[x][y][z]) return 0;
    if (x+y+z==SIZE*3-3) return 1;
    grid[x][y][z]=1;
    n=0;
    if (x>0)        n =calc_ways(x-1, y, z);  // go left
    if (x<SIZE-1)   n+=calc_ways(x+1, y, z);  // right
    if (y>0)        n+=calc_ways(x, y-1, z);  // down
    if (y<SIZE-1)   n+=calc_ways(x, y+1, z);  // up
    if (z>0)        n+=calc_ways(x, y, z-1);  // level down
    if (z<SIZE-1)   n+=calc_ways(x, y, z+1);  // level up
    grid[x][y][z]=0;
    return n;
}
int main()
{
  for (SIZE=1; SIZE<=4; ++SIZE) {
    int x, y, z;
    memset(grid, 0, sizeof(grid));
    for (x=1; x<SIZE-1; ++x)
      for (y=1; y<SIZE-1; ++y)
        for (z=1; z<SIZE-1; ++z)
          grid[x][y][z]=1;
    printf("%llu, ", calc_ways(0, 0, 0));
  }
}

Crossrefs

Cf. A007764, A059783.

Sequence in context: A259364 A013762 A078352 * A071098 A259164 A013808

Adjacent sequences: A215574 A215575 A215576 * A215578 A215579 A215580

Keyword

nonn,walk,more

Author

Alex Ratushnyak, Aug 16 2012

Status

approved