Scrabble in C

[AnujSuper9]

Hello everyone!

So, I've been given an assignment to create something of a simplified Scrabble game in C.

I'll start of by mentioning that I'm aware of the vastness in similarities between C and C++, but I am more versed in C++ and so I'd consider my C to be slow but functional, so please bear with me if I'm making trivial syntax errors.

Now, the assignment is to take an existing 'board' with some letters already placed on it, and a 'tray' of letters for the player, and then output a new 'board_res' with the new words/letters on it, a new 'tray_res' with the letters removed that were added to the board, and the total word score for the letters added (no triple or double word/letter scoring either).

The idea is to create a function that finds the maximal score possible, and uses those letters to form those words. Scoring is based on a template similar to traditional Scrabble letter scoring.

Now, I haven't even began writing too much code for this yet as I am still in the design phase of this. I'm not really sure what the best approach of attack is.

My initial thought is to check each 'word' present on the board, or even each grouping of letters, and see if it matches in similarity to any other words possible with letters in my tray, but that seems roundabout and not necessarily capable of achieving the optimal score.

My second thought is to take the letters one by one and place them near the words and see if they match something in the dictionary, check the score of it, and store the highest scoring variation of this. Now of course, the problems with this are immediately easy to recognize, as this is also somewhat of a roundabout way of doing it, and may not allow taking advantage of things like multiple word scores or etc.

Btw, when I refer to the dictionary, I refer to the a random char *dictionary[] array that I've been provided to check against, which we assume has words in it similar to what would be found in a dictionary.

So my other thought was to maybe start taking letters from my tray, and letters from the board, and checking in the dictionary the possibilities allowed by those letters. Maybe even establish some sort of order for the letters already on the board and then gauge the potential word scores there. But this seems a bit overly complex for this kind of thing.

Anyway, I assume that the creation of this design is one of the biggest purposes of this problem. I will continue to think about this obviously, but input/ideas/suggestions from you all would be most welcome.

Unscrambling a set of given letter is trivial if you use a letter frequency algo.

http://www.daniweb.com/code/snippet906.html

But once you start using a board there is also the position to consider.

http://www.gtoal.com/wordgames/scrabble.html

Seemed like a good site, you could probably simplify that.

A dynamic programming approach seems more logical than a brute force option.

[AnujSuper9]

Thanks for the links, iamthwee, they have been very helpful.

Regardless actually, I'm still having trouble coming up with the algorithm for this...

So I figure maybe I'll do this:

1. Find the spots on the board where there are "attachment points," i.e. next to tiles there there are already letters.
2. Cycle through all of the possible letters that could go there and see if it contributes towards forming a word.
3. If so, continue forming said word till complete.
4. Once said word is complete, calculate and store its score.
5. Continue process for any remaining letters.
6. Repeat process and store only the highest score.

...Hmm, how would I make certain that it wasn't trying the same letters/words in step 2?

Ugh, this entire process sounds relatively simple on paper, but I still can't figure out how exactly to write it, because I keep thinking of test cases where it wouldn't work. Not to mention the overall complexity of the individual steps outline above as well.

[csurfer]

Attachment point theory is good.You can create a board in which you assign three different symbols which mean <a char is placed here>,<a char can be placed here>,<a char is not placed but you cannot place a character here.>

And for the question you have asked what you can do is take the character's you have (the ones which you can make words) into an array and try rearranging them so that they form some meaning,in the process consider the attachment points as the starting character.That is even though you have 7 character blocks try using the 8th block as one of the available characters. In this way by arrays you can control the number of times you use a character.

[jephthah]

when in doubt, start simple and work your way up.

first get the mechanics of the board working. placing letters and calculating scores manually

then try implementing a simple algorithm to calculate all possible words (and their correspondign scores) given a set of letters, at one "insertion point" ... meaning, you tell the program *where* you want to attempt a word, and it returns the possible words you can put at that spot using whatever existing letters are present.

once you get that done, and i dont think that is an easy task, *then* worry about trying to generalize it across the entire board.

[jephthah]

