Заставить Prolog выбирать уникальные значения переменных

Хорошо, я новичок в Prolog, так что извините, если это что-то тривиальное, но я не могу найти правильный элегантный ответ на этот вопрос. Я пытаюсь выполнить это упражнение здесь, на learnprolognow.org, упражнение 2.4 (кроссворд).

В упражнении представлены следующие факты:

   word(astante,  a,s,t,a,n,t,e). 
   word(astoria,  a,s,t,o,r,i,a). 
   word(baratto,  b,a,r,a,t,t,o). 
   word(cobalto,  c,o,b,a,l,t,o). 
   word(pistola,  p,i,s,t,o,l,a). 
   word(statale,  s,t,a,t,a,l,e).

И решение, которое я придумал, чтобы разгадывать кроссворд для каждого слова, таково:

crossword(V1, V2, V3, H1, H2, H3) :-
   word(V1, V1a, V1bH1b, V1c, V1dH2b, V1e, V1fH3b, V1g), 
   word(V2, V2a, V2bH1d, V2c, V2dH2d, V2e, V2fH3d, V2g), 
   word(V3, V3a, V3bH1f, V3c, V3dH2f, V3e, V3fH3f, V3g), 
   word(H1, H1a, V1bH1b, H1c, V2bH1d, H1e, V3bH1f, H1g), 
   word(H2, H2a, V1dH2b, H2c, V2dH2d, H2e, V3dH2f, H2g), 
   word(H3, H3a, V1fH3b, H3c, V2fH3d, H3e, V3fH3f, H3g).

От V1a до V1g и т. Д. - символы каждого слова, а от V1bH1b до V3fH3f - символы, общие для слов в кроссворде.

Решение, похоже, работает, однако результат дает повторяющиеся значения, причем первый результат:

?- crossword(V1, V2, V3, H1, H2, H3).
V1 = astante,
V2 = baratto,
V3 = statale,
H1 = astante,
H2 = baratto,
H3 = statale .

Как я могу заставить Пролог иметь V1 \= V2 \= V3 \= H1 \= H2 \= H3? Если я буду выполнять их индивидуально, одну за другой, мне понадобится 120 перестановок, поэтому должен быть более быстрый способ, и это упражнение для новичков, поэтому я, должно быть, что-то упускаю.

Я нашел этот похожий вопрос, но представленные ответы кажутся такими сложными, я надеюсь, что есть более простой способ. Я использую swi-prolog в Ubuntu, на всякий случай.

Спасибо.


prolog prolog-dif crossword
person jbx    schedule 29.01.2013    source источник
comment
dif(V1,V2) и т. Д. maplist(dif(V1),[V2,V3,V3])   -  person false    schedule 29.01.2013
comment
Но разве div (V1, V2) не эквивалентен V1 \ = V2, поэтому мне все равно придется сделать это 120 раз, чтобы убедиться, что 6 переменных не совпадают ?!   -  person jbx    schedule 30.01.2013
comment
Обратите внимание, что это dif / 2. Да, это то же самое. с маплистом вы уже укорачиваете. Чтобы сократить еще больше, определите вспомогательный предикат alldif / 1, который истинен, если все элементы списка различны.   -  person false    schedule 30.01.2013
comment
Хорошо, и как мне это сделать? Пожалуйста, помните, что я все еще новичок, только начинаю это, поэтому не думайте, что я могу заполнить etc. или insert more here.   -  person jbx    schedule 30.01.2013
comment
если вы так рано в игре, не пытайтесь прыгать вперед; разрабатывать материал шаг за шагом. Сначала вам все равно придется вводить более подробные решения. Затем, когда вы перейдете к более продвинутым вещам, вы оцените это еще больше.   -  person Will Ness    schedule 30.01.2013

Ответы (3)


arrow_upward
10
arrow_downward

Используйте alldif/1, определенный так:

alldif([]).
alldif([E|Es]) :-
   maplist(dif(E), Es),
   alldif(Es).

Что можно использовать даже для самого общего запроса:

?- alldif(Es).
Es = [] ;
Es = [_G1924] ;
Es = [_G2061, _G2064],
dif(_G2061, _G2064) ;
Es = [_G2163, _G2166, _G2169],
dif(_G2163, _G2169),
dif(_G2163, _G2166),
dif(_G2166, _G2169) ;
Es = [_G2309, _G2312, _G2315, _G2318],
dif(_G2309, _G2318),
dif(_G2309, _G2315),
dif(_G2309, _G2312),
dif(_G2315, _G2318),
dif(_G2312, _G2315),
dif(_G2312, _G2318) ...

Смысл цели maplist(dif(E),Es) лучше всего понять, посмотрев на ответы:

?- maplist(dif(E),Es).
Es = [] ;
Es = [_G1987],
dif(E, _G1987) ;
Es = [_G2040, _G2043],
dif(E, _G2043),
dif(E, _G2040) ;
Es = [_G2093, _G2096, _G2099],
dif(E, _G2099),
dif(E, _G2096),
dif(E, _G2093) ;
Es = [_G2146, _G2149, _G2152, _G2155],
dif(E, _G2155),
dif(E, _G2152),
dif(E, _G2149),
dif(E, _G2146) ...

То есть Es - это список элементов, которые все отличаются от E. Цель maplist (dif (E), [ A, B, C]) объединяет первый элемент (в данном случае dif(E)) с каждым элементом списка. Таким образом dif(E,A), dif(E,B), dif(E,C).

