Public Group

#### Archived

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

# Word Search

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

## 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 on other sites
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 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 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 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 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 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 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 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 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.

• 22
• 10
• 19
• 14
• 20