6.バックトラック


【サザエさん一家】

タラの祖父、祖母を検索するプログラムです。 
今回は複数の解答が考えられるときに全解を出させるための述語を使います。 

サザエさん一家

1つの解、namiheiが見つかり何もなければ終了しますがプログラムでは、namiheiの他にfuneがいることがわかります。そのため、fail述語を使い述語をバックトラックさせています。

failした結果、1つ前の項へバックトラックし別解を探します。

fail述語は必ず失敗させる述語なので全てのparent述語を探し終えたあとは、Prologはnoを返します。

※カットオペレータ 
バックトラックを使って単位節すべての解答を出力をすることはできました。 
しかし、必要のないデータで処理してほしくない場合、プログラムの制御が必要です。
その際に使用するのがカットオペレータ(!)です。
バックトラックした際に、再充足(別解)をしたくない場合には!をつければ 再充足をおこないません。 

例) 
grandParent(Z,X):-  
                 parent(Y,X),parent(Z,Y),!.

最後の項に!をつければ最初の解 namihei のみ出力されます。


【Nqueen】

 4 クイーンの全解を求めます 。

質問を入力します。
queen1

safeが失敗してselectへバックトラックします。
queen2

allqueenで値を入力し、このput述語が成立しなければ、write(Ans)の評価へは進みません。
またput述語(ゴール)の中にselectやsafeといったサブゴールがあり、それぞれ順番に成功しなければ成立しません。
どこかのゴールで失敗した場合、今回のように選択肢の残っている直近のゴールへバックトラックします。
queen3