As a programmer, the thing I hate the most is having to redo code over again due to poor specs or bad design docs. Make sure they are organized and have the correct specifications.
Apparently, this isn't NP-complete. There is an algorithm that can solve this in O(n) time, see here: http://mathworld.wolfram.com/KnightsTour.html
This will save a LOT of time for larger boards. Try to implement this.