Thanks Paul for your reply. You may be right about my placement checker. What I currently do is as follows:
Starting with first char of word I want to place, loop through the characters of each word that is already on the puzzle and see if a match can be found. If a match is found then I calculate where the new word would appear on the grid based on crossing the existing word where they characters match. I then check if there are any words in the way or the new word goes off the grid. I also check that the new word is not adjacent to another word My code does not allow words to be added unless they cross another word so perhaps allowing disconnected placement would speed things up. I will give it a try. Thanks again for your help on this. Paul -----Original Message----- From: flashcoders-boun...@chattyfig.figleaf.com [mailto:flashcoders-boun...@chattyfig.figleaf.com] On Behalf Of Paul Andrews Sent: 02 June 2009 11:54 To: Flash Coders List Subject: Re: [Flashcoders] Crossword generator advice 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 very inefficient placement checker. A definite improvement to my suggestion would be to have a two stage placement algorithm - first of all only laying out words if they overlap another word, then if no solution is found by laying out the word as an overlap, it would then attempt a disconnected placement. I think that would 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 lay > them 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 on >> what >> 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 am >> assuming >> 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 be >> much >> appreciated. >> >> Thanks >> >> Paul >> >> ____ _______________________________________________ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders _______________________________________________ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
