0
$\begingroup$

Given an $n \times n$ modular (ie: the line resp. column after the last one is identified with the first) chessboard, I'd like to count the number of cycle-free $n$-paths a knight can do, starting from any square (ie: the knight will walk only $n$ squares instead of your usual $n^2$).

The solution with the knight graph adjacency matrix won't work here because I don't know $n$ in advance... I'd like to obtain the answer as a formula depending on $n$.

I tried thinking like this: there are $n^2$ squares to put the first knight. Since the board is modular that square threatens exactly other 8, so there are 8 possibilities for the 2nd. Since I want paths, for the third one there are only 7 possible squares, and so on until the last, giving the number $8n^27^{n-1}$ paths.

However I realized this number is merely an upper bound, not only because I'm counting some paths more than once but because that way some paths might also contain cycles...

So... How can I properly count the number of such paths?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.