Все возможные положения коня за n ходов - бесконечный цикл в прологе

У меня проблема с откатом в Прологе, когда вычисляется решение для всех возможных позиций коня за n ходов, зная точный путь.

Мое решение печатает некоторые из первых результатов, а затем никогда не завершается, ища невозможные результаты.

Это мой код:

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 ходов. Может ли sb помочь мне с добавлением условия в мой код, чтобы мой код не возвращался назад, чтобы двигаться и зацикливаться до бесконечности?

Szymon Modelewski 26.10.2017 источник

comment

Где вы уменьшаете на единицу счетчик перемещений и не позволяете Прологу взять второй knight_move, если счетчик уменьшился? - Willem Van Onsem 26.10.2017

Ответы (3)

arrow_upward
2
arrow_downward

Проблема: вы пишете:

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

нет ни разреза, ни какого-либо другого механизма, который мешает вам перейти на эту ветвь, поэтому Пролог может продолжать эту ветвь. Кроме того, вы должны уменьшить значение счетчика Cn is C-1 и сделать это перед рекурсивным вызовом.

Прежде всего, я думаю, что лучше построить какой-нибудь предикат validation вместо того, чтобы писать все эти проверки границ:

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).

хотя это вводит некоторые дополнительные предикаты и, возможно, немного менее эффективно, теперь ясно, что все ходы допустимы.

Теперь для knigt_move/4 со счетчиком мы можем написать предложение, в котором говорится, что если счетчик опустился ниже нуля, больше ходов не делается:

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).

Или собрать все вместе:

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, мы можем определить, что можем достичь 15 квадратов за два хода. За три хода есть 148 путей, чтобы добраться до 30 квадратов:

?- 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.

Willem Van Onsem 26.10.2017

arrow_upward
4
arrow_downward

Если вы используете 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
| ?-

lurker 26.10.2017

comment

Используйте abs/1, чтобы сократить move/2 до двух правил. Вы можете сделать это даже в одном (и без (#\/)/2, ни какой-либо формы овеществления). - false; 29.10.2017

comment

В GNU это называется dist/2. - false; 29.10.2017

arrow_upward
4
arrow_downward

Прежде чем на самом деле устранять проблему, давайте сузим источник незавершения. В вашем случае это особенно сложно, потому что вы получаете хорошие и правильные ответы. Только тогда возникает проблема. Самый простой способ сузить круг проблем — добавить в программу false цели. Если результирующая программа все еще зацикливается, мы можем продолжить добавлять такие цели. Вот что я придумал:

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.

Все части, которые теперь зачеркнуты, не влияют на завершение. Поначалу это может немного раздражать, потому что этот код действительно выполняется, но тем не менее: никакого влияния на завершение. Обратите внимание, что, в частности, переменная C в knight_move/4 теперь является одноэлементной!

Вам нужно изменить оставшуюся видимую часть, чтобы удалить ошибку.

false 29.10.2017

Все возможные положения коня за n ходов - бесконечный цикл в прологе

Ответы (3)

Вопросы по теме