この問題に対するブルートフォースソリューションを最適化するにはどうすればよいですか？
私は以下に説明する問題の解決に取り組んでいます。私は力ずくで使用していますが、解決策が法外なものになっているので、（可能であれば）さらに最適化する必要があります。もちろん、（ブルートフォースではなく）問題を解決するためのより良い方法があれば、さらに良いでしょう。
ソリューションを改善するためにできること、または調べることができる参照（同様の問題など）はありますか？
問題
長方形のボードから始めます。各セルはN状態にすることができ、各セルの初期状態は各セルでランダム（0 <=状態<N）です。また、ボードの内側に収まるさまざまな形状もあります。すべての形状は連続しています。
各形状は、ボードに1回（そして1回だけ）配置する必要があります。図形が配置されると、その図形に属する各セルの値が1ずつ増加します。いずれかのセルのボード値がNに達すると、0に変更されます。
目標は、最終的なボードに値0のすべてのセルが含まれるように、各形状を配置する必要がある位置を見つけることです。常に少なくとも1つの解決策があります。完成したボードから始めて、ランダムな位置にランダムな形状を適用することによって問題が発生したとしましょう。
ボードのサイズ、状態の数N、形状の数はゲームのセットアップであり、「レベル」ごとに（さまざまな速度で）増加し続けます。
私が現在していること
力ずくで問題を一定の大きさまで解決することができます。いくつかの最適化を行っています。解決策が法外なところまで来たので、ロジックを改善したいと思います。
私が最初に行っているのは、形状を大きいものから小さいものへと並べ替えることです。小さい方が内部反復で移動します。仮定（私は証明していませんが、より高速であることがテストされています）は、解を生成する可能性が高いため、小さい形状をより多く移動する方がよいということです。
次に、繰り返される形状の場合、同じ結果が得られるため、すべての順列をチェックすることは避けます。また、同じ形状のペアがオーバーラップしている場合は、1セットの位置のみをチェックします（すべてのオーバーラップで同じ結果が得られるため）。
私が大いに役立つと思う最後の最適化の1つですが、私はまだ実装しています。シーケンス内の各形状で、移動する必要のある形状のセルの合計を数えます。この数から、完成したボードを取得するために必要なセルフリップの合計を差し引いたものは、Nの倍数である必要があります。そうでない場合、残りのシェイプの位置をブルートフォースで強制することはできません。外部ループでシェイプを再配置する必要があります。
追加の詳細
これを最適化する方法に関する他のヒントに興味があります。既知のアルゴリズム、この一連の問題の適切な命名でさえ、私がより多くの研究に使用できるのは素晴らしいことです。
回答
整数線形計画法
あなたの問題は次のように定式化することができます：私たちはベクトルを与えられます $v_{i,j} \in (\mathbb{Z}/N\mathbb{Z})^d$、ボードが持っているところ $d$ セル、そして目標は、ベクトルが与えられることです $c \in (\mathbb{Z}/N\mathbb{Z})^d$、関数を見つける $f$ そのため $\sum_i v_{i,f(j)}=c$。この問題は、整数線形計画法によって解決できます。これはに関連しています$d$-次元のサブセット和問題。多次元のサブセット和の他のアルゴリズムを見つけて、それらを試すこともできるかもしれません。
そのようにどのように定式化するのですか？グリッドに$d$ セル、私たちは形をとして考えることができます $d$-0と1のベクトル。セル内の1は形状で覆われています。各形状は、さまざまな位置に配置して、さまざまなベクトルを生成できます。$v_{i,j}$ に対応します $j$形のある場所 $i$ 配置することができます。 $c$ 元々グリッドにあった数に対応します（まあ、それらの数の否定、モジュロ $N$）。すべての算術演算はモジュロで行われます$N$。
やや賢いブルートフォース
あるいは、メモリを時間と交換することで、ブルートフォースを少し改善する方法があります。あなたが持っているとしましょう$k$形。最初に配置するすべての方法を列挙することから始めます$k/2$すべてゼロの空のボードにシェイプし、結果のすべての位置をハッシュテーブルまたはソートされたリストに格納します。次に、最後に配置するすべての方法を列挙します$k/2$開始位置にシェイプし、ハッシュテーブルまたはソートされたリストで結果の各位置を検索します。一致するものが見つかった場合は、それで解決策が得られます。これにより、メモリの量に制限がない場合、ブルートフォースをもう少し（場合によっては約2倍の形状に）プッシュできます。これを最大限に最適化することには多くの詳細が含まれますが、ブルートフォースがあなたを近づけても少し足りない場合に検討できるアイデアです。それはまだ指数時間アルゴリズムであるため、制限に達します。