2
$\begingroup$

According to the following page (http://magictour.free.fr/enum), 17269264 open knight's tours are possible in a 3×16 chessboard.

I compute the number by using the following code(C) and the number is 17273760.

Is my result wrong?

#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;
}

Output (It takes about 36 hours.)

0
0
0
16
0
0
104
792
1120
6096
21344
114496
257728
1292544
3677568
17273760
$\endgroup$
  • 1
    $\begingroup$ Curiously oeis.org/A118067 and mathworld.wolfram.com/KnightGraph.html do not go further than $3 \times 13$ $\endgroup$ – Henry Sep 8 '15 at 13:08
  • $\begingroup$ At hindsight, I don't see a problem with the symmetries you are using or with your brute force search. It is easy to modify the program to list every solution without much overhead, and verifying that all of them are different and valid should be really easy. Later, I will leave my PC working overnight and see what happens. $\endgroup$ – chubakueno Sep 8 '15 at 14:00
  • $\begingroup$ Before they close the question(altough I don't agree), I'd like to keep contact to investigate further. You may write me to chubakueno@gmail.com :) . $\endgroup$ – chubakueno Sep 8 '15 at 15:13
  • $\begingroup$ @chubakueno: I sent you the message. $\endgroup$ – Manyama Sep 8 '15 at 15:44