n個の移動可能なすべてのナイトポジション - プロローグ内の無限ループ

Question

nの可能なすべてのナイトポジションの計算ソリューションが正確なパスを知っているときに、Prologのバックトラッキングに問題があります。

私の解決策は、最初の結果の一部を印刷し、不可能な結果を​​探している間は終了しません。

これは私のコードです：

move([X, Y], [A, B]) :- X + 1 < 8, Y + 2 < 8, A is X + 1, B is Y + 2. 
move([X, Y], [A, B]) :- X + 2 < 8, Y + 1 < 8, A is X + 2, B is Y + 1. 
move([X, Y], [A, B]) :- X + 2 < 8, Y - 1 >= 0, A is X + 2, B is Y - 1. 
move([X, Y], [A, B]) :- X + 1 < 8, Y - 2 >= 0, A is X + 1, B is Y - 2. 
move([X, Y], [A, B]) :- X - 1 >= 0, Y - 2 >= 0, A is X - 1, B is Y - 2. 
move([X, Y], [A, B]) :- X - 2 >= 0, Y - 1 >= 0, A is X - 2, B is Y - 1. 
move([X, Y], [A, B]) :- X - 2 >= 0, Y + 1 < 8, A is X - 2, B is Y + 1. 
move([X, Y], [A, B]) :- X - 1 >= 0, Y + 2 < 8, A is X - 1, B is Y + 2. 

knight_move(X,Y,[X,Y],1) :- move(X,Y). 
knight_move(X,Y,[X|P],C) :- move(X,Z), knight_move(Z,Y,P,Cn), C is Cn+1. 

predict_moves(X,C,P) :- knight_move(X,_,P,C). 

サンプルコール：

predict_moves([1,1],3,P). 

結果で私は、n 3が移動中のすべての可能なパスを期待しています。私のコードに条件を追加してコードを停止させ、無限に移動したりループしたりするのを助けることができますか？

Answer 1

問題：あなたが書く：プロローグはこのブランチを取っておくことができるように

knight_move(X,Y,[X|P],C) :- move(X,Z), knight_move(Z,Y,P,Cn), C is Cn+1. 

は、何カットもこのブランチを取ってからあなたを防止する任意の他のメカニズムはありません。さらにをのカウンターCn is C-1に減らし、の前に、の再帰呼び出しを行う必要があります。

まず第一に、私はそれではなく、これらすべての境界チェックを書くの検証述語のいくつかの並べ替えを構築する方がよいと思う：

valid_position(X,Y) :- 
    X >= 0, 
    Y >= 0, 
    X < 8, 
    Y < 8. 

我々はまた、plusneg/3なposneg(X,DX,Y)ため、Yという述語を構築することができますX+DXとX-DX両方です：

posneg(X,DX,Y) :- 
    Y is X+DX. 
posneg(X,DX,Y) :- 
    Y is X-DX. 

その後、我々は騎士の「可能な動き」を記述することができます：

possible(X, Y, A, B) :- 
    posneg(X,2,A), 
    posneg(Y,1,B). 
possible(X, Y, A, B) :- 
    posneg(X,1,A), 
    posneg(Y,2,B). 

ただし、新しい座標が有効かどうかを確認する必要があるため、これらは「有効な移動」ではありません。だから私たちは書くことができます。

move([X,Y], [A,B]) :- 
    possible(X,Y,A,B), 
    valid_position(A,B). 

を、これは、いくつかのadditiona述語を導入し、そしておそらくリッテあまり効率的ではあるが、すべての動きが有効なものであることが明らかです。、

はケースでカウントが1以上である

knight_move(P1,P1,[P1],C) :- 
    C < 1. 

：

は今カウンターでknigt_move/4のために、我々は、カウンタがゼロを下回った場合には、これ以上の移動が行われているという句を書くことができます騎士はまだ移動を行うことができますので、我々はとしてそれを書くことができます。

knight_move(P1,PZ,[P1|PT],C) :- 
    C >= 1, 
    C1 is C-1, 
    move(P1,P2), 
    knight_move(P2,PZ,PT,C1). 

またはすべて一緒にこれを置く：

valid_position(X,Y) :- 
    X >= 0, 
    Y >= 0, 
    X < 8, 
    Y < 8. 

posneg(X,DX,Y) :- 
    Y is X+DX. 
posneg(X,DX,Y) :- 
    Y is X-DX. 

possible(X, Y, A, B) :- 
    posneg(X,2,A), 
    posneg(Y,1,B). 
