Any other unsolvable conditions? Sure. Generalizing a bit from the N*N square - if the dimensions are M * N, then there must be M * N - 1 moves. Now imagine that the grid is a checkerboard of black and white. If the number of moves is even, then you must end on the same color you started on. If the number of moves is odd, you must end on the opposite color you started on. Otherwise there's no way to solve this. This condition can be formulated as:
(x2 - x1 + y2 - y1 + M*N - 1) % 2 == 0
If you were to choose M, N, x1, x2, y1, y2 all at random, you'd basically get an unsolvable configuration about half the time. A 2*2 grid with points at opposite corners is one example of this.
Note that if either M or N equals 1 while the other is > 2, there's no solution possible unless the points are at opposite ends. Otherwise though - as long as M and N are both >= 2, and the above condition is met, then I believe a solution is always possible.
A detailed algorithm for finding a solution is... ummm... left as an excercise for the student. Yeah, that's it.
[ May 09, 2004: Message edited by: Jim Yingst ]