i just pounded out a rough scrabble game, basically just the board and tile scoring. no dictionary check, and does not account for incidental parallel tiles in the scoring. this was a fun timewaster, but i think i'm mostly done with it now.

or maybe it will annoy me late nights until i tweak it to death

either way. do what you want with it.

// SCRABBLE GAME
// by jephthah
//
// develops standard english scrabble board and allows user to 'place' 
// tiles on board ... checks validity of word placement according to 
// boundaries and existing tiles ... calculates word scores based on tile 
// values, word and letter multipliers, and existing tiles' face value
//
// to do:  	
//    score parallel tiles that incidentally form cross-words with placed tiles
//    allow variable number of players
//    assign random tiles to players per standard distribution
//    validate words to "official dictionary"
//			
//

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

#define FLUSH_STDIN(x) {if(x[strlen(x)-1]!='\n'){do fgets(Junk,16,stdin);while(Junk[strlen(Junk)-1]!='\n');}}
char Junk[16]; // buffer for discarding excessive user input, used by "FLUSH_STDIN" macro

// Globals

typedef struct {
    char tile;      // current tile at board position
    int letter;     // letter multiplier (2 or 3), 0 if none
    int word;       // word multiplier (2 or 3), 0 if none
} board_t;

// board geometry 15x15
// add one extra column for print border
board_t Board[15][16];

// tile values are A B C D E F G H I J K L M N O P Q  R S T U V W X Y Z
int TileScore[26]={1,3,3,2,1,4,2,4,1,8,5,1,3,1,1,3,10,1,1,1,1,4,4,8,4,10};



// Functions

// initialize blank board with word and letter
// multipliers for each space, if any
void init_board(void)
{
    int i, j;

    for (i=0; i<15; i++)
        for (j=0; j<16; j++)
        {
            Board[i][j].letter = 0;
            Board[i][j].word = 0;
            Board[i][j].tile = ' ';
            if ((i==0 || i==7 || i==14) && (j==0 || j==7 || j==14))
                Board[i][j].word = (i==7 && j==7) ? 2 : 3;
            else if ((i==5 || i==9) && ((j-1)%4==0))
                Board[i][j].letter = 3;
            else if ((j==5 || j==9) && ((i-1)%4==0))
                Board[i][j].letter = 3;
            else if ((i==6 || i==8) && (j==2 || j==6 || j==8 || j==12))
                Board[i][j].letter = 2;
            else if ((j==6 || j==8) && (i==2 || i==6 || i==8 || i==12))
                Board[i][j].letter = 2;
            else if ((i==3 || i==11) && (j==0 || j==7 || j==14))
                Board[i][j].letter = 2;
            else if ((j==3 || j==11) && (i==0 || i==7 || i==14))
                Board[i][j].letter = 2;
            else if (i==j || i==(14-j))
                Board[i][j].word = 2;
        }
}

// draw the current board state including placed tiles
// square boundaries indicate word or letter multipliers
//
//  +---+  +- -+  +...+  +. .+  +   +
//  |3x |  |2x |  .3x .  .2x .   no
//  |wd |   wd    .let.   let    mult
//  |   |  |   |  .   .  .   .
//  +---+  +- -+  +...+  +. .+  +   +
//
void draw_board(void)
{
    int i, j, letter, word;

    printf("    1   2   3   4   5   6   7   8   9   10  11  12  13  14  15\n\n  ");
    for (i=0; i<15; i++)
    {
        for (j=0; j<15; j++)
        {
            letter = (Board[i][j].letter | ((i)?Board[i-1][j].letter:0));
            word = (Board[i][j].word | ((i)?Board[i-1][j].word:0));
            if (letter>1)
                printf("%s",(letter==2)?"+. .":"+...");
            else if (word>1)
                printf("%s",(word==2)?"+- -":"+---");
            else
                printf("+   ");
        }
        printf("+\n  ");
        for (j=0; j<16; j++)
        {
            letter = (Board[i][j].letter | ((j)?Board[i][j-1].letter:0));
            word = (Board[i][j].word | ((j)?Board[i][j-1].word:0));
            if (letter>1)
                printf(".   ");
            else if (word>1)
                printf("|   ");
            else
                printf("    ");
        }
        printf("\n%c ",i+0x61);
        for (j=0; j<16; j++)
        {
            letter = (Board[i][j].letter | ((j)?Board[i][j-1].letter:0));
            word = (Board[i][j].word | ((j)?Board[i][j-1].word:0));
            if (letter == 3)
                printf(". %c ",(j<15)?Board[i][j].tile:i+0x61);
            else if (word == 3)
                printf("| %c ",(j<15)?Board[i][j].tile:i+0x61);
            else
                printf("  %c ",(j<15)?Board[i][j].tile:i+0x61);
        }
        printf("\n  ");
        for (j=0; j<16; j++)
        {
            letter = (Board[i][j].letter | ((j)?Board[i][j-1].letter:0));
            word = (Board[i][j].word | ((j)?Board[i][j-1].word:0));
            if (letter>1)
                printf(".   ");
            else if (word>1)
                printf("|   ");
            else
                printf("    ");
        }
        printf("\n  ");
    }
    printf("+---+   +   +. .+   +   +   +---+   +   +   +. .+   +   +---+\n\n  ");
    printf("  1   2   3   4   5   6   7   8   9   10  11  12  13  14  15 \n\n");
 }

