From lafeber@zonnet.nl  Wed Oct 25 20:04:37 2000
Received: from relay2.zonnet.nl (relay2.zonnet.nl [212.48.41.22])
	by swi.psy.uva.nl (8.9.3/8.9.3) with ESMTP id UAA10148;
	Wed, 25 Oct 2000 20:04:37 +0200 (MET DST)
Received: from mail3.zonnet.nl ([10.170.1.24]) by
          relay2.zonnet.nl (Netscape Messaging Server 4.1) with ESMTP id
          G2ZZKA05.JBU; Wed, 25 Oct 2000 20:04:58 +0200 
Received: from zonnet.nl ([10.170.1.31]) by mail3.zonnet.nl
          (Netscape Messaging Server 4.15) with ESMTP id G2ZZKA00.4ON;
          Wed, 25 Oct 2000 20:04:58 +0200 
From: "Philip  Lafeber" <lafeber@zonnet.nl>
To: "Empress M'shel" <m_shel_m@hotmail.com>
Cc: prolog@swi.psy.uva.nl, prolog-request@swi.psy.uva.nl
Message-ID: <64d54651a8.651a864d54@zonnet.nl>
Date: Wed, 25 Oct 2000 18:04:58 GMT
X-Mailer: Netscape Webmail
MIME-Version: 1.0
Content-Language: nl
Subject: An elementary case of backtracking, my dear
X-Accept-Language: nl
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: 7bit

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" <m_shel_m@hotmail.com>
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 prolog-request@swi.psy.uva.nl 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
> 
> 

