Glad to hear that you're enjoying the game! I've added the 8x8 board. In the average case, it can be solved in around 32 moves using the most optimal algorithm.
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...