Thanks for all the ideas! I implemented the backtracking idea in the end. This graphic should generate a new random board each time you refresh the page.

The ultimate aim of this is, of course, for part of a puzzle thing I'm toying around with. Puzzle:

Answer:

http://www.chiark.greenend.org.uk/~sgtatham/puzzles/