Minimum cost of solving the Eni-Puzzle

Question

You're tasked with writing an algorithm to efficiently estimate cost of solving an Eni-Puzzle from a scrambled state as follows:

You're given m lists of containing n elements each(representing the rows of the puzzle). The elements are numbers between 0 and n-1 inclusive (representing the colors of tiles). There are exactly m occurrences of each integers across all m lists (one for each list).

For example:

m=3, n=4 :

[[3, 0, 3, 1],            [[1, 3, 0, 1],
 [1, 0, 2, 2],     or      [0, 2, 3, 1],
 [3, 0, 1, 2]]             [0, 3, 2, 2]]

You can manipulate these lists in two ways:

1: Swapping two elements between circularly adjacent indices in (non circularly) adjacent lists. Cost=1.

Ex:

m=3, n=4 :

Legal:
Swap((0,0)(1,1))
Swap((1,0)(2,3)) (circularly adjacent)

Illegal:
Swap((0,0)(0,1)) (same list)
Swap((0,0)(2,1)) (lists are not adjacent)
Swap((0,0)(1,0)) (indices are not circularly adjacent (they're the same)
Swap((0,0)(1,2)) (indices are not circularly adjacent)

2. Circularly shifting one of the lists (Cost=number of shifts)

Your algorithm must efficiently calculate minimum cost required to manipulate the lists such that the resulting lists are all rotations of each other (meaning the puzzle can be fully solved from this state using only rotation moves) i.e.:

[[0, 1, 2, 3]          [[2, 1, 0, 3]
 [3, 0, 1, 2]    and   [0, 3, 2, 1]
 [1, 2, 3, 0]]         [3, 2, 1, 0]] 

...are both valid final states.

Instead of lists, you may use any data structure(s) of your choice to represent the puzzle, so long as the cost of simulating a valid move (sliding or rotating) on the puzzle with this representation is O(n*m). The setup cost of initializing this data structure can be disregarded.

A winning solution will compute the cost in the lowest asymptotic runtime in terms of m and n. Execution time will be assessed as a tie breaker.