Word Search -- Recursively

[tofugirl]

Ahhh! It is the return of the Word Search!!! However, any ideas on how to do it recursively?

for instance:

n t o f u g i r l
h n d d c s e r c
e e b d u c s f e
l f e w e t s e e
p e s e w s e e e
e w w s b o o p f
f s j i w y b s e

Words to find:
tofugirl
help

Answers:
tofugirl is located at column 2, row 1 - direction is right
help is located at column 1, row 1 - direction is down

Sorry for the alignment of the puzzle. I just made it up -- supposedly a 9 x 9 matrix.

I made it up as a 12 x 12 matrix to account for the null, and to take out the 0 rows & 0 columns (this doesn't happen in real life).

Account that words show up across (left to right or right to left), and down (left to right or right to left). no diagonals! (thank goodness!)

I have something using strstr and using as it != NULL as a base case... but I cannot figure out how to get rid of the traditional
for ( i = 0; i < rows; i++)
for(j = 0; j < columns; j++)
........ etc........

and make it recursive!

Any ideas??? Any code snippet would be much appreciated...

I have an idea there needs to be 4 functions to check for words - Across, Down, Backwards Across, and Backwards Down.

Any input?

[sloopy]

wouldn't it be 16 functions, or 16 checks?

[quzah]

One function, four checks. I'm not sure how you're getting sixteen.

for each element in the array, with optional pruning for current XY
coordinates to EOL subtraction for length of the word to find
    if this letter is the first letter in the word
        function( x, y, north )
        function( x, y, east )
        function( x, y, south )
        function( x, y, west )

Optionally you can add a few more parameters, such as what word you're looking for, and what letter you're on, etc etc. You don't ever need to check more than the direction you're heading, once you've started on a word, because you don't have words that zig-zag all over, so just keep heading in the same direction until you run out of word, have a full word found, or run out of maze...er...word-search.


Quzah.

[SlyMaelstrom]

I think he's also assuming the diagonals. Which would be 8, though.

Maybe he was thinking backwards would be another 8.

[quzah]

Account that words show up across (left to right or right to left), and down (left to right or right to left). no diagonals! (thank goodness!)

Also, no, there still wouldn't be sixteen. At the most you're ever going to have is 8. Look at your numberpad. The letter you're searching from as a starting point is the 5. That leaves only ever 8 directions to search. Not sixteen.

Quzah.

[SlyMaelstrom]

Well, I know there wouldn't be 16. ...but good catch on the "no diagonals" quote. You got me there.

[quzah]

Well, I know there wouldn't be 16.

Don't feel bad. I myself often catch myself trying to unravel the thought process of posters. "How in the hell did they come up with that?" More often than not, it just leads to a head-ache, so I try to catch myself in time...


Quzah.

[SlyMaelstrom]

I'm not gonna get into this arguement of what I meant.

I'll let you have it since you, after all, are more experienced here.

[quzah]

I took it to mean: "I, of the dancing milk clan, know there aren't 16, but I think sloopy was thinking ..." *shrugs*

No worries. Oh, and to pull this back on track:

You could make your recursive function return 1 + the other recursive calls, and 0 on failure. If the total returned equals the length of the word you're looking for, you've got a match.

if( length_of_word_to_find == myfun( ... , heading ) )
{
    printf("Word %s found at %dX,%dY, heading %s!",
        word, x, y, wordofheading( heading ) );
}

Or something akin to that.


Quzah.

[tofugirl]

No worries. Oh, and to pull this back on track:

You could make your recursive function return 1 + the other recursive calls, and 0 on failure. If the total returned equals the length of the word you're looking for, you've got a match.
Code:

if( length_of_word_to_find == myfun( ... , heading ) )
{
    printf("Word %s found at %dX,%dY, heading %s!",
        word, x, y, wordofheading( heading ) );
}Or something akin to that.

Thanks Quzah. I'll try your suggestion. Would this be used as as a base case in the recursive function? Hopefully I won't produce some infinite recursion......

Any other ideas also appreciated!