Subject: An elementary case of backtracking, my dear

From: "Philip Lafeber" <[email-masked]>
Date: Wed, 25 Oct 2000 18:04:58 GMT

Prolog = backtracking.
Searching with constraints = LOTS of backtracking.

The approach, I believe, would have to be a breadth-first search. I.e.; 
imagine if you are going depth-first. This would mean you would fill in 
words wheere there is room until you can go no further and then you 
have to backtrack until you find a 'branch' (=a list of words to fill 
in) that fits exactly. But what if you have made a choice along the way 
that makes the continuance impossible to complete? For instance, a word 
with a q horizontally that needs a word with a q vertically in the last 
position. Then, depending on how deep this word is positioned, the 
whole of the subtree has to be searched without result. The CPU will be 
fried because of the amount of backtracking.
A breadth-first would require a lot of space. If you have it, this 
should be the most efficient option.
I think.

For breadth-first and depth-first search, see "Prolog" by Bratko.

From Holland  \/
              /\      _ 
  ,,,         MM    /|-|~           _
--+++--------JMML------------------/ \~~~~~~
 tulip       mill   cow           dyke\ sea

----- Origineel Bericht -----
Van: "Empress M'shel" <[email-masked]>
Datum: Woensdag 25 Oktober 2000 15:57
Onderwerp: Re: Ideas please

> 
> 
> 
> 
> Good day,
> 
> What are the areas I should be concentrating on inorder to 
> implement a 
> simple Crossword Puzzle in Prolog...??
> 
> The point of the puzzle is to find sets of words (from a given set 
> of 
> words)such that all the spaces in the puzzle is filled with these 
> words.
> What would be be a good search to use??
> 
> I need some guidance in approaching this.........
> 
> thanks
> yours truly
> M'shel
> 
> 
> 
________________________________________________________________________
_
> Get Your Private, Free E-mail from MSN Hotmail at 
> http://www.hotmail.com.
> Share information about yourself, create your own public profile 
> at 
> http://profiles.msn.com.
> 
> 
> ----------------
> * To UNSUBSCRIBE, please use the HTML form at
> 
>    http://www.swi.psy.uva.nl/projects/SWI-
> Prolog/index.html#mailinglist
> or send mail to [email-masked] using the Subject: 
> "unsubscribe"(without the quotes) and *no* message body.
> 
> ** An ARCHIVE of this list is maintained at
> 
>    http://www.swi.psy.uva.nl/projects/SWI-Prolog/mailinglis
> 
>