皆さんはチェスをしたことがありますか。 もしそうなら、クイーンが最も重要な駒であり、縦、横、斜めに何マスでも移動できることをすでにご存知でしょう。 今日は、どのクイーンも他のクイーンがいるマスに移動できないように、チェスボード上に8つのクイーンを配置する方法だけを学びます。 チェスの専門用語で、「クイーン同士が攻撃しあえないようにする」という意味です。 どうすればいいのか？
バックトラック アルゴリズムは、いくつかの制約を尊重しなければならない問題に対する解決策を見つけます。 正しい解を見つけるまで、可能なすべての解をテストします。 例として、4つのクイーンと小さなボードで試してみましょう。
The second step is to place the second queen in a safe position, and then the third one:
At this point, there is no safe square on which we can place the last queen. So, we will change the position of the previous one. This is backtracking!
As you can see, there is no other square to safely place the third queen, different than the one we tried. Hence, this will require multiple backtracks. We will have to go back again and change the position of the second queen we placed.
We will have to perform multiple backtracks again to place all queens correctly and finally obtain a solution:
If you want to learn more how multiple backtracking steps inevitably lead you to a solution, check out Computer Science Distilled.
バックトラックの仕組みがわかったところで、フルサイズの 8 クイーン問題を解いてみましょう。
バックトラックの仕組みがわかったところで、フルサイズの 8 クイーン問題を解いてみましょう。 まず、左上のマスをクリックして、最初のクイーンを配置します。
現在のクイーン
次に、別のクイーンを、互いが攻撃できないような位置に配置することができます。 最初の女王はa8に、2番目の女王はたとえばc7に置くことができます。 チェスボードに安全なマスがなくなるまで、クイーンを配置し続けます。 その時点で、”undo “をクリックして、後戻りすることができます。 これで、最後に置いたQueenが消去され、他のマスを選んで置くことができるようになります。
インタラクティブなゲームをプレイすることで、バックトラックの感覚をつかみ始めることができます。
インタラクティブなゲームをプレイすることで、バックトラックの感覚がつかめてきます。 そこで、プログラミングが役に立ちます!
擬似コード:
- 最初のクイーンをチェス盤の左上のマスに配置することから開始します。 そうでなければ、別のクイーンを安全な位置に置くことは可能か。
- 可能であれば、これを解決策の一部としてマークし、ポイント 2 に戻る。
- 不可能であれば、前のクイーンの位置を変更し（バックトラック）、ポイント 2 に戻る。