ブロックパズルを解くためのアルゴリズムを作りたいのですが、できるだけ効率的です。私はすでに簡単な方法(後戻り)をしました。
私はすべてをマトリックスとして表現しました. ピースが収まる必要がある大きなマトリックスは最初はすべて0で、ピースはスペースがいっぱいの場合は1、スペースが空の場合は0のマトリックスです. 次に考えられるより効率的なアイデアは、次の行に進む前に行が完了しているかどうかを常に確認することです。私が言いたいのは、
(十字架)として表現されたピースがあるかもしれないということです。クロスが隅に置かれている場合、プログラムは無効なソリューションに対してバックトラック全体を無用に実行するため、戻って別のピースを試す必要があります。
0 1 0
1 1 1
0 1 0
必要に応じてコードの一部を提供できますが、先ほど述べたように、単純で非効率的なバックトラッキングのみを行いました。
誰かがより良いアイデアを持っていますか? この場合、動的計画法を使用できますか?