# sum of like indices in circular lists

Consider the following problem:

Let a $k$-wheel be defined as an indexed circularly linked list of $k$ integers. For example…

{3, 4, 9, -1, 6}

…is a 5-wheel with 3 at position 0, 4 at position 1, and so on. A wheel supports the operation of rotation, so that a one-step rotation would turn the above wheel into…

{6, 3, 4, 9, -1}

…now with 6 at position 0, 3 at position 1, and so on. Let $W_{N_k}$ be an ordered set of $N$ distinct $k$-wheels. Given some $W_{N_k}$ and some integer $t$, find a series of rotations such that…

$$\forall\ 0 \leq i < k, \sum_{N \in W} N_i = t$$

In other words, if you laid out the wheels as a matrix, the sum of every column would be $t$. Assume that $W_{N_k}$ is constructed so that the solution is unique up to rotations of every element (i.e., there are exactly $k$ unique solutions that consist of taking one solution, then rotating every wheel in $W$ by the same number of steps).

The trivial solution to this problem involves simply checking every possible rotation. Here is some pseudocode for that:

function solve(wheels, index)
if wheels are solved:
return true
if index >= wheels.num_wheels:
return false
for each position 1..k:
if solve(index + 1) is true:
return true
else:
rotate wheels[index] by 1

solve(wheels, 0)


This is a pretty slow solution (something like $O(k^n)$). I'm wondering if it is possible to do this problem faster, and also if there is a name for it.

• I suspect this might be NP-complete, since it doesn't look like we can really tell if a partial solution is going to lead to a correct solution until we set the final wheel... I don't have a proof yet though. I'll add an answer if I think of one. – Matt Lewis Jan 9 '13 at 16:51