Check if word exists in the matrix of random characters in C

Question

I'm currently working in creating a word search/boggle game in C language. On which a player will input a word and the program will check if the inputted word is existing in the 2D matrix of random characters. I'm having difficulty in C language. Can someone help if I'm doing right? Or I need to change my codes. Help is much appreciated.

So here is my entire code. When I try to guess it always printing Not Found even though the word is the 2D matrix of random char. So, I need help with what is wrong? And what is the correct code to check if the word is existing?

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

#define SIZE 6 
#define MAX 10

typedef enum { true, false } bool;

// Draw the board with random characters
void board(char matrix[SIZE][SIZE]) {
    int i, j;
    for (i = 0; i < SIZE; i++) {
        for (j = 0; j < SIZE; j++) {
            matrix[i][j] = 'A' + rand() % ('Z' - 'A' + 1);
        }
    }
}

// Prints the board
void printBoard(char matrix[SIZE][SIZE]) {
    int i, j;
    srand((unsigned int)time(NULL));
    board(matrix);

    for (i = 0; i < SIZE; i++) {
        for (j = 0; j < SIZE; j++) {
            printf(" %c ", matrix[i][j]);
        }
        printf("\n");       
    }
}

bool adjacentSearch(char matrix[SIZE][SIZE], char *find, int i, int j, int index) {
    if (index == strlen(find))
        return true;

    if (i < 0 || j < 0 || i > SIZE - 1 || j > strlen(matrix[0]) - 1) {
        return true;
    }

    if (matrix[i][j] != find[index]) {
        return false;
    }

    matrix[i][j] = '*';

    bool searchFurther = adjacentSearch(matrix, find, i + 1, j, index + 1) ||
                         adjacentSearch(matrix, find, i - 1, j, index + 1) ||
                         adjacentSearch(matrix, find, i, j - 1, index + 1) ||
                         adjacentSearch(matrix, find, i, j + 1, index + 1);

    matrix[i][j] = find[index];
    return searchFurther;
}

bool exist(char matrix[SIZE][SIZE], char *find, int r, int c) {
    int len = strlen(find);

    if (len > r * c)
        return false;

    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < strlen(matrix[0]); j++) {
            if (matrix[i][j] == find[0]) {
                if (adjacentSearch(matrix, find, i, j, 0)) {
                    return true;
                }
            }
        }
    }
    return false;
}

// Driver 
int main() {
    char matrix[SIZE][SIZE];
    char word[MAX];

    printBoard(matrix);

    printf("\nThink of a word> ");
    fgets(word, MAX, stdin);
    //printf("word: %s", word);

    if (exist(matrix, word, SIZE, SIZE)) {
        printf("Found\n");
    } else {
        printf("Not Found\n");
    }
    return 0;
}

Answer 1

There are multiple problems in the code:

• the definition of true and false is incorrect: you should write:

  typedef enum { false, true } bool;
  

• you do not strip the trailing newline left in the buffer by fgets(). The program cannot find the word because the newline is not present in the matrix. Remove this character with:

  word[strcspn(word, "\n")] = '\0';
  

• the tests j > strlen(matrix[0]) - 1 are incorrect: you should just test if j >= SIZE to verify that the coordinates are inside the matrix.

• adjacentSearch() should return false when i or j are outside the matrix.

Here is a corrected version:

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

#define SIZE 6
#define MAX 40

typedef enum { false, true } bool;

// Draw the board with random characters
void board(char matrix[SIZE][SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            matrix[i][j] = 'A' + rand() % ('Z' - 'A' + 1);
        }
    }
}

// Prints the board
void printBoard(char matrix[SIZE][SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            printf(" %c ", matrix[i][j]);
        }
        printf("\n");
    }
}

bool adjacentSearch(char matrix[SIZE][SIZE], const char *find, int i, int j, int index) {
    if (find[index] == '\0')
        return true;

    if (i < 0 || j < 0 || i >= SIZE || j >= SIZE || matrix[i][j] != find[index])
        return false;

    matrix[i][j] = '*';
    bool found = (adjacentSearch(matrix, find, i + 1, j, index + 1) ||
                  adjacentSearch(matrix, find, i - 1, j, index + 1) ||
                  adjacentSearch(matrix, find, i, j - 1, index + 1) ||
                  adjacentSearch(matrix, find, i, j + 1, index + 1));
    matrix[i][j] = find[index];
    return found;
}

bool exist(char matrix[SIZE][SIZE], const char *find) {
    int len = strlen(find);
    if (len > SIZE * SIZE)
        return false;
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            if (adjacentSearch(matrix, find, i, j, 0)) {
                return true;
            }
        }
    }
    return false;
}

// Driver
int main() {
    char matrix[SIZE][SIZE], word[MAX];

    srand((unsigned int)time(NULL));
    board(matrix);
    printBoard(matrix);

    for (;;) {
        printf("\nThink of a word> ");
        if (!fgets(word, sizeof word, stdin))
            break;
        word[strcspn(word, "\n")] = '\0';
        if (exist(matrix, word)) {
            printf("Found\n");
        } else {
            printf("Not Found\n");
        }
    }
    return 0;
}