possible(X, Y, A, B) :- 
    posneg(X,1,A), 
    posneg(Y,2,B). 

move([X,Y], [A,B]) :- 
    possible(X,Y,A,B), 
    valid_position(A,B). 

knight_move(P1,P1,[P1],C) :- 
    C < 1. 
knight_move(P1,PZ,[P1|PT],C) :- 
    C >= 1, 
    C1 is C-1, 
    move(P1,P2), 
    knight_move(P2,PZ,PT,C1). 

我々はちょうど二つの移動（および方法）に達するものをフィールド尋ねれば、私達は得た：

?- knight_move([1,1],End,Path,2). 
End = [5, 3], 
Path = [[1, 1], [3, 2], [5, 3]] ; 
End = [5, 1], 
Path = [[1, 1], [3, 2], [5, 1]] ; 
End = [1, 3], 
Path = [[1, 1], [3, 2], [1, 3]] ; 
End = [1, 1], 
Path = [[1, 1], [3, 2], [1, 1]] ; 
End = [4, 4], 
Path = [[1, 1], [3, 2], [4, 4]] ; 
End = [4, 0], 
Path = [[1, 1], [3, 2], [4, 0]] ; 
End = [2, 4], 
Path = [[1, 1], [3, 2], [2, 4]] ; 
End = [2, 0], 
Path = [[1, 1], [3, 2], [2, 0]] ; 
End = [5, 1], 
Path = [[1, 1], [3, 0], [5, 1]] ; 
End = [1, 1], 
Path = [[1, 1], [3, 0], [1, 1]] ; 
End = [4, 2], 
Path = [[1, 1], [3, 0], [4, 2]] ; 
End = [2, 2], 
Path = [[1, 1], [3, 0], [2, 2]] ; 
End = [4, 4], 
Path = [[1, 1], [2, 3], [4, 4]] ; 
End = [4, 2], 
Path = [[1, 1], [2, 3], [4, 2]] ; 
End = [0, 4], 
Path = [[1, 1], [2, 3], [0, 4]] ; 
End = [0, 2], 
Path = [[1, 1], [2, 3], [0, 2]] ; 
End = [3, 5], 
Path = [[1, 1], [2, 3], [3, 5]] ; 
End = [3, 1], 
Path = [[1, 1], [2, 3], [3, 1]] ; 
End = [1, 5], 
Path = [[1, 1], [2, 3], [1, 5]] ; 
End = [1, 1], 
Path = [[1, 1], [2, 3], [1, 1]] ; 
End = [2, 4], 
Path = [[1, 1], [0, 3], [2, 4]] ; 
End = [2, 2], 
Path = [[1, 1], [0, 3], [2, 2]] ; 
End = [1, 5], 
Path = [[1, 1], [0, 3], [1, 5]] ; 
End = [1, 1], 
Path = [[1, 1], [0, 3], [1, 1]] ; 
false. 

をだから我々はちょうど二つの動きで24本のパスを作ることができます。重複があることに注意してください。setof/3を使用すると、2つの動きで15個の四角に到達できると判断できます。 3つの移動のために30個の正方形到達するための148回のパスがあります。

?- findall(End,knight_move([1,1],End,_,2),Ends), length(Ends,N). 
Ends = [[5, 3], [5, 1], [1, 3], [1, 1], [4, 4], [4, 0], [2, 4], [2|...], [...|...]|...], 
N = 24. 

?- setof(End,Pa^knight_move([1,1],End,Pa,2),Ends), length(Ends,N). 
Ends = [[0, 2], [0, 4], [1, 1], [1, 3], [1, 5], [2, 0], [2, 2], [2|...], [...|...]|...], 
N = 15. 

?- findall(End,knight_move([1,1],End,_,3),Ends), length(Ends,N). 
Ends = [[7, 4], [7, 2], [3, 4], [3, 2], [6, 5], [6, 1], [4, 5], [4|...], [...|...]|...], 
N = 148. 

?- setof(End,Pa^knight_move([1,1],End,Pa,3),Ends), length(Ends,N). 
Ends = [[0, 1], [0, 3], [0, 5], [0, 7], [1, 0], [1, 2], [1, 4], [1|...], [...|...]|...], 
N = 30. 

Answer 2

あなたは整数上の理由のためにCLP（FD）を使用して、あなたが再帰的に前にカウンターを制約するように、その意志をご制約の順序を変更した場合あなたのループの問題を排除：

になり