// ask user to input starting point for word insertion
// output row and column (zero-based index from top left)
// returns 1 if successful
//         0 if unsuccessful, and outputs will be undefined
//         -1 if user opts to quit
int get_location(int *row, int *col)
{
    char *temp, input[16];

    printf("enter row/col to start (ex: H8) or 'Q' to quit: ");
    fflush(stdout);

    fgets(input,sizeof(input),stdin);
    FLUSH_STDIN(input);

    input[0] &= 0x5F; //converts alpha to UPPERCASE

    if (input[0]=='Q')
        return -1;

    *row = input[0]-0x41; // zero-based index
    if (*row<0 || *row>14)
    {
        printf("not valid, try again.\n");
        return 0;
    }
    *col = strtol(&input[1],&temp,10);
    if (temp==&input[1] || *col<1 || *col>15)
    {
        printf("not valid, try again.\n");
        return 0;
    }
    *col = *col - 1; // make column zero-based index

    return 1;
}

// ask user to input direction for word insertion
// output dir = 0 horizontal or dir = 1 vertical
// returns 1 if successful
//         0 if unsuccessful, and outputs will be undefined
//         -1 if user opts to quit
int get_direction(int *dir)
{
    char input[16];

    printf("enter direction 'H'(0) or 'V'(1), or <ENTER> to restart: ");
    fflush(stdout);

    fgets(input,sizeof(input),stdin);
    FLUSH_STDIN(input);

    input[0] &= 0x5F; //converts alpha to UPPERCASE

    if (input[0]=='H' || input[0] == '0')
    {
        *dir = 0;
        return 1;
    }
    if (input[0]=='V' || input[0] == '1')
    {
        *dir = 1;
        return 1;
    }
    if (input[0]=='\n')
        return -1;

    printf("not valid, try again.\n");
    return 0;
}


// ask user to input the word to be inserted and checks validity
//    valid word must be alphabet chars only, of proper lenght, and
//    stay within board boundaries.
// input row,col,dir previously described by user
// output 'word' as entered by user, if valid.   must point to buffer
//    of at least 17 bytes to allow for \newline and \null chars
// returns 1 if successful
//         0 if unsuccessful, and output will be undefined
//         -1 if user opts to quit
int get_word(char *word, int row, int col, int dir)
{
    char *temp=word;
    char onechar;
    size_t length;

    printf("enter word, or <ENTER> to restart: ");
    fflush(stdout);

    fgets(word,17,stdin);  // 'word' must point to at least 17 bytes
    FLUSH_STDIN(word);      // warning: discards excessive input

    if (word[0] == '\n')  // \newline indicates user requests restart
        return -1;

        // otherwise remove newline char
    word[strcspn(word,"\n")]='\0';
        // and check that only alpha characters are permitted
    while(*temp)
    {
        onechar = *temp++ &= 0x5F; //converts alpha to UPPERCASE
        if (onechar < 'A' || onechar > 'Z')
        {
            printf("not valid, try again.\n");
            return 0;
        }
    }
        // verify word does not exceed board boundary
    length = strlen(word);
    if ((length+((dir)?row:col)) > 15)
    {
        printf("not valid, try again.\n");
        return 0;
    }

    return 1;
}

