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

Question

Креоль острова Рая имеет 14 слов: «отбросить», «ушка», «анаграмма», «лодка», «лодочник», «ребенок», «подключиться», «изящно», «улучшить «остров», «человек», «песок», «солнце» и «женщина».

Рай Времена опубликовали этот кроссворд:

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

Написать программа Пролог, который начинается с

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 являются действительными словами P aradise Остров, который образует действительное кроссворд, записанный в сетку, указанную выше. (Например, вторая буква H1 должна совпадать со второй буквой из V1.)

использовать запрос

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

решить кроссворд. Найти все решения кроссворда.

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

Answer 1

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

Answer 2

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

[EDIT] Поскольку каждое тело дает свое собственное решение, вот мое:

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

Уникально домена выбора 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 5

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