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)
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 _______________________________________________ Flashcoders mailing list Flashcoders@chattyfig.figleaf.com http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
