There might still be issues with multiple solutions... Because when a board has multiple solutions they're all valid Spanning Trees. But there probably is some way around this.

An efficient generator could perhaps even work client side, so I wouldn't have to store premade puzzle instances in the repo. That would be cool =).