Блог

Главная - Вопросы по программированию - Перемещение по списку, указывая возможные ходы. Пролог

Перемещение по списку, указывая возможные ходы. Пролог

#prolog #predicate #maze

Вопрос:

Поэтому я недавно начал изучать Пролог, и у меня возник вопрос о создании предиката, который дает вам все возможные решения (следующие шаги) по мере того, как задается текущее место. Лучший пример-лабиринт. Итак, это мои данные, которые говорят мне, что «w = белый» и «b = черный» в лабиринте 5×5:

 grid([ [w, w, w, b, w],
    [b ,b, w, w, w],
    [w, w, w, b, w],
    [w, b, b, b, b],
    [w, w, w, w, w] ]).

Я также реализовал предикат под названием white/1, который сообщает мне, является ли данное место в лабиринте белым:

 white(X/Y) :-
    grid(M),
    nth1(X, M, Line),
    nth1(Y, Line, w).

Что я сейчас хочу сделать, так это создать предикат, который даст мне все возможные ходы в лабиринте. Например, если я запрошу:

 ?- move(5/2, NextState).
NextState = 4/2 ;
NextState = 5/1 ;
NextState = 5/3 ;
No

Это мой код, но он выдает false, и я знаю, что это совершенно неправильно, но я не знаю, как реализовать такой предикат:

 move(5/5, _).

move(X/Y, NextState) :-
    white(X/Y),
    X1 is X   1,
    X1 =< 5,
    move(X1/Y, NextState),
    Y1 is Y   1,
    Y1 =< 5,
    move(X/Y1, NextState),
    X2 is X - 1,
    X2 >= 5,
    move(X2/Y, NextState),
    Y2 is Y - 1,
    Y2 >= 0,
    move(X/Y2, NextState).

Если бы кто-нибудь мог мне помочь, я был бы очень признателен! 🙂

Редактировать:

 move(X/Y, _) :-
    white(X/Y).

move(X/Y, X/Y) :-
    X1 is X   1,
    move(X/Y, X1/Y);
    X2 is X - 1,
    move(X/Y, X2/Y);
    Y1 is Y   1,
    move(X/Y, X/Y1);
    Y2 is Y - 1,
    move(X/Y, X/Y2).

Если я спрошу, это даст мне:

 ?- move(3/3, NextState).
true ;
NextState = 3/3 ;
NextState = 3/3 ;
NextState = 3/3 ;
NextState = 3/3 ;

Комментарии:

1. Здесь вам нужны дизъюнкции. Узнайте, как использовать ; .

2. @rajashekar You need disjunctions here. Learn how to use ; , Это напоминает мне об этой шутке. A person is drowning 100 meters off the shore. The lifeguard throws them a line. The by stander notes that the line is only 51 meters long. The lifeguard says, I went more than half way. ; В то время как это хорошо, без объяснения причин, это дает результат только на полпути. 🙁 Другая половина может быть сокращена ! , условно -> или что-то более сложное.

3. @rajashekar Я реализовал точку с запятой (;), и это дает мне 4 возможных решения, но неправильных. Лично я считаю, что мой базовый вариант неверен.

4. Что происходит, когда вы ударяетесь о стену?

5. Представляет интерес: Решение лабиринта с розеттакодом — Хотя вы не решаете проблему лабиринта так, как вы, код представляет ценность.

Ответ №1:

 move(X/Y, X1/Y1, Xm/Ym) :-
    X1 is X   1, Y1 = Y, X1 =< Xm;
    X1 is X - 1, Y1 = Y, X1 > 0;
    X1 = X, Y1 is Y   1, Y1 =< Ym;
    X1 = X, Y1 is Y - 1, Y1 > 0.

Для каждой строки в приведенном выше предикате у нас есть новое направление. Это Xm/Ym границы лабиринта.

 | ?- move(5/2, X, 5/5).

X = 4/2 ? ;

X = 5/3 ? ;

X = 5/1

yes

Вы можете удалить Xm/Ym в качестве аргумента и просто поместить 5 в тело. Или вы можете определить новый предикат

 move1(Current, Next) :- move(Current, Next, 5/5)

Вместо дизъюнкций мы также можем написать несколько предложений.

 move(X/Y, X1/Y) :- X1 is X   1, X1 =< 5.
move(X/Y, X1/Y) :- X1 is X - 1, X1 > 0.
move(X/Y, X/Y1) :- Y1 is Y   1, Y1 =< 5.
move(X/Y, X/Y1) :- Y1 is Y - 1, Y1 > 0.

И то, и другое эквивалентно, и это еще более ясно.

Метки: ,