• Advertisement

Archived

This topic is now archived and is closed to further replies.

Word Search

This topic is 5491 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey all, I am working on a C++ program that solves word search puzzles. I have a good portion of it running correctly now but I am having problems with one part (so far). The program searches through a grid of letters and once it finds the first letter of the first word in the list it calls a recursive function to find the rest of the word and then display the coordinates of the word. It all works out when the first letter of the first word is found in the grid when it is the first one in the grid. puzzle: OPHRTKG HATBLUZ OSOUDEB UTMLRST SAOLOOA EGJOWDJ TROWNPL word list: hat see how there is an H in the puzzle (row 0 col 2) before the H containing the word hat (row 1, col 0), I can not figure out how to make it continue on to the next letter and display the coordinates of the word. for my output now i get row 0, col 2 to row 0, col 2. here is the code i have:
  #include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;

const int BOARD_SIZE = 7;

void welcome_message();
void get_board(char puzzle_board[BOARD_SIZE][BOARD_SIZE]);
void search_grid(char word[8], char puzzle_board[BOARD_SIZE][BOARD_SIZE]);
void recursive_word_finder(char puzzle_board[BOARD_SIZE][BOARD_SIZE],int &row, int &col, char word[], int &space);

void main()
{
	char puzzle_board[BOARD_SIZE][BOARD_SIZE];
	welcome_message();
	get_board(puzzle_board);
}

void welcome_message()
{
	cout << "Welcome to the word puzzle solver." << endl;
	cout << "Here is the solustion for today''s puzzle:\n\n";
}

void get_board(char puzzle_board[BOARD_SIZE][BOARD_SIZE])
{
	
	int row;
	int col;
	char letter;
	int per_line = 0;
	char word[8];
	ifstream input_file;
	
	cout << "   0 1 2 3 4 5 6" << endl;
	cout << "   -------------";
	
	input_file.open("puzzle.txt");
	for (row = 0; row < BOARD_SIZE; row++)
	{
		for (col = 0; col < BOARD_SIZE; col++)
		{
			input_file >> letter;
			while (letter == ''/n'')
				input_file >> letter;
			puzzle_board[row][col] = letter;
			if (col%7 == 0)
				cout << endl;
			if (col == 0)
				cout << row << "|";
			cout << setw(2) << puzzle_board[row][col];
		}
	}
	cout << endl << endl;

	cout << "WORD\tSTART\tEND" << endl;
	cout << "---------------------";

	input_file >> word ;
	while (!input_file.eof())
	{
		cout << endl;
		cout << word;
		search_grid(word, puzzle_board);
		input_file >> word;
	}
	cout << endl << endl;
}	
	
void search_grid(char word[8], char puzzle_board[BOARD_SIZE][BOARD_SIZE])
{
	int row = 0;
	int col = 0;
	int space = 0;
	do
	{
		if (word[space] == puzzle_board[row][col])
		{
			cout << "\t" << col << "," << row;
			recursive_word_finder(puzzle_board,row, col, word, space);
			cout << "\t" << col << "," << row;
			return;
		}
		
		else
		{
			col++;
			if (col > 6)
			{
				row++;
				col = 0;
			}

		}
	}while (row != 7);
}

void recursive_word_finder(char puzzle_board[BOARD_SIZE][BOARD_SIZE],int &row, int &col, char word[], int &space)
{
	space++;
	//check to the right

	if (puzzle_board[row][col+1] == word[space])
	{
		
		col++;
		recursive_word_finder(puzzle_board,row, col, word, space);
	}

	//check down

	if (puzzle_board[row-1][col] == word[space])
	{
		
		row--;
		recursive_word_finder(puzzle_board,row, col, word, space);
	}

	//check left

	if (puzzle_board[row][col-1] == word[space])
	{
		
		col--;
		recursive_word_finder(puzzle_board,row, col, word, space);
	}

	//check up

	if (puzzle_board[row+1][col] == word[space])
	{
		
		row++;
		recursive_word_finder(puzzle_board,row, col, word, space);
	}
}	
  

Share this post


Link to post
Share on other sites
Advertisement
by the way: i know i still have to work on the diangonal words. I just want to get the 4 main directions working first then move to the diangonals

Share this post


Link to post
Share on other sites
The simplest solution I can think of would be for recursive_word_finder to return a bool value. Return true if a matching letter was found, return false if it can''t find a matching letter. If the outermost recursive_word_finder call returns false, just keep moving along your main loop.

Share this post


