Crossword Solver in PROLOG

Question

Creole of Paradise Island has 14 words: “refuse”, “abalone”, “anagram”, “boat”, “boatman”, “child”, “connect”, “gracefully”, “improve”, “island” “man”, "sand", "sun" and "woman".

Paradise Times published this crossword puzzle:

The crossword puzzle contains some of the 14 words, but no other words.

Write a Prolog program starting with

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

and defines the predicate solution in such a way that

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

true if and only if H1 , H2 , H3 , V1 , V2 and V3 are the actual words of Paradise Island, which forms a real crossword puzzle written in the grid above. (For example, the second letter H1 must match the second letter of V1 .)

Use query

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

to solve a crossword puzzle. Find all crossword puzzle solutions.

Hint: You can start with a smaller crossword puzzle and less rich vocabulary.

Answer 1

Just look at the picture, the words are written in letters, you have everything in the picture, translate it into Prolog lines (my solution has 12 lines, 2 lines for one word).

[EDIT] Since each body gives its own solution, here is mine:

 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 I originally wrote the word (H1), the word (H2) ...

Answer 2

Unique selection of the select/2 domain does the trick:

 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!'). 

Test:

 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! 

This solution allows the use of unique words in the puzzle (duplication is not allowed). This may or may not be what you intended.

Answer 3

Not a Prolog program in itself, but a solution using Constraint Logic Programming can be found at Hakan Kjellerstrand's excellent CP blog . It is in ECLiPSe, but easily adapts to other Prolog systems with end domain solvers. Using CLP instead of pure Prolog will make searching much faster.

Answer 4

 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]). 

The algorithm is not difficult to obtain:

• we build a grid using the crosswordize/2 predicate call
• we say prologue that every list is a word

The crosswordize/2 predicate passes through columns of two cells at a time, building rows. If you do not, you can still “hard-write” it, as Will did; it works too!

Answer 5

The theory here is to check letters that match them in vertical and horizontal words. This can be achieved using placeholders in the word rule. Checkout this gist https://gist.github.com/ITPol/f8f5418d4f95015b3586 he gives an answer in which the claims have no repetition. However, based on SQL, I think that for correct repetition restraint, a solution along the lines V1 @< V2 ; because just using "not equal" is not enough. Forgive the plural "[k] nots"; it's actually not that difficult. Pun is for (: