一意性までとなると全数列挙しかないから、解の一つを
できるだけ速く見つけたいというのであれば
選択枝が小さいものから順次とか随時矛盾チェックとか
いろいろと山の賭けかたにはノウハウはあるのかも知れないが
この問題の場合、列挙の途中で見つかる解を出力する
アルゴリズムだから、結局最終的には運だとしかいいようが
ないような感じ