0

The project involves the game scramble, where we have a 4x4 matrix of characters. The purpose of the program is to search through the matrix and find words in the matrix. I have a dictionary .txt file and can search that for a word correctly and can also print the 4x4 matrix. The problem lies on how to actually search the matrix for a word. The letters can be combined to form a word by any "touching" letters.

For example:
D O P C
H L A R
E S M T
B D E I

One of the words would be CAR.

So, basically, I need help with how you would go through the matrix and how you would be able to move to any letter touching.

int main(){
    
    FILE* Lex = fopen("lex.txt", "r");

    int i = 0;
    int j = 0;
    char *word = "attack";  //Only here to compile correctly and check to see if the dictionary can find the right word.
    char game[4][4] = {{'a', 'b', 'c', 'd'},{'e', 'f', 'g', 'h'},{'i', 'j', 'k', 'l'},{'m', 'n', 'o', 'p'}};

    for ( i = 0; i <= 3; i++){
        for( j = 0; j <= 3; j++){        //Takes the array and prints it out in a 4x4.
             game[i][j];
             printf("%c", game[i][j]); 
             if(j == 3){
                  printf("\n");     
             }             
        }    
    }
        
    char  tmp[256]={0x0};                  
                              
    while(Lex!=NULL && fgets(tmp, sizeof(tmp),Lex)!=NULL){      //Searches the dictionary for whatever word is and prints if matches
        if (strstr(tmp, word)){
            size_t lengthTmp = strlen(tmp);
            size_t lengthWord = strlen(word);
                if(lengthTmp - 1==lengthWord)
                    printf("%s", tmp);
               
        }
    }
                                
    if(Lex!=NULL) 
        fclose(Lex);

    system("PAUSE");	
    return 0;
}

I know I'm missing some things but I need some ideas on how to do a search method before I can fine tune the code. Any help is appreciated...Thanks in advance. Will be glad to clarify if anything is confusing.

2
Contributors
1
Reply
3
Views
7 Years
Discussion Span
Last Post by Protuberance
0

I think the best solution is using Finite-state machine or B-tree to keep you dictionary.
Finite-state machine(Wiki)
There is some kind of algorithm:
1. Take a letter from array.
2. Search that letter into the finite-state machine or B-tree
3. Get all of letters which follows that letter
4. Check all of adjoining letters in the array for matching.
5. If something matches goto point 2(with second letter) otherwise select another letter and repeat from point 2
6. If you collect a word - mark all it's letters as "Checked" or "Blocked"
7. Repeat, until array contains unmarked letters

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.