Yep, it requires n^2 moves for even boards while odd boards require less moves (no formula found yet). Using a computer, I found, by brute force, that the 5x5 can be solved in 8 moves at most, the problem quickly becomes intractable for 7x7 and above. It looks like this might be NP hard according to another post:
http://stackoverflow.com/questions/27436275/how-can-i-furthe...