# Knight's Tour Parberry algorithm: 4 knight's tour merge procedure

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.

• Have you tried a few data structures? How about a doubly linked list with pointers to both head and tail, for example? – Yuval Filmus Mar 31 '18 at 20:03
• @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. – False Promise Mar 31 '18 at 20:13