prolog - Backtracking over list in crossword-style puzzle -

prolog - Backtracking over list in crossword-style puzzle -

i'm creating programme take list of words, , square, crossword-style grid of spaces, , homecoming solution, filled crossword such words fit coherently. size of grid arbitrary, square.

see here illustration of i'm trying do: http://en.wikipedia.org/wiki/fill-in_(puzzle)

i have meat of programme down. first set of predicates take grid , create logical variables every slot, ignoring blacked out slots (the #s). then, create list of possible words greater 1 slot long (words 1 letter long not valid). result grid shape (a simple example):

#_# ___ #_#

where each row element of "puzzle list" top bottom, ie

row 1 row 2 row 3 [[#,_,#],[_,_,_],[#,_,#]]

will filled free logical variables so:

#x# abc #z#

and list (part 0):

[[#,x,#],[a,b,c],[#,z,#]]

then, wordlist of form:

[['m','e','n'],['n','e','w']]

is given, end solution being

#m# new #n#

so far fill grid list variables in part 0, , fill list possible slots words go in (the "slot list"), slot made every string of vertical , horizontal spaces longer 1 space in length (for example):

[[a,b,c],[x,b,z]]

so have these set up, such unifying word slot of slot list unify word matching variables in puzzle list.

now, inputs such there 1 way arrange words in grid (unlike illustration there 2 ways, ignore that), 1 solution provided completed programme (a solution beingness filled puzzle grid).

the word-unification algorithm should be:

1. take word word list 2. go through slot list , unify first slot succeeds 3. if there no successful bindings, fail , backtrack seek new set of unifications 4. maintain failing , backtracking until solution found such words bind

my code unification of words slots below:

%%% takes word (w) , list of slots (s|ss) , attempts bind slot bind_word(w,[s|ss],slots):- bind_w(w,[s|ss],[],slots). bind_w(_,[],acc,acc). bind_w(w,[s|ss],acc,slots):- ( w = s -> % word bind next slot? append(acc,[s],acc1), % yes add together bound slot accumulator append(acc1,ss,acc2), % add together rest of slots accumulator bind_w(_,[],acc2,slots) % exit success ; length(ss,0) -> fail % no word doesn't bind, if there no slots left bind has failed ; append(acc,[s],acc1), % no word doesn't bind, there slots left, append unbound slot accumulator bind_w(w,ss,acc1,slots) % move next slot ). %%%

what want if hits

length(ss,0) -> fail

then backtrack origin , seek again, instead of trying 1 time again same bindings, consider successful bindings failures , skip on them, example:

1. seek bind word b,e,n first slot, , works 2. seek bind word m,a,x sec slot, , doesn't work , there no slots left 3. backtrack (1), , instead of binding ben slot 1 (which succeeded before), skip next slot , seek unifying ben sec slot.

unfortunately, when hits

length(ss,0) -> fail

it considers entire thing failure , not backtrack, fails everything. solving predicate follows:

%%% takes puzzle grid , wordlist , solves puzzle solve_puzzle(solution, [], solution). solve_puzzle(puzzle, wordlist, solved):- fill_slots_h(puzzle,slots1,puzzle1), % fill out puzzle logical variables in every blank space (results = puzzle1), horizontal word slots (results = slots1) flip(puzzle1,0,puzzle1_flipped), % flip puzzle vertical utilize (results = puzzle1_flipped) fill_slots_v(puzzle1_flipped,slots1,slots), % take vertical puzzle , append slots vertical words onto end of existing slot list slots final unbound slot list flip(puzzle1_flipped,1,puzzle_final), % flip puzzle normal puzzle_final final unbound puzzle !, % create these choices final insert_words(wordlist,slots,final_slotlist),% insert words slots , homecoming finished slot list slots = final_slotlist, % bind logical variables in final slotlist slotlist linked puzzle solve_puzzle(puzzle_final, [], solved). % puzzle filled, homecoming solution %%% %%% takes (w)ordlist, , (s)lot list , binds every word slot until puzzle finished insert_words([],slots,slots). insert_words([w|ws], current_slotlist, filled_slotlist):- bind_word(w,current_slotlist,partial_slotlist), insert_words(ws, partial_slotlist, filled_slotlist). %%%

i fill out puzzle, list of horizontal word slots, transpose puzzle , list of vertical word slots (appending them horizontal one). then, fill out slot list words, unify filled list empty slot list (which unifies words puzzle grid), homecoming finished puzzle.

how create if fails unify word, backtracks , skips on successes , tries choice? i've thought of trying bind, if fails, randomise word list , seek again, doesn't sound logic-driven me...

thanks in advance.

you have been thinking bit much search algorithm, , little logical meaning of program. in prolog have both, , can take while find right balance.

if understand correctly, want take 1 word after other, seek fit slot, , backtrack chronologically. easy in prolog. words in word list, utilize recursion. seek slots in slot list, utilize member/2. backtracking happens automatically:

solve(ss) :- ws=[[b,e,g],[w,e,b],[n,e,w],[b,e,n]], ss=[[a,b,c],[d,b,f],[f,h,i],[c,h,l]], all_member(ws, ss). all_member([], _). all_member([w|ws], ss) :- member(w, ss), all_member(ws, ss). ?- solve(ss). ss = [[b, e, n], [w, e, b], [b, e, g], [n, e, w]] yes (0.00s cpu, solution 1, maybe more) ss = [[w, e, b], [b, e, n], [n, e, w], [b, e, g]] yes (0.00s cpu, solution 2, maybe more) no (0.01s cpu)

[i have assumed words in word list different]

ps: 1 time have corrected bind_w/4 replacing if-then-else disjunction, becomes complex version of member/2. don't need accumulator pair , appends, because build re-create of slots list (which don't need, utilize original one). don't need first clause of bind_w/4, because want fail empty slot list. 1 time remove this, don't need length-test longer.

prolog logic crossword