move([X, Y], [A, B]) :- X + 1 #< 8, Y + 2 #< 8, A #= X + 1, B #= Y + 2. 
move([X, Y], [A, B]) :- X + 2 #< 8, Y + 1 #< 8, A #= X + 2, B #= Y + 1. 
move([X, Y], [A, B]) :- X + 2 #< 8, Y - 1 #>= 0, A #= X + 2, B #= Y - 1. 
move([X, Y], [A, B]) :- X + 1 #< 8, Y - 2 #>= 0, A #= X + 1, B #= Y - 2. 
move([X, Y], [A, B]) :- X - 1 #>= 0, Y - 2 #>= 0, A #= X - 1, B #= Y - 2. 
move([X, Y], [A, B]) :- X - 2 #>= 0, Y - 1 #>= 0, A #= X - 2, B #= Y - 1. 
move([X, Y], [A, B]) :- X - 2 #>= 0, Y + 1 #< 8, A #= X - 2, B #= Y + 1. 
move([X, Y], [A, B]) :- X - 1 #>= 0, Y + 2 #< 8, A #= X - 1, B #= Y + 2. 


knight_move(X,Y,[X,Y], 1) :- move(X,Y). 

# NOTE the constraint of C#= Cn + 1 before the recursive call 
knight_move(X,Y,[X|P], C) :- C#> 1, move(X,Z), C#= Cn + 1, knight_move(Z,Y,P,Cn). 

predict_moves(X,C,P) :- knight_move(X,_,P,C). 

：実際に問題を削除する前に

| ?- predict_moves([1,1], 3, P). 

P = [[1,1],[2,3],[3,5],[4,7]] ? a 

P = [[1,1],[2,3],[3,5],[5,6]] 

P = [[1,1],[2,3],[3,5],[5,4]] 

P = [[1,1],[2,3],[3,5],[4,3]] 

P = [[1,1],[2,3],[3,5],[2,3]] 

P = [[1,1],[2,3],[3,5],[1,4]] 

P = [[1,1],[2,3],[3,5],[1,6]] 

P = [[1,1],[2,3],[3,5],[2,7]] 

P = [[1,1],[2,3],[4,4],[5,6]] 

P = [[1,1],[2,3],[4,4],[6,5]] 

P = [[1,1],[2,3],[4,4],[6,3]] 

P = [[1,1],[2,3],[4,4],[5,2]] 

P = [[1,1],[2,3],[4,4],[3,2]] 

P = [[1,1],[2,3],[4,4],[2,3]] 

P = [[1,1],[2,3],[4,4],[2,5]] 

P = [[1,1],[2,3],[4,4],[3,6]] 

P = [[1,1],[2,3],[4,2],[5,4]] 

P = [[1,1],[2,3],[4,2],[6,3]] 

P = [[1,1],[2,3],[4,2],[6,1]] 

P = [[1,1],[2,3],[4,2],[5,0]] 

P = [[1,1],[2,3],[4,2],[3,0]] 

P = [[1,1],[2,3],[4,2],[2,1]] 

P = [[1,1],[2,3],[4,2],[2,3]] 

P = [[1,1],[2,3],[4,2],[3,4]] 

P = [[1,1],[2,3],[3,1],[4,3]] 

P = [[1,1],[2,3],[3,1],[5,2]] 

P = [[1,1],[2,3],[3,1],[5,0]] 

P = [[1,1],[2,3],[3,1],[1,0]] 

P = [[1,1],[2,3],[3,1],[1,2]] 

P = [[1,1],[2,3],[3,1],[2,3]] 

P = [[1,1],[2,3],[1,1],[2,3]] 

P = [[1,1],[2,3],[1,1],[3,2]] 

P = [[1,1],[2,3],[1,1],[3,0]] 

P = [[1,1],[2,3],[1,1],[0,3]] 

P = [[1,1],[2,3],[0,2],[1,4]] 

P = [[1,1],[2,3],[0,2],[2,3]] 

P = [[1,1],[2,3],[0,2],[2,1]] 

P = [[1,1],[2,3],[0,2],[1,0]] 

P = [[1,1],[2,3],[0,4],[1,6]] 

P = [[1,1],[2,3],[0,4],[2,5]] 

P = [[1,1],[2,3],[0,4],[2,3]] 

P = [[1,1],[2,3],[0,4],[1,2]] 

P = [[1,1],[2,3],[1,5],[2,7]] 

P = [[1,1],[2,3],[1,5],[3,6]] 

