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.

4
Contributors
6
Replies
9
Views
8 Years
Discussion Span
Last Post by jephthah

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

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

nice

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.

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.

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.

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;
}
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.