150908

C


Number of knight's tours on a 3×k chessboard(1)

一日半かけて計算した。

#include <stdio.h>

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

int directed_open_tours3(int h){
  if (h < 3) return 0;
  int y;
  long long used;
  int total = 0;
  for (y = 0; y < h / 2; y++){
    used = 0LL;
    total += search(0, y, 3, h, used, 1) * 4;
    used = 0LL;
    total += search(1, y, 3, h, used, 1) * 2;
  }
  if (h % 2 == 1){
    y = h / 2;
    used = 0LL;
    total += search(0, y, 3, h, used, 1) * 2;
    used = 0LL;
    total += search(1, y, 3, h, used, 1) * 1;
  }
  return total;
}

int main(void){
  int h;
  for (h = 1; h < 17; h++){
    printf("%d\n", directed_open_tours3(h));
  }
  return 0;
}

出力結果

0

0

0

16

0

0

104

792

1120

6096

21344

114496

257728

1292544

3677568

17273760