P = [[1,1],[2,3],[1,5],[3,4]] 

P = [[1,1],[2,3],[1,5],[2,3]] 

P = [[1,1],[2,3],[1,5],[0,3]] 

P = [[1,1],[2,3],[1,5],[0,7]] 

P = [[1,1],[3,2],[4,4],[5,6]] 

P = [[1,1],[3,2],[4,4],[6,5]] 

P = [[1,1],[3,2],[4,4],[6,3]] 

P = [[1,1],[3,2],[4,4],[5,2]] 

P = [[1,1],[3,2],[4,4],[3,2]] 

P = [[1,1],[3,2],[4,4],[2,3]] 

P = [[1,1],[3,2],[4,4],[2,5]] 

P = [[1,1],[3,2],[4,4],[3,6]] 

P = [[1,1],[3,2],[5,3],[6,5]] 

P = [[1,1],[3,2],[5,3],[7,4]] 

P = [[1,1],[3,2],[5,3],[7,2]] 

P = [[1,1],[3,2],[5,3],[6,1]] 

P = [[1,1],[3,2],[5,3],[4,1]] 

P = [[1,1],[3,2],[5,3],[3,2]] 

P = [[1,1],[3,2],[5,3],[3,4]] 

P = [[1,1],[3,2],[5,3],[4,5]] 

P = [[1,1],[3,2],[5,1],[6,3]] 

P = [[1,1],[3,2],[5,1],[7,2]] 

P = [[1,1],[3,2],[5,1],[7,0]] 

P = [[1,1],[3,2],[5,1],[3,0]] 

P = [[1,1],[3,2],[5,1],[3,2]] 

P = [[1,1],[3,2],[5,1],[4,3]] 

P = [[1,1],[3,2],[4,0],[5,2]] 

P = [[1,1],[3,2],[4,0],[6,1]] 

P = [[1,1],[3,2],[4,0],[2,1]] 

P = [[1,1],[3,2],[4,0],[3,2]] 

P = [[1,1],[3,2],[2,0],[3,2]] 

P = [[1,1],[3,2],[2,0],[4,1]] 

P = [[1,1],[3,2],[2,0],[0,1]] 

P = [[1,1],[3,2],[2,0],[1,2]] 

P = [[1,1],[3,2],[1,1],[2,3]] 

P = [[1,1],[3,2],[1,1],[3,2]] 

P = [[1,1],[3,2],[1,1],[3,0]] 

P = [[1,1],[3,2],[1,1],[0,3]] 

P = [[1,1],[3,2],[1,3],[2,5]] 

P = [[1,1],[3,2],[1,3],[3,4]] 

P = [[1,1],[3,2],[1,3],[3,2]] 

P = [[1,1],[3,2],[1,3],[2,1]] 

P = [[1,1],[3,2],[1,3],[0,1]] 

P = [[1,1],[3,2],[1,3],[0,5]] 

P = [[1,1],[3,2],[2,4],[3,6]] 

P = [[1,1],[3,2],[2,4],[4,5]] 

P = [[1,1],[3,2],[2,4],[4,3]] 

P = [[1,1],[3,2],[2,4],[3,2]] 

P = [[1,1],[3,2],[2,4],[1,2]] 

P = [[1,1],[3,2],[2,4],[0,3]] 

P = [[1,1],[3,2],[2,4],[0,5]] 

P = [[1,1],[3,2],[2,4],[1,6]] 

P = [[1,1],[3,0],[4,2],[5,4]] 

P = [[1,1],[3,0],[4,2],[6,3]] 

P = [[1,1],[3,0],[4,2],[6,1]] 

P = [[1,1],[3,0],[4,2],[5,0]] 

P = [[1,1],[3,0],[4,2],[3,0]] 

P = [[1,1],[3,0],[4,2],[2,1]] 

P = [[1,1],[3,0],[4,2],[2,3]] 

P = [[1,1],[3,0],[4,2],[3,4]] 

P = [[1,1],[3,0],[5,1],[6,3]] 

P = [[1,1],[3,0],[5,1],[7,2]] 

P = [[1,1],[3,0],[5,1],[7,0]] 

P = [[1,1],[3,0],[5,1],[3,0]] 

P = [[1,1],[3,0],[5,1],[3,2]] 

P = [[1,1],[3,0],[5,1],[4,3]] 

P = [[1,1],[3,0],[1,1],[2,3]] 

P = [[1,1],[3,0],[1,1],[3,2]] 