Answer 2

Array indexing problem. Check this code

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

#define SIZE 6
#define MAX 10

// typedef enum {true, false} bool;

// Draw the board with random characters
void board(char* matrix){
    int i, j;
    for(i=0; i<SIZE; i++){
            for(j=0; j<SIZE; j++){
                matrix[i*SIZE + j] = 'A'+(50 *i *j)%('Z'-'A'+1);
        }
    }
}

// Prints the board
void printBoard(char* matrix){
    int i, j;
    srand((unsigned int)time(NULL));
    board(matrix);

    for(i=0; i<SIZE; i++){
            for(j=0; j<SIZE; j++){
                    printf(" %c ", matrix[i*SIZE + j]);
            }
        printf("\n");
    }
}

enum class Direction : int
{
    Left = 0,
    Right,
    Up,
    Down,
    Unknown
};

bool SearchGivenStart(char* matrix,
char* find, int length,
int startRowIndex,
int startColumnIndex,
Direction direction)
{
     printf("Start %d %d\n", startRowIndex, startColumnIndex);
    int nextRowIndex = startRowIndex;
    int nextColumnIndex = startColumnIndex;
    for(int i = 1; i< length - 1 ;i++)
    {
        if(direction == Direction::Left)
        {
            nextColumnIndex -= 1;
        }
        else if (direction == Direction::Right)
        {
            nextColumnIndex += 1;
        }
        else if (direction == Direction::Up)
        {
            nextRowIndex -= 1;
        }
        else if (direction == Direction::Down)
        {
            nextRowIndex += 1;
        }
        else
        {
            // Assert error
        }

         printf("Next %d %d\n", nextRowIndex, nextColumnIndex);
        // Check bounds
        if(nextRowIndex  < 0 ||
        nextRowIndex > SIZE  ||
        nextColumnIndex  < 0 ||
        nextColumnIndex > SIZE )
        {
            printf("returning false out of bound\n");
            return false;
        }

        if (matrix [nextRowIndex * SIZE + nextColumnIndex] != find [i])
        {
            printf("returning false\n");
            return false;
        }

    }

    printf("returning true\n");
    return true;
}

bool Search(char* matrix, char* find, int length)
{
    // Find start
    // For each start candidate, serach all possible direction

    printf("%s %d\n", find, length);
    bool found = false;
    for (int i = 0; i < SIZE; i++)
    {
        for(int j= 0; j< SIZE; j++)
        {
            if ( matrix[i*SIZE + j] == find[0] )
                {
                    printf("%d %d\n", i, j);
                     found = SearchGivenStart(matrix,
                     find,
                     length,
                     i,
                     j,
                     Direction::Left);
                     if (found)
                        return true;

                     found = SearchGivenStart(matrix,
                     find,
                     length,
                     i,
                     j,
                     Direction::Right);
                     if (found)
                        return true;
                     found = SearchGivenStart(matrix,
                     find,
                     length,
                     i,
                     j,
                     Direction::Up);
                     if (found)
                        return true;
                     found = SearchGivenStart(matrix,
                     find,
                     length,
                     i,
                     j,
                     Direction::Down);
                     if (found)
                        return true;
                }
        }
    }
    return found;
}

bool adjacentSearch(char* matrix, char* find, int i, int j, int index){
    if(index == strlen(find))
        return true;

    if(i < 0 || j < 0 || i > SIZE-1 || j > SIZE - 1){
        return true;
    }

    if(matrix[i *SIZE + j] != find[index]){
        return false;
    }

    matrix[i*SIZE + j] = '*';

    bool searchFurther = adjacentSearch(matrix, find, i+1, j, index+1) || adjacentSearch(matrix, find, i-1, j, index+1) || adjacentSearch(matrix, find, i, j-1, index+1) || adjacentSearch(matrix, find, i, j+1, index+1);

    matrix[i * SIZE + j] = find[index];
    return searchFurther;
}

bool exist(char* matrix, char* find, int r, int c){
    int len = strlen(find);

    if(len > r * c)
        return false;

    for(int i=0; i<SIZE; i++){
        for(int j=0; j<SIZE; j++){
            if(matrix[i*SIZE + j] == find[0]){
                if(adjacentSearch(matrix, find, i, j, 0)){
                    return true;
                }
            }
        }
    }
    return false;
}


// Driver
int main(){
    char matrix[SIZE][SIZE];
    char word[MAX] = "SOKK";

    printBoard((char *)matrix);

    printf("\nThink of a word> ");
    fgets(word, MAX, stdin);
    printf("word: %s", word);

   /*if(exist((char *)matrix, word, SIZE, SIZE)){
        printf("Found\n");
   }*/
   if(Search((char *)matrix, word, strlen(word)))
      {
          printf("%s Found\n", word);
      }
    /*if(found)
    {
        printf("%s Found\n", word);
    }*/
    else{
        printf("%s Not Found\n", word);
    }
    return 0;
}