// scores a word at the indicated board placement if word is a valid
//    placement according to existing letters
// input word,row,col,dir previously indicated, plus 'accept'
//    argument which indicates whether word is written
// output score of word
// returns 1 if successful
//         0 if unsuccessful, and output will be undefined
//         -1 if user opts to quit
int score_word(char *word, int *score, int row, int col, int dir, int accept)
{
    char *temp = word;
    int tempscore, valid=0, wordmult=1, r=row, c=col, index;

    tempscore = 0;
    *score = 0;

    while(*temp)
    {
        if (r == 7 && c == 7)  // first valid move uses center square
            valid = 1;

        index = *temp - 0x41;  // find zero-based index for alpha tile score

        if (Board[r][c].tile != ' ') // if letter was already placed...
        {
            if (Board[r][c].tile != *temp) // make sure it matches
            {
                printf("not valid, try again.\n");
                return 0;
            }
            valid = 1; // valid moves use previously placed letter
            tempscore += TileScore[index]; // tile score has no multipliers
        }
        else
        {       // new tiles get letter and/or word multiplier, if any
            tempscore += (TileScore[index] * ((Board[r][c].letter > 1)?Board[r][c].letter:1));
            if (Board[r][c].word > 1)
                wordmult *= Board[r][c].word;
        }
            // increment row or col index appropriately
        if (dir) r++;
        else c++;
            // increment pointer for next letter
        temp++;
    }

    if (valid == 0)
    {
        printf("not valid, try again.\n");
        return 0;
    }
        // calculate final word score
    *score = tempscore * wordmult;

    if (accept) // add word to board if accepted
    {
        r=row;
        c=col;
        temp=word;
        while (*temp)
        {
            Board[r][c].tile=*temp++;
            if (dir) r++;
            else c++;
        }
    }
    return 1;
}




int main()
{
    int row, col, direction, player=1, score_p1=0, score_p2=0, tempscore, result;
    char word[17], prompt[8];

    init_board();

    while(1)
    {       // display current board and scores
        draw_board();
        printf("SCORE Player 1: %-4d            Player 2: %d\n",score_p1, score_p2);
            // indicate which player's turn
        printf("\n -- PLAYER #%d --\n",player);

            // get location of where to start word insertion, or quit game
        do result = get_location(&row, &col);
        while (result == 0);
        if (result == -1)
            break;

            // get direction (Horiz, Vert) to place word, or restart location
        do result = get_direction(&direction);
        while (result == 0);
        if (result == -1)
            continue;

            // get word to be inserted, or restart location
        do result = get_word(word, row, col, direction);
        while (result == 0);
        if (result == -1)
            continue;

            // test validity and score word on board
        tempscore=0;
        while (1)
        {
            result = score_word(word, &tempscore, row, col, direction, 0);
            if (result == 1)
                break;
            do result = get_word(word, row, col, direction);
            while (result == 0);
            if (result == -1)
                break;
        }
            // restart new location if user opts out
        if (result == -1)
            continue;

            // display score for valid word allow accept or reject
        printf("score is %d.  accept word? (Y/N): ",tempscore);
        fflush(stdout);
        fgets(prompt,sizeof(prompt),stdin);
        prompt[0] &= 0x5F;  //converts alpha to UPPERCASE
        FLUSH_STDIN(prompt);

            // write word to memory, or allow new word/location
        if (prompt[0]=='Y')
            result = score_word(word, &tempscore, row, col, direction, 1);
        else
            continue;

            // unknown error, word was not written to board memory
        if (result == 0)
            printf("ERROR:  word was not entered!\n");

            // score word to player's total
        else if (player == 1)
            score_p1 += tempscore;
        else
            score_p2 += tempscore;

        player ^= 3;  // XOR function toggles Player1 <--> Player2
    }

    return 0;
}