Is there a good reason for limiting the size of the board? If you can make the board any size and efficient then you are in a better position of getting a good time.
I suppose the main reason I'm asking has more to do with the search space for finding the optimal solution (shortest path). If the board is very large, then the search space becomes very large and this could affect how you approach solving this.