Решатель кроссвордов в PROLOG

Question

В креольском Райском Острове есть 14 слов: «покинуть», «ушка», «анаграмма», «лодка», «лодочник», «ребенок», «соединить», «элегантный», «улучшать», «остров»."," мужчина "," песок "," солнце "и" женщина ".

Paradise Times опубликовала этот кроссворд:

Кроссворд содержит некоторые из 14 слов, но не содержит других слов.

Напишите программу Prolog , которая начинается с

word(X) :-
member(X,
[
[a,b,a,n,d,o,n], [a,b,a,l,o,n,e], [a,n,a,g,r,a,m],
[b,o,a,t], [b,o,a,t,m,a,n], [c,h,i,l,d],
[c,o,n,n,e,c,t], [e,l,e,g,a,n,t], [e,n,h,a,n,c,e],
[i,s,l,a,n,d], [m, a, n], [s,a,n,d],
[s,u,n], [w, o, m, a, n]
]).

solution(H1,H2,H3,V1,V2,V3) :-

и определяет предикат solution таким образом, что

solution(H1,H2,H3,V1,V2,V3)

true тогда и только тогда, когда H1, H2, H3, V1, V2 и V3 являются действительными словами Paradise Island, которые образуют действительный кроссворд при записи в таблицу, приведенную выше.(Например, вторая буква H1 должна совпадать со второй буквой V1.)

Используйте запрос

?- solution(H1,H2,H3,V1,V2,V3).

, чтобы разгадать кроссворд.Найдите все варианты решения кроссворда.

Подсказка. Возможно, вы захотите начать с меньшего кроссворда и менее богатого словаря.

Answer 1

Просто посмотрите на картинку, слова написаны буквами, у вас есть все на картинке, переведите это в строки Пролога (мое решение имеет 12 строк, 2 строки для одного слова).

[РЕДАКТИРОВАТЬ] Поскольку каждое тело дает свое собственное решение, вот мое:

solution(H1,H2,H3,V1,V2,V3) :-
    H1 = [_,A2,_,A4,_,A6,_],
    H2 = [_,B2,_,B4,_,B6,_],
    H3 = [_,C2,_,C4,_,C6,_],
    V1 = [_,A2,_,B2,_,C2,_],
    V2 = [_,A4,_,B4,_,C4,_],
    V3 = [_,A6,_,B6,_,C6,_],
    maplist(word, [H1,H2,H3,V1,V2,V3]).

PS Я изначально написал слово (H1), слово (H2) ...

Answer 2

Уникальный выбор домена select/2 делает трюк:

select([A|As],S):- select(A,S,S1),select(As,S1).
select([],_). 
words(X) :- X = [
    [a,b,a,n,d,o,n], [a,b,a,l,o,n,e], [a,n,a,g,r,a,m],
    [b,o,a,t],       [b,o,a,t,m,a,n], [c,h,i,l,d],
    [c,o,n,n,e,c,t], [e,l,e,g,a,n,t], [e,n,h,a,n,c,e],
    [i,s,l,a,n,d],   [m, a, n],       [s,a,n,d],
    [s,u,n],         [w, o, m, a, n]
    ].
solve(Crossword):- words(Words), 
    Crossword = [ [_,A2,_,A4,_,A6,_],
                  [_,B2,_,B4,_,B6,_],
                  [_,C2,_,C4,_,C6,_],
                  [_,A2,_,B2,_,C2,_],
                  [_,A4,_,B4,_,C4,_],
                  [_,A6,_,B6,_,C6,_] ],
    select(Crossword, Words).
solve:- solve(Crossword),
        maplist(writeln, Crossword), writeln(';'), fail 
     ;  writeln('No more solutions!').

Тест:

7 ?- solve.
[a, b, a, n, d, o, n]
[e, l, e, g, a, n, t]
[e, n, h, a, n, c, e]
[a, b, a, l, o, n, e]
[a, n, a, g, r, a, m]
[c, o, n, n, e, c, t]
;
[a, b, a, l, o, n, e]
[a, n, a, g, r, a, m]
[c, o, n, n, e, c, t]
[a, b, a, n, d, o, n]
[e, l, e, g, a, n, t]
[e, n, h, a, n, c, e]
;
No more solutions!

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

Answer 3

solution(H1, H2, H3, V1, V2, V3) :-
    crosswordize([H1,H2,H3], [V1,V2,V3]),
    maplist(word, [H1,H2,H3,V1,V2,V3]).

crosswordize([], [[_],[_],[_]]).
crosswordize([[_, X1, _, X2, _, X3, _]|Lines],
             [[_, X1|R1], [_, X2|R2], [_, X3|R3]]) :-
    crosswordize(Lines, [R1,R2,R3]).

Алгоритм не сложен:

• мы строим сетку с помощью предиката crosswordize/2
• мы говорим прологу, что в каждом списке есть слово

Предикат crosswordize/2 проходит по столбцам по две ячейки за раз при построении линий. Если вы не получите его, вы все равно можете «жестко» его кодировать, как это сделал Уилл, он тоже работает!

Answer 4

Не программа Prolog сама по себе, а решение с использованием Constraint Logic Programming можно найти в Отличном блоге Хакана Кьеллерстранда на CP .Он находится в ECLiPSe, но легко адаптируется к другим системам Prolog с конечными доменными решателями.Использование CLP вместо чистого Prolog значительно ускорит поиск.

Answer 5

Теория здесь заключается в проверке букв, которые соответствуют им в вертикальных и горизонтальных словах.Это может быть достигнуто с помощью заполнителей в правиле word.Оформить заказ https://gist.github.com/ITPol/f8f5418d4f95015b3586, он дает ответ, претензии которого не повторяются.Однако, исходя из SQL, я думаю, что для правильного ограничения повторений потребуется решение, аналогичное V1 @< V2;потому что просто использование «не равно» просто недостаточно.Простите за множественные "[k] nots";это на самом деле не так сложно.Пан предназначен (: