Need some logic advice

Question

This is not specifically about VB Net except that is what I am using to create the program. Trying to make a "Numbrix" puzzle. If you aren't familiar with Numbrix, it's a 9x9 grid of numbers where the requirement is simple, you must be able to go from 1 to 81 by only going Up, Down, Left or Right. I want to auto-generate them but using a random placement leads to failure every time. I wind up with something like this:

Any suggestions on how to avoid trapping one's self would be appreciated.