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

Question

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

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

верно тогда и только тогда, когда H1, H2, H3, V1, V2, а также V3 являются действительными словами Райского Острова, которые образуют действительный кроссворд при написании в приведенной выше сетке. (Например, вторая буква 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 вместо чистого Пролога сделает поиск намного быстрее.

Answer 5

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