1
$\begingroup$

I'm implementing Parberry's algorithm for closed Knight's tour problem.

Brief idea of the algorithm: split the board in $4$ parts, find the tour on them recursively then delete $1$ edge in each part and add $4$ edges that will connect each part with two adjacent parts.

At the end of page 5 (of the pdf viewer) the author estimates the time complexity of his algorithm. Namely, he writes: $T(n) = 4 \cdot T(n / 2) + O(1)$.

As I understood, the time complexity on each level of recursion is $O(1)$.

Parberry says nothing about the data structures he uses.

So, my question is:

How do I represent Knight's tour and how to merge $4$ Knight's tours to reach a $O(1)$ on each level of the recursion?

Thanks.

$\endgroup$
  • $\begingroup$ Have you tried a few data structures? How about a doubly linked list with pointers to both head and tail, for example? $\endgroup$ – Yuval Filmus Mar 31 '18 at 20:03
  • $\begingroup$ @YuvalFilmus I was thinking about writing a class for Knight's tour representation that will store several data structures such as Arrays and Hash Tables, but I think a single doubly linked list will work much better here. Thanks for the suggestion I will try to implement it. $\endgroup$ – False Promise Mar 31 '18 at 20:13

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.