Link to post
Share on other sites
Oh yeah, and don''t use references to row and col in the recursive function. I think the way you have it structured, it will mess up if you have to find more than one word cause the row and col variables will be out of whack when the recursive_word_finder finishes. I think it would work if you just let recursive_word_finder operate on its own local copies of col and row.

Share this post


Link to post
Share on other sites
Another thing: the word finder doesn''t look very robust. What happens when you access puzzle_board[row-1][col] and row==0? Reading outside the bounds of an array is bad.

Share this post


Link to post
Share on other sites
boy,

you are just chalk full of good points. I was meaning to add some sort of if statement to each one so that it wouldnt check anything out of the array.

Also I kind of understand what you are saying about the having the function return a bool value to see if the word is found or not but not 100%. Like I guess I dont know where things would start up again if false was returned.

thnaks for your help so far

Share this post


Link to post
Share on other sites
i just encountered another problem too. is there a way to get the function to know what direction the word is going after it finds the next letter? Because one of the words in the puzzle (bots) from the point of the t there is the letter s above it and diangonaly down. and since the check for up is first it uses that coordiante.

Share this post


Link to post
Share on other sites
here is what the puzzle.txt file looks like (i dont know if this will help any)


O P H R T K G
H A T B L U Z
O S O U D E B
U T M L R S T
S A O L O O A
E G J O W D J
T R O W N P L

HAT
HOUSE
GOLD
BULL
PAST
DROWN
MOJO
LOW
TAG
BOTS

Share this post


Link to post
Share on other sites
The true/false thing won''t work the way you have it designed.

You really need to re-think your design from the beginning. The way you have it, the function follows through with the first instance of the correct letter it finds, and if that letter doesn''t lead to the complete word, the function messes up.

What you need is a function that recurses until it reaches the end of the word (in which case it passes back the current x, y coords), or it reaches a "dead end". If it reaches a dead end, it should return something that indicates that it failed (false) and unwind the recursion one level. The function that called it should then pick up where it left off, now knowing that a certain direction, though it has the correct letter, is invalid because it doesn''t have the whole word.

I think you can do that if you think it through completely.

Share this post


Link to post
Share on other sites
do you think i need to scrap pretty much everything i have and start over, or will some of what i have still be useful? this recursion stuff is somewhat confusing to me.

Share this post


Link to post
Share on other sites
Your code is almost there. You just need to add a way to check whether or not the word is complete, and if it's not, to go back to where you were before.

The problem is, your current code terminates when there are no more "correct" letters available. This should only happen when there IS no such word in the grid. You need to make the function terminate when space == the length of the word. Get it?

[edited by - micepick on February 9, 2003 9:23:26 PM]

Share this post


Link to post
Share on other sites
The problem is merely a basic 2D string search algorithm:

"I want to check Letter[X][Y] in my array and check if a particular word starts on that letter. Return TRUE if so, else FALSE." This is just a strcmp() with delusions of grandeur and recursion is really overkill for such a task. It's like trying to shell peas using an Exocet missile.

I'd go for a master "WordFound()" function that takes:

1. The search string,
2. The starting coordinate in the grid,
3. a 'direction' parameter (I suggest using deltas).

E.g. "WordFound(string, x, y, dx, dy)".

For NE, dx and dy would both be set to 1. For E, dx would be set to 1, dy to zero. For SE, dx would be 1 and dy -1. And so on around the compass.

All the function does is loop through each character in the string, checking if the current character in the string matches the character in the grid. If there's a match, increment x and y by dx and dy respectively and check the next character, and so on. Return FALSE if you get a mismatch or go out of bounds; return TRUE if you reach the end of the loop without hitting a mismatch.

(Recursion can still be used if you must.)


--
Sean Timarco Baggaley


[edited by - stimarco on February 9, 2003 9:43:06 PM]

Share this post


Link to post
Share on other sites
micepick,

i understand what you are telling me. now i just have to figure it all out and put it into code form which is going to be the tough part.

so i make recursive_word_finder a bool function.

inside the function do a string length or the word? (so the function knows when it has found the whole word and knows when to stop?)

when space == word it is done. when space != word it has to keep going.


  
int length = strlen(word) ;
space++;

//check to the right

if (col < 7)
{
if (puzzle_board[row][col+1] == word[space])
{
col++;
recursive_word_finder(puzzle_board,row, col, word, space);
return 0;
}

if (length == space)
return 1;
}


something is wrong with that code but im not really sure what. i figure if i can get the code for one of the checks, the rest will be similar


Share this post


