ラッシュアワーゲーム パズルの複雑さの上限を理解しようとしています。私は、トラック (長さ 3 グリッド) と車 (長さ 2 グリッド) を含む車両で、9x9ボードを扱っています。22
私の論理では、車がボード上を一方向に移動できるという事実を考える8 timesと9x9、計算は8^22となり、結果は になり7.34e+19ます。7.34e+19これは、このパズルの上限が異なる状態であることを意味します。
反復されたボードの状態の数を考慮して、アルゴリズムがソリューションにどれだけ近いかを計算したいので、私には過剰に思えます。すべての車両がトラックであり、したがって 2 回しか移動できないと仮定しても、7大きすぎるように思えます。
上限は過大評価されていますか? 車両が占有していないスペースは可動スペースの量だけと考えるべきではないでしょうか。