Assignment 12

due at 6pm on Wed 14 Dec

The goal of this assignment is to build a word-search puzzle by placing a list of words on a grid. To obscure the words, we then fill in the remaining blank spaces with random letters. Your program should print the solution (exposed words), followed by the complete puzzle, as below. The layout of words is random, so the puzzle should look different every time you run it.

      SOLUTION:

    .......string.t..........g....
    eo...boolean..r.n.h......r..p.
    lr.float......e.e.ec...m.a..o.
    edregister....e.t.ah...o.p.ji.
    mi.............lw.da...d.h.an.
    enqueue.integeroo.er...u.i.vt.
    na....kindle...nr.r....l.c.ae.
    tldouble.......gk......e.s..r.
    ...........array..............

      PUZZLE:

    VASWQRISTRINGMTMWHTAMNOATGWEDW
    EOKYWBOOLEANNSRUNTHKQOKKMRDBPU
    LRPFLOATOQYJSKEYEGECNTFMRAWBOB
    EDREGISTERXZQPEWTJAHBMZOMPXJIL
    MIRYHIOYHZSTYZGLWRDAGXODJHAANN
    ENQUEUEIINTEGEROOSERCGDUEITVTC
    NASQNJKINDLEQXRNRFRVAGPLUCEAEQ
    TLDOUBLECWWCMHEGKZSXDYAEHSRFRB
    JUMARGHMGNEARRAYCUUFSRHEALFSKI

You can approach this however you want, however below I’ll give you a sense of how I’d approach it. You can take this and fill in the gaps with your own code.

Global declarations

We’ll need the following libraries included, for I/O, randomness, and string and character operations:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <ctype.h>

Use constants for the size of the grid:

const int ROWS = 9;
const int COLS = 30;

The character that represents an unused space in the grid should be a period:

const char BLANK = '.';

Words can go either across or down. It’s useful to represent those two possibilities as constants, but underlying that it’s just a boolean (because there are exactly two possibilities).

const bool ACROSS = true;
const bool DOWN = false;

Function prototypes

We’ll put these at the top of the program, so we can refer to them in main, but we’ll get to the definitions of them later on in this document.

void initialize_grid(char grid[ROWS][COLS]);
void print_grid(char grid[ROWS][COLS]);
void fill_blanks(char grid[ROWS][COLS]);

bool does_word_fit(const char* word, char grid[ROWS][COLS],
                   int i, int j, bool direction);

void place_word(const char* word, char grid[ROWS][COLS],
                int i, int j, bool direction);

void random_direction_and_position(const char* word, int& i, int& j,
                                   bool& direction);

void place_word_randomly(const char* word, char grid[ROWS][COLS]);

Main program

Here is the main program that I recommend you use.

int main()
{
    const int NUM_WORDS = 20;
    const char* wordList[NUM_WORDS] = {
        "array", "boolean", "char", "double",
        "element", "float", "graphics", "header",
        "integer", "java", "kindle", "long",
        "module", "network", "ordinal", "pointer",
        "queue", "register", "string", "tree"
    };
    srand(time(NULL));
    char grid[ROWS][COLS];

    initialize_grid(grid);
    for(int i = 0; i < NUM_WORDS; i++)
    {
        place_word_randomly(wordList[i], grid);
    }
    printf("\n  SOLUTION:\n\n");
    print_grid(grid);
    fill_blanks(grid);
    printf("\n  PUZZLE:\n\n");
    print_grid(grid);
    return 0;
}

Let’s break that down. Look for the following elements of the algorithm:

• Declare a list of 20 words to place on the puzzle.
• Initialize the random number generator.
• Declare a grid of ROWS × COLS.
• Initialize the grid, placing BLANK characters in every cell.
• For each word, place that word randomly on the grid.
• Print out the current grid as the solution.
• Fill in the blank characters with random characters.
• Print out the current grid as the puzzle.

The ‘easy’ functions

These are pretty similar to lots of past examples we have using two-dimensional arrays.

initialize_grid(grid) should put the BLANK character into every cell. You’ll have to use nested loops to visit every cell of the grid.

print_grid(grid) should output the grid onto the screen using printf("%c", grid[i][j]). This of course also requires nested loops, and printing a newline in the right place.

fill_blanks(grid) should go through the entire grid, and any cell that remains BLANK should be replaced with a random letter. To generate a random letter, generate a number from 0 to 25, and then add it to the character 'a'. ('a'+0 produces just 'a', and 'a'+25 will produce 'z').

The ‘slightly tricky’ functions

TODO: more info on these

bool does_word_fit(const char* word, char grid[ROWS][COLS],
                   int i, int j, bool direction);

void place_word(const char* word, char grid[ROWS][COLS],
                int i, int j, bool direction);

void random_direction_and_position(const char* word, int& i, int& j,
                                   bool& direction);

Putting it all together

The final piece of the puzzle is place_word_randomly, which loops until it finds a suitable place for the current word. It uses the three ‘tricky’ functions from the previous section.

void place_word_randomly(const char* word, char grid[ROWS][COLS])
{
    int i, j;
    bool direction;
    do {
        random_direction_and_position(word, i, j, direction);
    } while(!does_word_fit(word, grid, i, j, direction));
    place_word(word, grid, i, j, direction);
}