なんか難しくてよくわからないけど、
背理法＋バックトラッキングでも、十分高速だと重。

^１．後から開いた数字とその周囲を優先、
^　　(未確定マスー実質値)の絶対値の小さいもの優先で、数字を一個選択
^２．その周囲に★を仮に置いてみる。同時に☆が仮に決定
^３．それを再帰的に繰り返す
＾　　↓
^　　ａ．矛盾(＝２で★や☆の数が超過で置けない)したら
^　　　　一つ前に戻って別の場所に置く
^　　　　↓
^　　　　全部の場所、ケースで矛盾すれば、はじめに置いた★が☆に決定
^　　　　それを開いて１へ
^　　　　そうでなければ、１で別の数字を選択
^４．全部の数字で矛盾が発見できなければ、解は不定。失敗
^　　未確定マスがゼロなら、解有り。成功

効率は１のところの選択アルゴリズムの性能次第だけど、
判定に時間かかるなら、その問題は捨ればいいし