2018-矢印-解説
- 考案国:ハンガリー
- 正解
- 説明
- 条件を満たす解を見つけるため、ある矢印から始めて、仮に白か黒に決め、その矢印が指している矢印の色を条件を満たすように仮に決める(複数の可能性がある場合は、そのうちの一つを選び)ということを繰り返し、うまく選べなくなったら複数の可能性から選択した矢印まで戻り、まだ試してない可能性を選択するという方法があります。戻ったとき、もう選ぶ選択肢がない場合は、さらに戻ります。
- このように、ある状況から可能性を探索し、ステップバイステップで進み、行き詰まるともとに戻る方法を、情報科学ではバックトラックと言います。 バックトラックは、8クイーンパズルや数独などのパズルを解くのに、また,ナップザック問題などの組み合わせ最適化問題を解決するのにも使用できます。他にも、様々な応用があります。
https://ja.wikipedia.org/wiki/バックトラッキング
https://ja.wikipedia.org/wiki/論理プログラミング