Link to post
Share on other sites
For one thing, if the call to recursive_word_finder returns one, the current function should also immediately break and return one.

Share this post


Link to post
Share on other sites
why not write a small search function for each direction, then in a main wordsearch function you call each of them and whichever returns true you have your direction. if none return true then you haven''t found anything. That is how I would approach it.

Share this post


Link to post
Share on other sites
Here is some code I wrote.. I can't guarantee it will work. for diagonals, its just a variation on the other check_ functions...


      
bool check_left_to_right( char *word, int row, int col )
{
char buffer[10];
int i;
int ilenght = strlen(word);

if ( (ilength + col) > 7 )
return FALSE;

buffer[0] = '\0';
for( i = 0; i<ilength; i++ )
buffer[i] = puzzle_board[row][col+i];
buffer[i] = '\0';
if ( !strcmp( word, buffer ) )
return TRUE;

return FALSE;
}

bool check_right_to_left( char *word, int row, int col )
{
char buffer[10];
int i;
int ilenght = strlen(word);

if ( (col - ilength) < 0 )
return FALSE;

buffer[0] = '\0';
for( i = 0; i<ilength; i++ )
buffer[i] = puzzle_board[row][(col-ilength)+i];
buffer[i] = '\0';
if ( !strcmp( word, buffer ) )
return TRUE;

return FALSE;
}

bool check_top_to_bottom( char *word, int row, int col )
{
char buffer[10];
int i;
int ilenght = strlen(word);

if ( (row + ilength) > 7 )
return FALSE;

buffer[0] = '\0';
for( i = 0; i<ilength; i++ )
buffer[i] = puzzle_board[row+i][col];
buffer[i] = '\0';
if ( !strcmp( word, buffer ) )
return TRUE;

return FALSE;
}

bool check_bottom_to_top( char *word, int row, int col )
{
char buffer[10];
int i;
int ilenght = strlen(word);

if ( (row - ilength) < 0 )
return FALSE;

buffer[0] = '\0';
for( i = 0; i<ilength; i++ )
buffer[i] = puzzle_board[(row - ilength)+i][col];
buffer[i] = '\0';
if ( !strcmp( word, buffer ) )
return TRUE;

return FALSE;
}


POINT *find_word_location( char *word, int direction )
{
int row, col;
bool found = FALSE;
static POINT pt;

for ( row = 0; row < 7; row++ )
{
for ( col = 0; col < 7; col++ )
{
if ( puzzle_board[row][col] == word[0] )
{
if ( direction == DIR_R2L && check_right_to_left( word, row, col ) )
found = TRUE;
else
if ( direction == DIR_L2R && check_left_to_right( word, row, col ) )
found = TRUE;
else
if ( direction == DIR_T2B && check_top_to_bottom( word, row, col ) )
found = TRUE;
else
if ( direction == DIR_B2T && check_bottom_to_top( word, row, col ) )
found = TRUE;

if ( found )
{
pt.x = row;
pt.y = col;
return &pt;
}
}
}
}

return NULL;
}


void main_loop()
{
//load the puzzle and words to search for

...
//loop through the words and direction

for ( iword = 0; iword < number_of_words; iword++ )
{
for ( direction = 0; direction < 4; direction++ )
{
board_location = find_word_direction( word_table[iword], direction );
if ( board_location != NULL )
{
// do something with the board location and direction and word

}
}
}
}


Hope that helps... yes, I was bored

edit: messed up the tags

[edited by - evillive2 on February 10, 2003 3:44:27 AM]

Share this post


Link to post
Share on other sites
This is how I would test a word:


    
bool check_word(const std::vector<std::vector<char> > &grid, int width, int height, int x, int y, int direction, const char *word)
{
// direction is 0-7, 0 being right, and 0+ turning in a clockwise direction.

static const int dirx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
static const int diry[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int len = std::strlen(word);


if(x < 0 || y < 0 || x >= width || y >= height || // check if starting point is outside of grid

x+dirx[direction]*len < 0 || y+diry[direction]*len < 0 || // check if ending point is outside of grid

x+dirx[direction]*len >= width || y+diry[direction]*len >= height)
return false;

// Check if the letters in the grid match the word.

for(int p = 0; p < len; ++p)
if(grid[x+dirx[direction]*p][y+diry[direction]*p] != word[p])
return false;

// Everything is okay.

return true;
}


[edited by - smart_idiot on February 10, 2003 4:15:31 AM]

Share this post


Link to post
Share on other sites

  • Advertisement