m×n board におけるナイト・ツアーの数えあげを高速に行うには？

以前の質問（n×n board におけるナイト・ツアーの数えあげについて）
でナイトツアーの数えあげを行いました。

さて、一般に
m×n board におけるナイト・ツアーの数えあげを高速に行うには
どうすればよろしいでしょうか？

以下のコードは、長方形の対称性を利用することで以前の計算の約1/4位になっています。

#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_tours(int w, int h){
  int x;
  int y;
  long long used;
  int total = 0;
  for (y = 0; y < h / 2; y++){
    for (x = 0; x < w / 2; x++){
      used = 0LL;
      total += search(x, y, w, h, used, 1) * 4;
    }
    if (w % 2 == 1){
      x = w / 2;
      used = 0LL;
      total += search(x, y, w, h, used, 1) * 2;
    }
  }
  if (h % 2 == 1){
    y = h / 2;
    for (x = 0; x < w / 2; x++){
      used = 0LL;
      total += search(x, y, w, h, used, 1) * 2;
    }
    if (w % 2 == 1){
      x = w / 2;
      used = 0LL;
      total += search(x, y, w, h, used, 1) * 1;
    }   
  }
  return total;
}

int main(void){
  int w;
  int h;
  printf("%d\n", directed_open_tours(4, 5));
  printf("%d\n", directed_open_tours(5, 4));
  printf("%d\n", directed_open_tours(4, 6));
  printf("%d\n", directed_open_tours(6, 4));
  printf("%d\n", directed_open_tours(4, 7));
  printf("%d\n", directed_open_tours(7, 4));
  return 0;
}

実行結果
164
164
1488
1488
12756
12756