Need recursion??

[whitenite1]

Most of the time, this function (below) works to find a word in a Boggle type grid. The times it doesn't, is when the same letter from the searched word, is located more than once in the search, and the searched word isn't found following a false, dead-end, letter search.
How can I search each of the directions, until a match is found, then exit function, or all directions were searched and no match was found?

bool Check_Word(char grid[10][10], string Search_Word, int z, int j)
{
	int Ck_Grid[10][10]={{0},{0}};
	bool Found = false;
	int go=1;
	int zz = z, jj = j;
	int len = Search_Word.length();
	for (int x = 1;x < len; x++)
	{
		if(grid[zz-1][jj] == Search_Word[x] && Ck_Grid[zz-1][jj] == 0)
		{
			Ck_Grid[zz-1][jj] = 1;
			go++;
			zz--;
		}
		if(grid[zz+1][jj] == Search_Word[x] && Ck_Grid[zz+1][jj] == 0)
		{
			Ck_Grid[zz+1][jj] = 1;
			go++;
			zz++;
		}
		if(grid[zz][jj-1] == Search_Word[x] && Ck_Grid[zz][jj-1] == 0)
		{
			Ck_Grid[zz][jj-1] = 1;
			go++;
			jj--;
		}
		if(grid[zz][jj+1] == Search_Word[x] && Ck_Grid[zz][jj+1] == 0)
		{
			Ck_Grid[zz][jj+1] = 1;
			go++;
			jj++;
		}
		if(grid[zz-1][jj-1] == Search_Word[x] && Ck_Grid[zz-1][jj-1] == 0)
		{
			Ck_Grid[zz-1][jj-1] = 1;
			go++;
			zz--;
			jj--;
		}
		if(grid[zz+1][jj+1] == Search_Word[x] && Ck_Grid[zz+1][jj+1] == 0)
		{
			Ck_Grid[zz+1][jj+1] = 1;
			go++;
			zz++;
			jj++;
		}
		if(grid[zz+1][jj-1] == Search_Word[x] && Ck_Grid[zz+1][jj-1] == 0)
		{
			Ck_Grid[zz+1][jj-1] = 1;
			go++;
			zz++;
			jj--;
		}
		if(grid[zz-1][jj+1] == Search_Word[x] && Ck_Grid[zz-1][jj+1] == 0)
		{
			Ck_Grid[zz-1][jj+1] = 1;
			go++;
			zz--;
			jj++;
		}
	}
	if(go==len)
		Found = true;

	return Found;
}

example:

S L D M
V C L O
J O O B
N M A C

(This program is being written with user urfa2 criteria, in a letter search can be diagonal)
If the searched for word is 'MOOD', then I could get a false result since the search may stop after 'MOOB', 'MOLD', 'MOOJ, etc. I'm not sure how to check if there is more than one word path, after finding a false word. Any ideas??

[jonnin]

recursion would do it. Its like a maze traversal but you can't stop short and have to check all paths.
how would your code know that 1) Moodinesses is a word and 2) it can stop after mood+1 because there are no more words possible from any of the mood+1 letter combos.. ?

this is why I said its probably (easier to code and possibly more efficient as well) to check all the possible words from all your letters (ignoring their position) and then check each word from that list to see if it can actually be made on the board. The other way around is harder, you spend a lot of time checking whether MNJ or MNOL are words and trying to keep track of what paths you have used.

[dhayden]

That sequence of if's should be an if/else ladder. Otherwise with input word "mood" you could wander around several o's in one iteration of the loop. You could also shorten the code by creating a table x,y increments and going through them in a loop.

[whitenite1]

@jonnin

I'm using the following code. I check the letter at each location in the Boggle grid. If the location equals the first letter of the search word, the I call Check_Word function, with the location of the found letter, z and j, as the starting point. I use int len to find the length of Search_Word, and increase variable go in Check_Word as each successive letter is found. If the next letter is found, I increase zz, and/or jj to show where I am in the grid. (In OP)
When/If I find the complete word in the grid, I check my dictionary to see if the word is in it. I have it to matter of a few seconds to find the word, or not. I am interested on how I can make the Check_Word function into a recursive function so it can check other letters that are the same in the grid as ones that don't pan out.

for (z = 0; z < y; z++)
		{
			for (j=0; j < x; j++)
			{
				if( grid [z][j] == Search_Word[0])
				{
					In_Grid = Check_Word(grid, Search_Word, z, j);
				}
				if(In_Grid)
				{
					j = x;
					z = y;
				}
			}
		}

@dhayden
I did as you suggested, and added else in the if ladder. Thanks for the suggestion.

[dhayden]

When/If I find the complete word in the grid, I check my dictionary to see if the word is in it.

It would probably be faster to check if the word is in the dictionary first.

Here is code that recursively checks for a list of words

#include <iostream>
#include <string>

using std::string;
using std::cin;
using std::cout;

constexpr unsigned GRIDSIZE=4;

bool checkWord(const char grid[GRIDSIZE][GRIDSIZE],
	       const char *searchWord,
	       unsigned x, unsigned y  /* starting position */ )
{
    if (*searchWord == 0) {
	return true;		// found it
    }

    if (x<0 || y<0 || x >= GRIDSIZE || y >= GRIDSIZE) {
	return false;		// x,y out of bounds
    }

    if (grid[x][y] != *searchWord) {
	return false;		// this character doesn't match
    }
    
    // Now recursively look for the rest of the word in the neighbors
    for (int i = -1; i<2; ++i) {
	for (int j = -1; j<2; ++j) {
	    if (i==0 && j==0) continue;
	    if (checkWord(grid, searchWord+1, x+i, y+j)) {
		return true;
	    }
	}
    }
    return false;
}

int main()
{
    char grid[GRIDSIZE][GRIDSIZE];

    // Read the grid
    for (auto &row : grid) {
	for (char &ch : row) {
	    cin >> ch;
	}
    }
    
    // Now read words and find them
    string word;
    while (cin >> word) {
	bool found = false;
	for (unsigned i=0; i<GRIDSIZE && !found; ++i) {
	    for (unsigned j=0; j<GRIDSIZE && !found; ++j) {
		if (checkWord(grid, word.c_str(), i,j)) {
		    cout << word << " starts at row " << i+1
			 << " col " << j+1 << '\n';
		    found = true;
		}
	    }
	}
	if (!found) {
	    cout << word << " not found\n";
	}
    }
}

Input:

SLDM
VCLO
JOOB
NMAC
MOOD
MOLD
BOA
VAN

Output:

MOOD starts at row 4 col 2
MOLD starts at row 1 col 4
BOA starts at row 3 col 4
VAN not found

[whitenite1]

@dhayden

It would probably be faster to check if the word is in the dictionary first.

You're right. It would be. I'll change around my code to then first check it, then check the grid.

Also, thanks for a way to do the recursion. I'll incorporate that into my Check_Word() function.