151118

C


Self-avoiding walk(3)

3 x n を調べた。
（実行時間は1時間弱ほどかかる。）
なお、オンライン整数列大辞典の
A006192（http://oeis.org/A006192/list）
に詳しく載っている。

#include <stdio.h>

// startがx, y、goalがw - 1, h - 1
long long search(int x, int y, int w, int h, long long used, int depth){
 long long cnt = 0LL;
 if (x < 0 || w <= x || y < 0 || h <= y || (used & (1LL << (x + y * w))) > 0) return 0;
 if (x == w - 1 && y == h - 1) return 1;
 used += 1LL << (x + y * w);
 cnt += search(x + 1, y, w, h, used, depth + 1);
 cnt += search(x - 1, y, w, h, used, depth + 1);
 cnt += search(x, y + 1, w, h, used, depth + 1);
 cnt += search(x, y - 1, w, h, used, depth + 1);
 used -= 1LL << (x + y * w);
 return cnt;
}

int main(void){
 int i;
 long long used;
 for (i = 1; i < 21; i++){
  used = 0LL;
  printf("%lld\n", search(0, 0, 3, i, used, 1));
 }
 return 0;
}

出力結果
1
4
12
38
125
414
1369
4522
14934
49322
162899
538020
1776961
5868904
19383672
64019918
211443425
698350194
2306494009
7617832222