person false    schedule 30.01.2013
comment
Ваше здоровье! Я только что добавил alldif, который вы указали, и в конце моего предложения crossword() добавил alldif([V1, V2, V3, H1, H2, H3]). Спасибо за вашу помощь. Должен был быть простой способ. - person jbx; 30.01.2013
comment
@jbx: Вы можете добавить это также в начале! Таким образом, пространство поиска будет сокращено. - person false; 30.01.2013
comment
Хорошая идея, спасибо. Уже достаточно хорошо, что мне удалось заставить упражнение работать :) - person jbx; 30.01.2013
comment
Небольшой последний вопрос, который может быть полезен потенциальным читателям. Что maplist(dif(E), Es) на самом деле делает? С чем dif/1 сравнивается E? И что на самом деле будет maplist/2? - person jbx; 30.01.2013
comment
@jbx: Задайте вопрос Прологу: ответы на ?- maplist(dif(E), Es). совершенно ясны! - person false; 30.01.2013
comment
@jbx: Надеюсь, это вас не смущает. Но ответы, которые дает Пролог, часто являются наиболее проницательным способом понять отношение. - person false; 30.01.2013
comment
Ага, честно говоря, понятия не имею :). Я пробовал maplist(dif(E), Es). и только что получил Es = []. Что бы это ни значило :) - person jbx; 30.01.2013
comment
Спасибо, чтобы получить четкое представление, как предикат арности 2 dif/2 используется с формой арности 1 в maplist? - person jbx; 30.01.2013
comment
@jbx: через call(dif(X),A). Это то же самое, что и dif(X,A), подробнее см. Ссылку в списке карт. - person false; 30.01.2013

arrow_upward
0
arrow_downward

length(List, N): N - длина списка
sort(List, SortedList): SortedList - это отсортированная версия List (повторяющиеся элементы удаляются)

С другой стороны, может быть быстрее иметь список доступных слов и удалять одно, когда оно используется; не только вам не нужно будет выполнять проверку в конце, но вы избежите бессмысленных экземпляров (A1 = foo, A2 = foo остановится немедленно, а не будет отклонен в конце). Другими словами, обрезка веток.

person Thanos Tintinidis    schedule 29.01.2013
comment
Спасибо, но не могли бы вы подробнее рассказать, как мне использовать факты, предоставленные в упражнении, чтобы, наконец, достичь crossword(V1, V2, V3, H1, H2, H3), каждый из которых гарантирует, что все они различны? В этом суть этого упражнения. - person jbx; 30.01.2013

arrow_upward
0
arrow_downward

Либо то, что @false сказал вам в комментариях; или мне нравится использовать выбор домена:

selectM([A|As],S,Z):- select(A,S,S1),selectM(As,S1,Z).
selectM([],Z,Z).

word(astante,  [a,s,t,a,n,t,e]). 
word(astoria,  [a,s,t,o,r,i,a]). 
word(baratto,  [b,a,r,a,t,t,o]). 
word(cobalto,  [c,o,b,a,l,t,o]). 
word(pistola,  [p,i,s,t,o,l,a]). 
word(statale,  [s,t,a,t,a,l,e]).

crossword(Words) :- findall(W, word(_,W), WS),
   Words = [[ _,A,_,B,_,C,_], 
            [ _,D,_,E,_,F,_], 
            [ _,G,_,H,_,I,_],
            [ _,A,_,D,_,G,_],
            [ _,B,_,E,_,H,_],
            [ _,C,_,F,_,I,_]],
   selectM( Words, WS, _).
person Will Ness    schedule 30.01.2013
comment
Спасибо, ваш подход кажется изящным. Но вы изменили список фактов, приведенный в упражнении? - person jbx; 30.01.2013
comment
@jbx да, я сделал. :) Если вам это не разрешено, вы можете преобразовать одно в другое: wordL(W):- word(_, A,B,C,D,E,F,G), W=[ вставьте сюда больше ].. Затем вы можете использовать wordL вместо word при вызове findall. - person Will Ness; 30.01.2013
comment
Ну это не мне не разрешено, это способ упражнения, и я пытаюсь учить вещи медленно. Что было бы у insert more here? - person jbx; 30.01.2013
comment
@jbx Я оставил это на ваше усмотрение. :) Скажем, для word(day, d, a, y) мы бы хотели W=[d,a,y], верно? Если вам сейчас сложно, возможно, лучше сначала изучить введение в Prolog. - person Will Ness; 30.01.2013
comment
Да в том-то и дело. Это упражнение - это глава 2 на learnprolognow.org (в главе 1 просто объясняются атомы, простые термины и т. Д.). Я четко сказал, что в вопросе хочу указать, что я новичок, поэтому мне трудно преодолеть разрыв в данный момент. Но спасибо и за ответ. - person jbx; 30.01.2013
comment
@jbx Попробуем еще раз. Мы конвертируем word(day, d, a, y) в [d,a,y] с помощью word(_,A,B,C), W=[A,B,C]. Или, если бы у нас был факт word(month, m,o,n,t,h), мы бы преобразовали его с помощью word(_,A,B,C,D,E),W=[A,B,C,D,E]. Здесь у нас есть слова из семи букв, вот и все. Это помогает? - person Will Ness; 30.01.2013