Word Search Generator in C++
Final Project for 'Survey of Programming Languages'
/ 7 min read
The Assignment
The only requirement was that we had to make a puzzle. It was a group project so we split the project up into two pieces: generator and solver. My partner @michaelvessia called dibs on the solver so I guess that meant I was stuck building the generator. The code for generator can be found here.
Design
- the puzzle will be a 10x10 square
- each tile is an uppercase alphabetic character
Rules
- words generated must be at least two characters and no more than
(GRID_SIZE - 1)characters - maximum of
(GRID_SIZE - 3)words per puzzle
Thought Process
When I hear the words “Word Search” the programmer part of my brain instantly shouts out “Multi-dimensional character array!“. This is because that’s all a word search is. Rows and columns filled with letters. Simple.
char grid[GRID_SIZE][GRID_SIZE];Ok, so we have our grid. The next question I asked myself was how can I populate this grid with words from our input. Soon after, a simple flowchart appeared before me:
Functions
void ReadFile(char* filename);
Now, let’s read in our list of words so we know what we’re working with!
ifstream wordsFile(filename);
string word;
int line = 0;
if(wordsFile.is_open()){
printf("Reading file '%s'\n",filename);
while(getline(wordsFile,word)){
words[line] = word;
line++;
if(line == 8){
throw "Words list can not have more than 7 words";
}
if(word.length() < 2 || word.length() > GRID_SIZE-1){
throw "Words must be at least two characters and no more than the grid size";
}
}
}
else{
throw "Cannot open words list file";
}void ClearGrid();
Let’s clear the grid. This makes it so the cells are initialized, allocated, and able to be manipulated. In my code a define a null character that is used to show that a space on the grid is not part of the actual puzzle.
NULL_CHAR = 'x'; //Sets the null char to a lowercase xI set it to be a lowercase letter because the puzzle will only insert uppercase letters, so no issues will arise. So let’s clear the grid and get it ready for action, shall we?
for(int i=0;i<GRID_SIZE;i++){
for(int k=0;k<GRID_SIZE;k++){
grid[i][k] = NULL_CHAR; //Every empty value will be a lowercase x
}
}bool CanInsert(const char* word, point start, direction d);
This is a function that checks if the given word can be inserted into the grid. You may notice two types called direction and point. Direction is just what you think it is, all the possible directions a word can face. It is defined as such:
enum direction{
UP,
DOWN,
LEFT,
RIGHT,
UP_LEFT,
UP_RIGHT,
DOWN_LEFT,
DOWN_RIGHT
};Point is also would you would think it is. A type that represents a point on the grid.
struct point{int i,k;}; //Declare a point structure that represents a point on the gridint i = 0;
point newPoint = start;
while(i < (int)strlen(word)) //Iterates through the word char array
{
//Attempt to shift the point
try{
if(grid[newPoint.i][newPoint.k] == NULL_CHAR){
newPoint = ShiftPoint(newPoint,d);
i++;
}
else{
return false;
}
}
catch(const char* msg) //Returns false if the out of bounds error occurs
{
return false;
}
}
return true;What have here is a loop that goes through each character in the given word. Within that loop an if-statement checks whether or not the current point is occupied by seeing if the value is equal to the NULL_CHAR we defined before. If the point is null, shift the point in the direction specified and repeat the check until there are no more characters left in the word. If the loop finishes with no problems, return true; the word can indeed be inserted.
This function calls a function called ShiftPoint which takes in a point and a direction and returns a point at the new location.
point ShiftPoint(point start, direction d);
int i = start.i;
int k = start.k;
point newPoint;
switch(d){
case UP:
newPoint.i = i-1; //Move up a row
newPoint.k = k; //Column stays the same
break;
case DOWN:
newPoint.i = i+1; //Move down a row
newPoint.k = k; //Column stays the same
break;
case LEFT:
newPoint.i = i; //Row stays the same
newPoint.k = k-1; //Column moves left
break;
case RIGHT:
newPoint.i = i; //Row stays the same
newPoint.k = k+1; //Column moves right
break;
case UP_LEFT:
newPoint.i = i-1; //Row moves up
newPoint.k = k-1; //Column moves left
break;
case UP_RIGHT:
newPoint.i = i-1; //Row moves up
newPoint.k = k+1; //Column moves right
break;
case DOWN_LEFT:
newPoint.i = i+1; //Row moves down
newPoint.k = k-1; //Column moves to left
break;
case DOWN_RIGHT:
newPoint.i = i+1; //Row moves down
newPoint.k = k+1; //Column moves right
break;
default:
newPoint.i = i; //Row stays the same
newPoint.k = k; //Column stays the same
break;
}
//Handle out of bounds errors
if(newPoint.i < -1 || newPoint.i > GRID_SIZE || newPoint.k < -1 || newPoint.k > GRID_SIZE)
{
throw "Out of Bounds";
}
return newPoint;void InsertWord(const char* word)
This function is the meat of the program. This is the function that actually inserts the words into the puzzle at a random location in a random direction.
point start;
direction d;
do{
start.i = rand() % GRID_SIZE; //set to a random row
start.k = rand() % GRID_SIZE; //set to a random column
d = direction(rand() % 8); //get a random direction
}
while(!CanInsert(word,start,d));
int i = 0;
point newPoint = start;
while(i < (int)strlen(word))
{
grid[newPoint.i][newPoint.k] = (char)toupper(word[i]);
newPoint = ShiftPoint(newPoint,d);
i++;
}The do-while loop in the very beginning, I admit, seems kind of hack-y. But hey, it works. The do part generates a random row, a random column, and a random direction. It is then checked against the while condition that says to break once the word can be inserted. Probably not the best, or most efficient way to do this, but it is what it is. Still got a 💯.
The next while loop just iterates through the given word and inserts each character into the randomly generated start position, facing the randomly generated direction making sure to convert each character to an uppercase letter using toupper().
I created a seperate function to insert all the words from the given file. It’s cleverly named
void InsertWordsFromFile()
//Iterate through all of the indexes in the array and insert them into the grid
for(int i=0;i<(int)(sizeof(words)/sizeof(words[0]));i++){
string word = words[i];
InsertWord(word.c_str()); //Convert the word (std::string) into a useable char* array
}This function is pretty self explanatory. It loops through all of the words foudn in the file we read in before in a for-loop and calls InsertWord for each word.
Great! So now we have our words inserted into the puzzle. All that is left is to fill the remaining NULL_CHARs with a random uppercase character to confuse the hell out of the solver.
void FillGrid()
For this function we’re going to have to have a way to generate a random character. A very simple and cool way to do this is to create a function that returns 'A' + rand()%26;. Nifty eh?
for(int i=0;i<GRID_SIZE;i++){
for(int k=0;k<GRID_SIZE;k++){
if(grid[i][k] == NULL_CHAR){
grid[i][k] = GenerateRandomChar(); //Set every null value to a random character
}
}
}Honestly that’s pretty much it. All there is left to do is print the grid to a file.
void PuzzleToFile(char* filename);
ofstream output(filename);
char c;
if(output.is_open()){
printf("Writing to file '%s'\n",filename);
for(int i=0;i<GRID_SIZE;i++){
for(int k=0;k<GRID_SIZE;k++){
if(k == GRID_SIZE-1){
c = grid[i][k];
output.put(c);
output.put('\n'); //Append a newline if it is on the last column
}
else{
c = grid[i][k];
output.put(c);
}
}}
}
else{
throw "Cannot create output file";
}There we go, ladies and gentlemen. A word search generator written in C++. Let me know what you think.