|Welcome to the Monastery|
find all paths of length n in a graphby davidj (Priest)
|on Jan 10, 2006 at 17:43 UTC||Need Help??|
davidj has asked for the
wisdom of the Perl Monks concerning the following question:
My fellow monks,
I know this smells like homework, but I assure you, it is not.
First, as to what prompts my question: My 7 year old daughter has been turned on to the old Parker Brothers game 'Boggle'. She absolutely LOVES it. For those of you who don't know the game, its quite simple: 16 cubes with letters on each side are arranged into a 4x4 grid of letters from which you need to find words. You have 3 minutes to find as many 3 to 6 letter words of as you can. The rules are simple: 1) the words are created from sequences of adjacent letters (including diagonal), 2) the same position cannot be used more than once in the same word.
So, being the wonderful father that I try to be, I thought 'hmm, I'll program it so she can play it on the computer.' Generating the 16 letters from the actual cube values and arranging them into a 4x4 grid was trivially easy. It took like 5 minutes.
Now, for the vocabulary-building value of the game, I thought it would be cool to list all the words that actually exist. That is where I am stuck. In order to do this I need to generate all paths of lengths 3 to 6 starting with each cube position. I have the grid represented as an adjacency list and I know how to use depth first search to find paths from one node to another, but I am struggling to find a way to use DFS to generate all valid paths of length n, regardless of what the final node is. I would show you what I have but it is less than useful. It doesn't even come close to working.
The numbered grid looks like this:
The list looks like this:
what I need is the list of paths of length 3 to 6
After I have the list of paths generated it will be trivial to substitute the appropriate letters and check the possiblities against a a database of age appropriate words.
As always any assistance you can provide will be greatly appreciated by me and my daughter.