# How many open knight's tours are possible in a 3×16 chessboard? [closed]

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

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

• Curiously oeis.org/A118067 and mathworld.wolfram.com/KnightGraph.html do not go further than $3 \times 13$ Sep 8, 2015 at 13:08
• 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. Sep 8, 2015 at 14:00
• Before they close the question(altough I don't agree), I'd like to keep contact to investigate further. You may write me to [email protected] :) . Sep 8, 2015 at 15:13
• @chubakueno: I sent you the message.
– TOM
Sep 8, 2015 at 15:44