Пролог - генерировать кроссворды

Question

Я сталкиваюсь с этим трудным упражнением, я уже видел другие упражнения о кроссвордах (то есть последнее упражнение "p-99: девяносто девять программ пролога", или то, о котором сообщалось в "Программе пролога для ИИ" Братко), но это отличается и сложнее, потому что здесь у нас нет шаблона для заполнения.

Текст:

Напишите программу Prolog для генерации кроссворда. Предположим, у вас есть словарь фактов, подобных этому: w(Word,Lentgth). Запишите предикатный кроссворд (C,W,H), чтобы создать экземпляр C, для всех возможных списков (кроссворд) списков (строка кроссворда) символа словаря, где черная клетка представлена ​​звездочкой.
Пример:

w(online,6).
w(prolog,6).
w(perl,5).
w(emacs,5).
w(linux,5).
w(gnu,3).
w(mac,3).
w(nfs,3).
w(sql,3).
w(web,3).
w(xml,3).
w(a,1).
w(b,1).
w(e,1).
w(i,1).
w(l,1).
w(m,1).
w(n,1).
w(o,1).
w(q,1).
w(r,1).
w(s,1).
w(t,1).
w(u,1).
w(w,1).

?- crossword(C,9,6).
C=[[p,r,o,l,o,g,*,*,e],
   [e,*,n,*,*,n,*,*,m],
   [r,*,l,i,n,u,x,*,a],
   [l,*,i,*,f,*,m,a,c],
   [*,*,n,*,s,q,l,*,s],
   [*,w,e,b,*,*,*,*,*]]

Данные подсказки

1) Вы можете добавить в словарь эти "черные" слова:

black(*,1).
black(**,2).
black(***,3).
black(****,4).
black(*****,5).

2) Каждая строка представляет собой последовательность чередующихся "белых" слов (обычных слов) и "черных" слов, и эта последовательность может начинаться / заканчиваться обоими.

3) Я предлагаю вам управлять 2 возможностями предыдущего пункта с 2 различными предложениями.

4) Кроссворд - это матрица символов, поэтому его транспонирование все еще остается кроссвордом.

5) Кроссворд транспонирования уже создан, поэтому вам нужно только проверить его выполнимость с помощью словаря.

Вот что мне пришло в голову: создать список из H (высота кроссворда, строки) списков (строки кроссворда), для каждого списка (строки) я пытаюсь вставить слова из словаря, за которыми следуют "черные" слова и затем снова слово, пока строка не заполнится, или то же самое, начиная с "черного". Когда кроссворд заполнен, я переставляю его и проверяю, является ли транспонирование допустимым кроссвордом: каждое содержащееся слово является допустимым словом из словаря. Я знаю, что это очень неэффективный метод, я попытался с помощью небольшого словаря сгенерировать кроссворд 2x2, он правильно генерирует первые два, но, похоже, для третьего нужны годы. Я не знаю, если что-то не так в моем коде, может быть, он застрял где-то. Знаете ли вы более эффективный способ решения этой проблемы или вы видите что-то, что можно улучшить в моем коде?

crossword(C,W,H):- create(C,H),
                   insert_words(C,W,[],_),
                   clpfd:transpose(C,Traspose),
                   isok(Traspose).

insert_words([],_,U,U).
insert_words([H|T],W,Uacc,U):-
                             (add_white(H,[],C,[],Uacc,Udef);
                              add_black(H,[],C,[],Uacc,Udef)),
                              insert_words(T,C,Udef,U).

create(Puzzle,H) :- length(Puzzle,H).


add_white(P,P,0,_,U,U).
add_white(P,Row,R,Used,Uacc,Udef):- 
                                R\=0,
                                w(Word,L),
                                \+member(Word,Used),
                                \+member(Word,Uacc),
                                R2 is R-L,
                                R2 >= 0,
                                atom_chars(Word,Word2),
                                append(Row,Word2,Row2),
                                append(Used,[Word],Used2),
                                append(Uacc,[Word],Uacc2),
                                add_black(P,Row2,R2,Used2,Uacc2,Udef).

add_white(P,Row,R,Used,Uacc,Udef):-
                                   R\=0,
                                   w(Word,L),
                                   \+member(Word,Used),
                                   R2 is R-L,
                                   R2 < 0,
                                   append(Used,[Word],Used2),
                                   add_white(P,Row,R,Used2,Uacc,Udef).

add_white(P,Row,R,Used,Uacc,Udef):-
                                   R\=0,
                                   w(Word,_),
                                   member(Word,Used),
                                   add_white(P,Row,R,Used,Uacc,Udef).


add_black(P,P,0,_,U,U).
add_black(P,Row,R,Used,Uacc,Udef):-
                                   R\=0,
                                   black(Black,L),
                                   R2 is R-L,
                                   R2 >= 0,
                                   atom_chars(Black,Black2),
                                   append(Row,Black2,Row2),
                                   add_white(P,Row2,R2,Used,Uacc,Udef).

add_black(P,Row,R,Used,Uacc,Udef):-
                                   R\=0,
                                   black(_,L),
                                   R2 is R-L,
                                   R2 < 0,
                                   add_black(P,Row,R,Used,Uacc,Udef).

isok([]).
isok([H|T]):-split(H,*,R),
        check(R),
        isok(T).

split(L,C,R):-split2(L,C,X),trim(X,R).

split2(In, Sep, [Left|Rest]) :-
append(Left, [Sep|Right], In), !, split2(Right, Sep, Rest).
split2(In, _Sep, [In]).

trim([],[]).
trim([H|T],[H|T2]):-H\=[],trim(T,T2).
trim([H|T],Y):-H=[],trim(T,Y).

check([]).
check([H|T]):-
               atom_chars(X,H),
               w(X,_),
               check(T).

Я использую этот небольшой словарь вместо оригинального, чтобы протестировать мою программу и сгенерировать простые кроссворды 2x2, но, как я уже говорил, он застревает после того, как правильно нашел 2 решения.

w(ci,2).
w(ca,2).
w(i,1).
w(a,1).
black(*,1).