Crossword solver in PROLOG

问题:

The creole of Paradise Island has 14 words: "abandon", "abalone", "anagram", "boat", "boatman", "child", "connect", "elegant", "enhance", "island", "man", "sand", "sun", and "woman".

The Paradise Times have published this crossword:

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

Write a Prolog program that starts from

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)

is true if and only if H1, H2, H3, V1, V2, and V3 are valid words of Paradise Island which form a valid crossword when written into the grid given above. (For example, the second letter of H1 should coincide with the second letter of V1.)

Use the query

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

to solve the crossword. Find all solutions to the crossword.

Hint: You might want to start from a smaller crossword and a less rich lexicon.

回答1:

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

[EDIT] As every 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 word(H1), word(H2) ...

回答2:

Uniquely domain-selecting select/2 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 only allows for unique words to be used in the puzzle (no duplicates are allowed). This might or might not be what you intended.

回答3:

Not a Prolog program per se, but a solution using Constraint Logic Programming can be found in Hakan Kjellerstrand's excellent blog on CP. It's in ECLiPSe, but easily adaptable to other Prolog systems with finite domain solvers. Using CLP instead of pure Prolog will make the search much faster.

回答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 isn't hard to get:

• we build the grid through the crosswordize/2 predicate call
• we tell prolog that every list is a word

The crosswordize/2 predicate is going through the columns two cells at a time while building lines. If you don't get it you still can "hardcode" it as Will did, it works too!

回答5:

The theory here is to check for the letters which correspond to themselves in vertical and horizontal words. This can be achieved by using placeholders in the word rule. Checkout this gist https://gist.github.com/ITPol/f8f5418d4f95015b3586 it gives an answer which claims has no repetitions. However, coming from SQL, I think to properly curb repetitions will require a solution along the lines of V1 @< V2; because just using a "not equals to" is just not sufficient enough. Pardon the multiple "[k]nots"; it's actually not that complicated. Pun intended (: