Re: [Flashcoders] Crossword generator advice

Paul Andrews Tue, 02 Jun 2009 03:56:01 -0700

Paul Steven wrote:

Here is a link to the crossword generator in its current state.


http://www.mediakitchen.co.uk/crossword.html

Cheers

Paul

-----Original Message-----
From: flashcoders-boun...@chattyfig.figleaf.com
[mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul Steven
Sent: 02 June 2009 10:27
To: 'Flash Coders List'
Subject: RE: [Flashcoders] Crossword generator advice

Sorry to drag this one out but I have one last question.

I implemented the recursive solution as Paul Andrews and Charles suggested
however I find that it can take up to 8 minutes to generate a solution
(which incidentally is pretty much the same amount of time my non recursive
implementation takes)

I think there's a problem in the algorithm again or you have a veryinefficient placement checker.

A definite improvement to my suggestion would be to have a two stageplacement algorithm - first of all only laying out words if they overlapanother word, then if no solution is found by laying out the word as anoverlap, it would then attempt a disconnected placement. I think thatwould improve things.


It's difficullt to know why it takes so long without seeing the code.

Paul

If I order my words from largest to smallest first this actually seems to
result in a longer time. I am thinking this is perhaps because one of the
longest words (tarragon) is at the bottom of the solution:
http://www.mediakitchen.co.uk/solution.gif

Anyway I do not mind it taking so long as a new crossword will only be
generated once a week. However I am curious as to whether this sounds like a
flaw in my code or if it is just the result of having to try so many
combinations to find the unique solution?

If I adjust my list of words into the order in which it looks like they
would be placed one at a time onto the grid, then the solution only takes
about 3 seconds to generate.

Because I know there is the possibility that having the list ordered in a
particular way can result in a super fast puzzle creation time, I am
wondering if it is worth just randomising the list every 10 seconds if a
solution has not been found?

Promise not to ask any more questions about this crossword generator after
this one:)

Thanks

Paul

-----Original Message-----
From: flashcoders-boun...@chattyfig.figleaf.com
[mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul Andrews
Sent: 01 June 2009 11:14
To: Flash Coders List
Subject: Re: [Flashcoders] Crossword generator advice

You should use recursion.

At each stage you should loop through the available words, trying to laythem onto the crossword area.


Paul

It goes a bit like this:

var wordList = ["word1","word2","word3", ..   ];
var xwordSolution:XwordSolution;
var currentSolution= new XwordSolution(maxWidth, maxHeight); // emptyGrid

xwordSolution = layoutXword(wordList, currentSolution);

if (xwordSolution.isValid())
trace("Solved!")
else
trace("no solution found");

function layoutXword(words:Array,currentSolution:XwordSolution):XwordSolution

{
while (words.length > 0){
currentWord = words.pop();

// horizontal

newSolution = layoutHorizontalWord(currentWord, currentSolution);
if (newSolution.isValid())
{
    newSolution = layoutXword(words, newSolution );
    if (newSolution.isValid())
        return newSolution; // solved
}
// the horizontal layout wasn't possible, try vertical
newSolution = layoutVerticalWord(currentWord, currentSolution);
if (newSolution.isValid())
{
    newSolution = layoutXword(words, newSolution );
    if (newSolution.isValid())
        return newSolution; // solved
}
// couldn't layout this word, try the next
}
// Couldn't layout any of the words - solution failed.
return newSolution; // this will be failed
}

----- Original Message -----From: "Paul Steven" <paul_ste...@btinternet.com>

To: "'Flash Coders List'" <flashcoders@chattyfig.figleaf.com>
Sent: Monday, June 01, 2009 10:33 AM
Subject: RE: [Flashcoders] Crossword generator advice

I am still struggling to find a solution to this crossword generator and
could do with some advice on a possible solution I want to try.

If I enter my list of 16 words in a particular order (an order based onwhat

looks like the order the solution would place them), the generator creates
the puzzle in a matter of seconds.

However if I enter them in a different order, the generator always breaks

out of the loop by my exit condition (number of loops > 5000). I amassuming

this is either due to an error in my code or due to the fact there are so
many combinations to try.

I am therefore thinking a possible solution is to try every permutation (I
think this is the right word) of the 16 words. If I am correct there would
be 240 possible permutations. ((X - 1) * X) where X is the number of items
in the list.

I am not sure however how to create the 240 variations of the list.

Any advice on how to create these 240 permutations of the list would bemuch

appreciated.

Thanks

Paul

____


_______________________________________________
Flashcoders mailing list
Flashcoders@chattyfig.figleaf.com
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders

Re: [Flashcoders] Crossword generator advice

Reply via email to