It's less than or equal to mn. I will show that any move X is not needed more than m times.
Note that any combination of moves is still in the form of a move. We'll replace any sequence of non-X moves with a single move (which may or may not be an original move)
Suppose we have a sequence S = T1 X T2 X ... X T(m+2) involving m+1 iterations of the move X. For each line p, let i_p be the greatest i such that Ti has a fixed output for line p (ie it makes it vertical or horizontal, as opposed to doing nothing or swapping it). By the pigeonhole principle, there is some k < m+2 which is not i_p for any p. I claim then that S' = T1 X T2 X ... T(k-1) Tk T(k+1) X ... X T(m+2) has the same result as S. For any p that has i_p > k, the results is clear since the position of p is set after the modification. Similarly for any p which is set by X. For p that has i_p < k, every transformation after i_p either does nothing or flips it, so they commute. There are the same Ts after, and the number of Xs is equal to the number of Xs - 2, and since X doesn't set it, any even number of Xs has no effect.
Thus any sequence of m+1 Xs can be rewritten as a sequence with fewer Xs. Since X is arbitrary, the longest possible sequence is at most mn. (By the pigeonhole principle)
Edit: A bit of case analysis gets this down to mn-n pretty easily, I only had to use mn because the general case didn't allow the excluded k to be the final one, but this is only an issue if X and T(m+2) don't set any positions, in which case they commute and the last 2 Xs aren't needed either.
Ok, I can do much better, 2n.
Suppose T1 T2 -- Tk is a minimal solve. Reorder the lines so that the final transformation that 'sets' that line does not occur later than the final operation that sets the line to its right. Ie if o means swap, x means nothing, | means make verticle and - means make horizontal, then we would reorder the lines if the minimal solve was (- |) (o -) (o -), since the fist line is fixed only in the first move and the second line is fixed in every move.
We thus have two (possibly empty) groups of lines, the first of which are at some point 'set' during the solve and the second of which are only ever 'swapped'. Note that the states and moves of the second group correspond to a vector space over F_2 so any attainable orientation can be obtained at one move per line.
We will solve the first group at at most 2 moves per line. Starting from the left, solve the line. Use the last move that set this line to set it, and if a rotation is required, select one of the subsequent moves from the final solve. Repeat this for each line going left to right, always using the final 'setting' move from the original solve, and a subsequent rotation if necessary. This guarantees that one will always exist.
After doing this, the position of the second group is again attainable because we used moves from the original solve, and so can be obtained with 1 move per line. Thus we have a solve with at most 2 moves per line =2n.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.