誰かが次のパズルのロジックを持っています

Question

私はn * nの行列を持っています。 各頂点には、関連する次数があります。 Degreeは、隣接する頂点に描画できる線の数です。 私は各頂点の次数を含む配列を生成しています。 たとえば、array {1,2,2,1}は次の2つのソリューションを実装します。私はそれが一つの解決策または複数のソリューションを持っているかどうかを知りたい配列を取得するときに私が欲しいもの

ソリューション1

ソリューション2

は、あります。

これは、{0,3,1,2,4,2,2,1,3}が2つ以上の解決策を持つ別の例です。

Answer 1

私はこれについてどこかで読んでいます。私はそれには2つのアプローチがあると思います：ブルートフォースか洗練されたどちらかです。

ブルートフォース：矛盾が見つかった場合（ノードがアウトに対応していないインラインカウントを取得し、再帰的に各頂点の程度によって許可されている行の任意の組み合わせを試して、バックトラック-度）。

絞り込み：最初のノードから開始する代わりに、最も多くのリンクを持つノードから開始します。これはまた、残りのノードを介して繰り返されるが、残りのノードは、がその程度のままで更新される（例えば、前のノードにすでに線がある場合にはノードの次数が減少する）。これがより速い理由は、大きな程度のノードは、その周囲のノードに対してより高い制限を課すことである。ノードが近隣ノードの残存度を0に減少させる場合、そのノードについて考慮する必要があるケースは0である。