[バックトレース]フォールバック検索

トレースバック(検索後)

遡及は、限定された条件を有する問題を解決するための戦略である. 

誰が作ったの?

1950年代にアメリカの数学者D.H.Lemmerによって創造された. 

限定条件がある場合,要素の順序は解決方法とは無関係である.これらの問題は変数セットで構成されています.
限定条件を構成するには、各値の変数に値が必要です.検索を撤退すると、すべての組合せが試行されます.
質問の答えを探す.これはメリットかもしれません.
これは,退却探索を実施する方法が多くの部分の組合せ**を排除しているためである.
最終的に,解の時間が短縮される. 

特長

主な概念は解を得る前にすべての可能性を試みることである. 
すべての可能性は木のように構成され、その中に解決策があります.DFSを使用してツリーをチェックします. 
探索中に誤った答えに出会ったら、以前の分かれ道に戻ります.
他に試したことのない解決策があれば、試してみましょう.
これ以上解決策がなければ、以前の分かれ道に戻ります. 
すべてのツリーのノードに答えが見つからないことを確認した場合、この問題の解決ジャックはありません. 
backtrackingは通常再帰関数で実現される.後退探索はDFSとほぼ同じであるが,占有する記憶領域は少ない.(DFSの微妙な違い) 後続トレースは、現在の状態を保存および変更する間にのみ占有される動作を行います.
ナビゲーション速度を速めるために、 
再帰呼び出しを行う前に、アルゴリズムを適用して、試行する値を決定し、条件を超えた値をクリアできます. または、 この値以外の値を参照できます. 
backtrackingはDFSで答えを望む可能性を判断し,より深い探索を行うかどうかを決定する.
うまくやれば,より効率的なアルゴリズムが出現したと考えられる. 
典型的な遡及問題N-Queens問題を見てみましょう.
まず、優秀なブログを参考にしたほうがいいです. 
[ 問題の概念をうまく説明できるブログ ]
[ 本当にノートのブログをよく理解しました ]

n = int(input())
s = [0 for i in range(16)]
result = 0


def isTrue(x):
    for i in range(1, x):
        if s[x] == s[i] or abs(s[x] - s[i]) == x - i:
            return False
    return True


def dfs(cnt):
    global result
    if cnt > n:
        result += 1
    else:
        for i in range(1, n + 1):
            s[cnt] = i
            if isTrue(cnt):
                dfs(cnt + 1)


dfs(1)
print(result)