P = [[1,1],[3,0],[1,1],[3,0]] 

P = [[1,1],[3,0],[1,1],[0,3]] 

P = [[1,1],[3,0],[2,2],[3,4]] 

P = [[1,1],[3,0],[2,2],[4,3]] 

P = [[1,1],[3,0],[2,2],[4,1]] 

P = [[1,1],[3,0],[2,2],[3,0]] 

P = [[1,1],[3,0],[2,2],[1,0]] 

P = [[1,1],[3,0],[2,2],[0,1]] 

P = [[1,1],[3,0],[2,2],[0,3]] 

P = [[1,1],[3,0],[2,2],[1,4]] 

P = [[1,1],[0,3],[1,5],[2,7]] 

P = [[1,1],[0,3],[1,5],[3,6]] 

P = [[1,1],[0,3],[1,5],[3,4]] 

P = [[1,1],[0,3],[1,5],[2,3]] 

P = [[1,1],[0,3],[1,5],[0,3]] 

P = [[1,1],[0,3],[1,5],[0,7]] 

P = [[1,1],[0,3],[2,4],[3,6]] 

P = [[1,1],[0,3],[2,4],[4,5]] 

P = [[1,1],[0,3],[2,4],[4,3]] 

P = [[1,1],[0,3],[2,4],[3,2]] 

P = [[1,1],[0,3],[2,4],[1,2]] 

P = [[1,1],[0,3],[2,4],[0,3]] 

P = [[1,1],[0,3],[2,4],[0,5]] 

P = [[1,1],[0,3],[2,4],[1,6]] 

P = [[1,1],[0,3],[2,2],[3,4]] 

P = [[1,1],[0,3],[2,2],[4,3]] 

P = [[1,1],[0,3],[2,2],[4,1]] 

P = [[1,1],[0,3],[2,2],[3,0]] 

P = [[1,1],[0,3],[2,2],[1,0]] 

P = [[1,1],[0,3],[2,2],[0,1]] 

P = [[1,1],[0,3],[2,2],[0,3]] 

P = [[1,1],[0,3],[2,2],[1,4]] 

P = [[1,1],[0,3],[1,1],[2,3]] 

P = [[1,1],[0,3],[1,1],[3,2]] 

P = [[1,1],[0,3],[1,1],[3,0]] 

P = [[1,1],[0,3],[1,1],[0,3]] 

(3 ms) no 
| ?- 

Answer 3

、のは、非終了の原因を絞り込むましょう。あなたのケースでは、それは特にトリッキーです、あなたは良いと正しい答えを得るためです。それだけで問題があります。問題を絞り込む最も簡単な方法は、falseゴールをプログラムに追加することです。結果として生じるプログラムがまだループしている場合、私たちはさらにそのような目標を追加することができます。今通じstrikedされているすべての部品がすべて終了へ影響を持っていない

 
move([X, Y], [A, B]) :- X+1 < 8, Y+2 < 8, A is X+1, B is Y+2. 
move([X, Y], [A, B]) :- false, X+2 < 8, Y+1 < 8, A is X+2, B is Y+1. 
move([X, Y], [A, B]) :- false, X+2 < 8, Y-1 >= 0, A is X+2, B is Y-1. 
move([X, Y], [A, B]) :- false, X+1 < 8, Y-2 >= 0, A is X+1, B is Y-2. 
move([X, Y], [A, B]) :- X-1 >= 0, Y-2 >= 0, A is X-1, B is Y-2. 
move([X, Y], [A, B]) :- false, X-2 >= 0, Y-1 >= 0, A is X-2, B is Y-1. 
move([X, Y], [A, B]) :- false, X-2 >= 0, Y+1 < 8, A is X-2, B is Y+1. 
move([X, Y], [A, B]) :- false, X-1 >= 0, Y+2 < 8, A is X-1, B is Y+2. 

knight_move(X,Y,[X,Y],1) :- false, move(X,Y). 
knight_move(X,Y,[X|P],C) :- move(X,Z), knight_move(Z,Y,P,Cn), false, C is Cn+1. 

predict_moves(X,C,P) :- knight_move(X,_,P,C), false. 

?- predict_moves([1,1],3,P), false. 

：ここに私が思い付いたものです。これは、コードが実際に実行されるため、最初は少し刺激的かもしれませんが、それでもなお、終了に影響はありません。特に、の変数knight_move/4は、現在シングルトンになっています。

エラーを削除するには、残りの表示部品を変更する必要があります。