/* This is a relatively small and simple word-puzzle solver, (or at least it was; it seems to have grown a little more complex as some bugs were fixed) which takes a board layout and finds all possible plays (it is currently up to the user to chose the best one). This could be used for other games such as "Crossword Anagrams" or "Wordy" as it has no special knowlege of any one game. The current setting of the board size, of course, makes it useful for Scrabble, but that's a 2-line parameter that can be easily changed. (actually since I first wrote that, the code has become more Scrabble-oriented) I wrote this while on vacation at a Wingate hotel which has T1 ethernet to the room. Very nice. It originally took about 6 hours to get it working, over two evenings, although I've put a little more time into it since. I wrote it specifically because although the Wordgame Programmers Archive (www.gtoal.com/wordgames/) has several Scrabble sources, there was none that was basic enough to take and modify for use in various utilities. I expect this program will be developed, but I am specifically freezing this version as a short and simple example program. Although there are two procedures in here which dive into the guts of a DAWG data struture, the general framework of the source is actually completely independent of DAWGs and any other data structure could be used (right down to a linear search through a file of strings, if you feel so inclined!). The two aforementioned procedures are not especially high-quality code and are specifically *not* part of the instructional purpose of this program. Just pay attention to the interface procedures which wrap them, and ignore the internal details entirely - they are not critical to the general algorithm. You'll need this data file: --- #..-...#.J.-..# .+...=...E...+. ..+...-.-S..+.. -..+...-.U.+..- ....+....I+.... .=...=...T.KOR. ..-...-.-I.IRE. #..-...ALCADE.# ..-...-.-...-.. .=...=...=...=. ....+.....+.... -..+...-...+..- ..+...-.-...+.. .+...=...=...+. #..-...#...-..# GIMSST* 0 0 --- To generate a dawg dictionary file, you'll need the "token" program from ../spell Current bugs: if a word on the board contains a blank, and that word is added to, the blank letter is not scored as 0 but as what the actual letter would have been. Problem with 'apparent_letter' I think. Maybe in read_board? */ #include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <string.h> #include <assert.h> static int bestscore = 0; // setlocale appears to be broken :-( int latin1_islower(unsigned int cc) { char c = cc; return (islower(c) || (c == 'ä') || (c == 'ö') || (c == 'å')); } int latin1_isupper(unsigned int cc) { char c = cc; return (isupper(c) || (c == 'Ä') || (c == 'Ö') || (c == 'Å')); } int latin1_toupper(unsigned int cc) { char c = cc; if (c == 'ä') return('Ä'); if (c == 'ö') return('Ö'); if (c == 'å') return('Å'); return (toupper(c)); } int latin1_tolower(unsigned int cc) { char c = cc; if (c == 'Ä') return('ä'); if (c == 'Ö') return('ö'); if (c == 'Å') return('å'); return (tolower(c)); } int latin1_isalpha(unsigned int cc) { char c = cc; return (isalpha(c) || (c == 'ä') || (c == 'ö') || (c == 'å') || (c == 'Ä') || (c == 'Ö') || (c == 'Å')); } /*#include "mnemosyne.h"*/ /* Only externals used here are my 'dawg' library, and even that is only for loading the dict file. However in a later iteration I may move the two dawg-based procedures here to the library */ #include "splib.h" #ifndef FALSE #define TRUE (0==0) #define FALSE (0!=0) #endif static int debug = FALSE; static int megaanalysis = FALSE; #define MIN(a, b) (a < b ? a : b) #define WIDTH 15 #define HEIGHT 15 #define MAX_TILES 100 #define RACKSIZE 7 /* 7 for most, 9 for old-style German */ #define BINGO 50 #ifdef SWEDISH // under development ... äöå char FULLRACK[256]; #else #define FULLRACK "aaaaaaaaabbccddddeeeeeeeeeeeeffggghhiiiiiiiiijkllllmm\ nnnnnnooooooooppqrrrrrrssssttttttuuuuvvwwxyyz??" #endif /* 1..WIDTH for board, 0 and (WIDTH+1) for tombstones */ static char board[HEIGHT+2][WIDTH+2]; static char apparent_letter[HEIGHT+2][WIDTH+2]; static int lettermult[HEIGHT+2][WIDTH+2] = { {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,1,1,1,2,1,1,1,1,1,1,1,2,1,1,1,0}, {0,1,1,1,1,1,3,1,1,1,3,1,1,1,1,1,0}, {0,1,1,1,1,1,1,2,1,2,1,1,1,1,1,1,0}, {0,2,1,1,1,1,1,1,2,1,1,1,1,1,1,2,0}, {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0}, {0,1,3,1,1,1,3,1,1,1,3,1,1,1,3,1,0}, {0,1,1,2,1,1,1,2,1,2,1,1,1,2,1,1,0}, {0,1,1,1,2,1,1,1,1,1,1,1,2,1,1,1,0}, {0,1,1,2,1,1,1,2,1,2,1,1,1,2,1,1,0}, {0,1,3,1,1,1,3,1,1,1,3,1,1,1,3,1,0}, {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0}, {0,2,1,1,1,1,1,1,2,1,1,1,1,1,1,2,0}, {0,1,1,1,1,1,1,2,1,2,1,1,1,1,1,1,0}, {0,1,1,1,1,1,3,1,1,1,3,1,1,1,1,1,0}, {0,1,1,1,2,1,1,1,1,1,1,1,2,1,1,1,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, }; static int wordmult[HEIGHT+2][WIDTH+2] = { {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,3,1,1,1,1,1,1,3,1,1,1,1,1,1,3,0}, {0,1,2,1,1,1,1,1,1,1,1,1,1,1,2,1,0}, {0,1,1,2,1,1,1,1,1,1,1,1,1,2,1,1,0}, {0,1,1,1,2,1,1,1,1,1,1,1,2,1,1,1,0}, {0,1,1,1,1,2,1,1,1,1,1,2,1,1,1,1,0}, {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0}, {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0}, {0,3,1,1,1,1,1,1,2,1,1,1,1,1,1,3,0}, {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0}, {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0}, {0,1,1,1,1,2,1,1,1,1,1,2,1,1,1,1,0}, {0,1,1,1,2,1,1,1,1,1,1,1,2,1,1,1,0}, {0,1,1,2,1,1,1,1,1,1,1,1,1,2,1,1,0}, {0,1,2,1,1,1,1,1,1,1,1,1,1,1,2,1,0}, {0,3,1,1,1,1,1,1,3,1,1,1,1,1,1,3,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} }; static int myscore = 0; static int oppscore = 0; static char *dict = NULL; static int vertical_score[HEIGHT+2][WIDTH+2]; static int tiles_held = 0; static char tiles[/*RACKSIZE*/MAX_TILES+1]; static char fullrack[MAX_TILES+1]; static char *crosschecks[HEIGHT+2][WIDTH+2]; static char *vertical_word[HEIGHT+2][WIDTH+2]; static int vindex[HEIGHT+2][WIDTH+2]; static char remaining_tiles[MAX_TILES+1]; static char *boardfile = NULL; /* This should be in "main()" but for hacky reasons (HTML in playword()) it is global *for now* */ #define HORIZONTAL 1 #define VERTICAL 2 static int orientation = 0; static float totprob[256]; static int tot[256]; static int itot[27] = /* 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 */ { 9,2,2,4,12,2,3,2,9,1,1,4,2,6,8,2, 1,6,4,6,4,2,2,1,2, 1}; static int score[256]; static int iscore[27] = /* a b c d e f g h i j k l m n o p q r s t */ { 1, 3, 3, 2, 1, 4, 2, 4, 1, 8, 5, 1, 3, 1, 1, 3, 10, 1, 1, 1, /* u v w x y z */ 1, 4, 4, 8, 4, 10}; /* Temporarily, until I write some code to handle rack leaves in my own idiosyncratic way, I'm going to use Mark Watkins' values for rack-leave on a per-tile basis. (Not actually used yet) */ static float watkins_rackvalue[256]; static float iwatkins_rackvalue[27] = /* a b c d e f g h i j */ { 1.0, -2.0, -0.5, 0.5, 2.0, -2.0, -3.0, 1.5, -1.0, -2.0, /* k l m n o p q r s t */ 0.0, 0.5, 0.5, 0.5, -0.5, -1.0, -9.0, 1.0, 8.0, 0.0, /* u v w x y z */ -4.0, -6.0, -3.0, 2.5, -0.5, 5.0}; static NODE *dawg; static INDEX nedges; /*--------------------- crosscheck code -------------------------*/ /* When placing a word horizontally, if it abuts to any tiles either above or below, we will have generated a wildcard string consisting of the tiles above, a "?", and the tiles below, from which we then find all the valid words allowed which match that wildcard string. From that we find which letters were valid at that position, and we return the set of valid letters to the scrabble code, so that the search for legal plays can be trimmed for speed. */ /* External interface procedure follows this internal procedure, which needs a lot of extra parameters that the interface isn't really interested in */ static int crosscheck_internal( NODE *dawg, INDEX i, char *word, char *res, char *set, int len, int *found ) { int endsword, last, ch, target; NODE node; INDEX link; static int wildch = '\0'; for (;;) { node = dawg[i++]; ch = (int)((node >> V_LETTER) & M_LETTER); last = ((node & (INDEX)M_END_OF_NODE) != 0); endsword = ((node & M_END_OF_WORD) != 0); link = node & M_NODE_POINTER; res[len] = ch; res[len+1] = '\0'; target = ((int)*word)&255; if (ch != 0) { if (ch == target || target == '?') { if (target == '?') { wildch = ch; } if (endsword && *(word+1) == '\0') { int i; (*found)++; /* Add ch to crosscheck set if not already there */ /* We just assume only 1 '?' per word, and last wildch was it */ if (strchr(set, wildch) == NULL) { i = strlen(set); set[i] = wildch; set[i+1] = '\0'; } } if (*(word+1) != '\0' && link != 0) (void) crosscheck_internal(dawg, link, word+1, res, set, len+1, found); } } if (last) break; } return(0==0); } /* This is a 'black box' procedure which can be replaced by anything which behaves the same even though implemented differently. In fact the internal code of this function is a 'quick hack' and probably should be replaced by something neater. INTERFACE: inputs: word list, wild-card string containing one "?" output: string of letters which the "? could represent or NULL if none found. (i.e this square is blocked) example: twl98, "c?t" -> "auo" (cat, cut and cot all matching the pattern) */ char *convert_wildcard_to_permitted_set(NODE *dawg, char *word) { char result[MAX_WORD_LEN]; static char set[MAX_WORD_LEN]; int i = 0; *set = '\0'; if (debug) fprintf(stderr, "wildcard: %s\n", word); (void)crosscheck_internal(dawg, (INDEX)ROOT_NODE, word, result, set, 0, &i); if (i == 0) return(NULL); if (debug) fprintf(stderr, " -> %s\n", set); return(set); } /*--------------------- placement code -------------------------*/ /* This finds words which can be played at this row,column position of the length requested. It does a wildcard match of a string such as "c[aiou]t[etrains]" which in this instance might return cats, cots, cute & cuts. The search is pruned in two ways - the first, by which letters are allowed on certain squares, eg [aiou] may be a constraint from cross-check words (see above); and the second by the tiles in your rack (eg "etrains"). If you hold a blank, the wildcard might look like "c[aiou]t?" instead. The decision to do separate searches for different lengths of words was a deliberate one, to simplify the code. Some scrabble programs would prefer to do searches which looked more like "c[aiou]t*" allowing more letters to be added at the right. I chose not to do this for simplicity, and also because some other optimisations are possible when you are using fixed-length searches (although those have not yet been done). This procedure is also passed the tiles which we hold, because the wildcard itself does not describe only valid words. For instance, if we hold the tiles "act" then the wildcard might be "[act][act][act]" - but "tat" could not be played even though wildcard expansion listed it. By removing the tiles played at each point for a wild letter, we end up playing only "act" and "cat" here. One known design flaw: if we have the tiles "ob?" and want to pay the word "bob", then the fixed "b" will always be put down before the wild-card as a "b". This could be a mistake if the second "b" is on a triple-letter score, for example. [this bug was fixed when we switched from an iterative placement procedure to a recursive one, similar to that in upwords example] */ void playword(char *tiles, char *word, char *tilesleft, char *template, int placed, int Letter, int number, int orientation) { int hscore = 0, vscore = 0; int row, col; int tmp, tmpch, i, nexttile = 0; int wmult = 1; char *s = word; tiles[placed] = '\0'; /* we treat the board as horizontal even if it's not */ row = (orientation == HORIZONTAL ? number : Letter-'A'+1), col = (orientation == HORIZONTAL ? Letter-'A'+1 : number), fprintf(stdout, (orientation == VERTICAL ? "place %s at %c%d %s (%s) => " : "place %s at %d%c %s (%s) => "), tiles, (orientation == VERTICAL ? Letter : number), (orientation == VERTICAL ? number : Letter), (orientation == VERTICAL ? "down" : "across"), template); assert((word != NULL) && (boardfile != NULL) && (fullrack != NULL) && (tiles != NULL)); fprintf(stdout, "<A HREF=\"play?word=%s&board=%s&bagwas=%s&rackwas=%s&letter=%c&number=%d&orientation=%d&myscore=%d&oppscore=%d&dict=%s\">%s</A>", word, boardfile, fullrack, tiles, Letter, number, orientation, myscore, oppscore, dict == NULL ? "" : dict, word); fflush(stdout); i = col; for (;;) { if (*s == '\0') break; if (board[row][i] == 0) { /* Place first letter from "tiles" here */ hscore += ((tmp = score[tmpch = tiles[nexttile++]]) * lettermult[row][i]); if (debug) fprintf(stdout, "row %d col %d: add %d%s to hscore for %c\n", row, i, tmp, (lettermult[row][i] == 2 ? "*2L" : ( lettermult[row][i] == 3 ? "*3L" : "") ), tmpch); wmult *= wordmult[row][i]; if (vertical_word[row][i] != NULL) { tmp = (vertical_score[row][i] + (score[tmpch] * lettermult[row][i])) * wordmult[row][i]; vscore += tmp; vertical_word[row][i][vindex[row][i]] = *s; /* Plug in the letter to the vword */ fprintf(stdout, "/%s(%d", vertical_word[row][i], tmp); if (wordmult[row][i] != 1) fprintf(stdout, ":%dWS", wordmult[row][i]); fprintf(stdout, ")"); fflush(stdout); vertical_word[row][i][vindex[row][i]] = '?'; /* restore */ } if (debug) if (vertical_word[row][i] != NULL) { fprintf(stdout, "Intersects with %s ", vertical_word[row][i]); vertical_word[row][i][vindex[row][i]] = *s; /* Plug in the letter to the vword */ fprintf(stdout, "forming %s, worth %d", vertical_word[row][i], tmp); if (wordmult[row][i] != 1) fprintf(stdout, " (%dWS)", wordmult[row][i]); vertical_word[row][i][vindex[row][i]] = '?'; /* restore */ fprintf(stdout, "\n"); } } else { /* The tile is already placed - apparent_letter takes care of blanks */ /* no bonuses */ tmp = score[tmpch = apparent_letter[row][i]]; hscore += tmp; if (debug) fprintf(stdout, "add %d to hscore for %c\n", tmp, tmpch); } s += 1; i += 1; } /* simple hscore, and vscores now all added */ if (debug) if (wmult != 1) fprintf(stdout, "Multiply score by %d\n", wmult); hscore *= wmult; assert(nexttile == placed); if (placed == RACKSIZE) { hscore += BINGO; if (debug) fprintf(stdout, "Add 50 for a bingo!\n"); } if (megaanalysis) { fprintf(stdout, ". SCORE %d\n", hscore+vscore); } else { fprintf(stdout, ", leaving %s. SCORE %d\n", tilesleft, hscore+vscore); } if (hscore+vscore > bestscore) bestscore = hscore+vscore; fflush(stdout); } /* External interface procedure follows this internal procedure, which needs a lot of extra parameters that the interface isn't really interested in */ static void fix_scrabble( NODE *dawg, INDEX i, char *word, char *template, char *res, char *tilesleft, char *placedtiles, int placed, int len, int *found, int L, int n, int orientation ) { int endsword, last, ch, target; NODE node; INDEX link; for (;;) { node = dawg[i++]; ch = (int)((node >> V_LETTER) & M_LETTER); last = ((node & (INDEX)M_END_OF_NODE) != 0); endsword = ((node & M_END_OF_WORD) != 0); link = node & M_NODE_POINTER; res[len] = ch; res[len+1] = '\0'; target = *word; target &= 255; if (ch != 0) { if (ch == target) { /* matches a tile on the board already */ if (endsword && *(word+1) == '\0') { playword(placedtiles, res, tilesleft, template, placed, L, n, orientation); (*found)++; } if (*(word+1) != '\0' && link != 0) { (void) fix_scrabble(dawg, link, word+1, template, res, tilesleft, placedtiles, placed, len+1, found, L, n, orientation); } } else if (target == '?') { /* We matched a wildcard. If we have the correct letter, play it; otherwise play the blank */ if (endsword && *(word+1) == '\0') { char *s; int i; s = strchr(tilesleft, ch); if (s != NULL) { /* Do we have the actual tile? */ i = *s; *s = tilesleft[0]; tilesleft[0] = i; placedtiles[placed] = ch; playword(placedtiles, res, tilesleft+1, template, placed+1, L, n, orientation); (*found)++; } s = strchr(tilesleft, '?'); if (s != NULL) { /* If not, do we have a blank left to play? */ i = *s; *s = tilesleft[0]; tilesleft[0] = i; res[len] = latin1_toupper(ch); /* Signal blank to display routine */ /* This trick is not ideal. Would be better to have a parallel array to 'res' which is given the equivalent of 'apparent_letter' instead of uppercase. (i.e. the actual blank character. Note in almost every case I can think of, it is better to play the actual letter if you have it rather than the blank. The only exception is when you're playing the same letter twice in a word, once as the letter and once as the blank. In that case, you don't know which of the two positions may be a double or triple letter square. But if the blank is not needed in a word at all because you already have all the letters, why would you ever play it? */ placedtiles[placed] = '?'; /* blank */ playword(placedtiles, res, tilesleft+1, template, placed+1, L, n, orientation); (*found)++; } } if (*(word+1) != '\0' && link != 0) { char *s; int i; s = strchr(tilesleft, ch); if (s != NULL) { /* Do we have the actual tile? */ i = *s; *s = tilesleft[0]; tilesleft[0] = i; placedtiles[placed] = ch; (void) fix_scrabble(dawg, link, word+1, template, res, tilesleft+1, placedtiles, placed+1, len+1, found, L, n, orientation); } s = strchr(tilesleft, '?'); if (s != NULL) { /* If not, do we have a blank left? */ i = *s; *s = tilesleft[0]; tilesleft[0] = i; res[len] = latin1_toupper(ch); /* Signal blank to display routine */ placedtiles[placed] = '?'; /* Blank */ (void) fix_scrabble(dawg, link, word+1, template, res, tilesleft+1, placedtiles, placed+1, len+1, found, L, n, orientation); } } } else if (target == '[') { /* Is this letter in our set of valid letters? */ char choices[(WIDTH * (256+2)) + 1]; char *s, *saved = word; strcpy(choices, word+1); s = strchr(choices, ']'); /* We assume well-formed expressions */ *s = '\0'; word = strchr(word, ']'); if (strchr(choices, ch) != NULL) { if (endsword && *(word+1) == '\0') { char *s; int i; s = strchr(tilesleft, ch); if (s != NULL) { /* Do we have the actual tile? */ i = *s; *s = tilesleft[0]; tilesleft[0] = i; placedtiles[placed] = ch; playword(placedtiles, res, tilesleft+1, template, placed+1, L, n, orientation); (*found)++; } s = strchr(tilesleft, '?'); if (s != NULL) { /* If not, do we have a blank left? */ i = *s; *s = tilesleft[0]; tilesleft[0] = i; res[len] = latin1_toupper(ch); /* Signal blank to display routine */ placedtiles[placed] = '?'; /* Blank */ playword(placedtiles, res, tilesleft+1, template, placed+1, L, n, orientation); (*found)++; } } if (*(word+1) != '\0' && link != 0) { char *s; int i; s = strchr(tilesleft, ch); if (s != NULL) { /* Do we have the actual tile? */ i = *s; *s = tilesleft[0]; tilesleft[0] = i; placedtiles[placed] = ch; (void) fix_scrabble(dawg, link, word+1, template, res, tilesleft+1, placedtiles, placed+1, len+1, found, L, n, orientation); } s = strchr(tilesleft, '?'); if (s != NULL) { /* If not, do we have a blank left? */ i = *s; *s = tilesleft[0]; tilesleft[0] = i; res[len] = latin1_toupper(ch); /* Signal blank to display routine */ placedtiles[placed] = '?'; /* Blank */ (void) fix_scrabble(dawg, link, word+1, template, res, tilesleft+1, placedtiles, placed+1, len+1, found, L, n, orientation); } } } word = saved; } } if (last) break; } } /* This is a 'black box' procedure which can be replaced by anything which behaves the same even though implemented differently. In fact the internal code of this function (above) is a 'quick hack' and probably should be replaced by something neater. INTERFACE: inputs: word list, wild-card, rack, row & column outputs: should be list of words to play. (Currently the output is printed, not returned) The wild card can contain only fixed letters, [abcd...] (sets of letters), or "?" (single-character wild-card). There are no multi- character wild-cards (eg "*") - the word length is fixed. IMPORTANT NOTE: "cat?" is not the same as "c[a]t?" - the former expects ONE tile to be placed, the latter exects TWO. I.e. simple letters represent tiles already placed on the board. A cleaned-up interface would not need L/n (letter/number, ie row/col in format such as "H7 across" or "G5 down". This procedure should just return (or action) the list of words, and doesn't need to know where they are placed if it is not doing the placement itself. */ int scrabble_match(NODE *dawg, char *word, char *tiles, int L, int n, int orientation) { char result[MAX_WORD_LEN]; char placedtiles[MAX_WORD_LEN]; int i = 0; result[0] = '\0'; placedtiles[0] = '\0'; fix_scrabble(dawg, (INDEX)ROOT_NODE, word, word, result, tiles, placedtiles, 0, 0, &i, L, n, orientation); return(i); } /*--------------------------------------------------------------*/ /* This reads a board in the simple file format which Kevin Cowtan uses in his board-graphic image generator software. I just happened to have some cgi web page software which generates this format so I plan to reuse it to create a graphical front-end to solving scrabble problems. */ void read_board(char *fname) { int row, col; int c, rackletter; int tiles_left_in_bag; FILE *sample; char *s; sample = fopen(fname, "r"); if (sample == NULL) { fprintf(stderr, "Cannot open board file '%s'\n", fname); exit(0); } for (row = 1; row <= HEIGHT; row++) { if (debug) fprintf(stderr, "Row %02d: ", row); for (col = 1; col <= WIDTH; col++) { c = fgetc(sample)&255; if (latin1_isalpha(c)) { /* Take care with locale for other language versions */ board[row][col] = latin1_tolower(c); if (debug) fprintf(stderr, "%c", latin1_tolower(c)); if (latin1_islower(c)) { rackletter = '?' /* BLANK */; } else { rackletter = latin1_tolower(c); } apparent_letter[row][col] = rackletter; s = strchr(fullrack, rackletter); if (s == NULL) { fprintf(stderr, "Error: we appear to have too many %c's on the board\n", rackletter); fprintf(stderr, " %s\n", FULLRACK); fprintf(stderr, " %s\n", fullrack); exit(0); } memmove(s, s+1, strlen(s)); } else if (debug) fprintf(stderr, " "); } c = fgetc(sample); /* newline */ if (c != '\n') { fprintf(stderr, "Data format in .dat file\n"); exit(0); } if (debug) fprintf(stderr, "\n"); } tiles_held = 0; for (col = 0; col < RACKSIZE; col++) { c = fgetc(sample); if (c == '?') continue; if (c == '*') c = '?'; if (latin1_isalpha(c)) c = latin1_tolower(c); rackletter = tiles[tiles_held++] = c; s = strchr(fullrack, rackletter); if (s == NULL) { fprintf(stderr, "Error: we appear to have too many %c's in the rack\n", rackletter); fprintf(stderr, " %s\n", FULLRACK); fprintf(stderr, " %s\n", fullrack); exit(0); } memmove(s, s+1, strlen(s)); } tiles[tiles_held] = '\0'; fscanf(sample, " %d %d\n", &myscore, &tiles_left_in_bag); if (debug) { fprintf(stderr, "%0d Tiles: %s\n", tiles_held, tiles); } if ((tiles_left_in_bag != 0) && (tiles_left_in_bag != strlen(fullrack))) { fprintf(stderr, "Data file says %d tiles left. I'm showing %d left\n%s\n", tiles_left_in_bag, strlen(fullrack), fullrack); exit(0); } /* We don't really need this now since we're calculating it on the fly */ remaining_tiles[0] = '\0'; fgets(remaining_tiles, MAX_TILES+1, sample); /* Ignore error code */ remaining_tiles[MAX_TILES] = '\0'; fclose(sample); } /*--------------------------------------------------------------*/ /* This looks at the place where a tile is likely to be played, and whether there are tiles abutting above or below it, which would permit or deny a word to be placed there. This generates a wild-card string which is then expanded in the code above to generate the set of letters which are valid here. It is that set which is stored, not the wild card string or the words themselves. */ char *create_crosscheck_wildcard(int r, int c) { char crosscheck[WIDTH+2]; char *s; int rp; vertical_score[r][c] = 0; /* Already a tile here so crosscheck is meaningless */ if (board[r][c] != 0) return(NULL); /* none above and none below? */ if ((board[r-1][c] == 0) && (board[r+1][c] == 0)) return(NULL); /* what's above? */ rp = r-1; while (board[rp][c] != 0) rp -= 1; rp += 1; /* row of 1st letter in crosscheck word */ s = crosscheck; while (rp != r) { *s = apparent_letter[rp][c]; vertical_score[r][c] += score[*s]; /* 0 if blank */ s += 1; rp += 1; } *s++ = '?'; /* r */ vindex[r][c] = s-crosscheck-1; /* what's below? */ rp = r+1; while (board[rp][c] != 0) { *s = apparent_letter[rp][c]; vertical_score[r][c] += score[*s]; /* 0 if blank */ s += 1; rp += 1; } *s = '\0'; vertical_word[r][c] = strdup(crosscheck); return(strdup(crosscheck)); } /*--------------------------------------------------------------*/ /* Can we slot a word into the board at this row,col and length(*)? If so, then the very last thing we do before returning is to actually generate the words. This is not really good design - we should pass the wildcard which this generates up a level and have that level do the search. This procedure generates a wild-card string using fixed letters, "[...]" letter sets, and wildcards ("?") which when expanded returns valid words which can be played here. *: Note 'length' here doesn't mean word length. It means number of tiles to be placed. The word may be longer because of tiles already on the board that we are placing around. */ void slot_internal( int orig_r, int orig_c, int r, int c, int still_to_place, int placed, char *pattern, int touches_center, int touches_horiz, int touches_vert, int orientation) { int valid; int pp = strlen(pattern); int opp = strlen(pattern); char *s; /* No more loop. Just place one, and recurse. If I had done this with the scrabble program to begin with, I wouldn't have had the stupid bug to do with playing blanks as the same letter as another letter you hold in the rack... */ /* Ran off end of board with tiles still to place? */ if ((c > WIDTH) && (still_to_place > 0)) return; /* Covered with an earlier hook? */ if ((placed == 0) && (board[r][c-1] != 0) && (c != 1)) return; /* (special case for first col ... */ while (board[r][c] != 0) { /* There is already a tile on the board here. Careful with blanks */ pattern[pp++] = board[r][c++]; pattern[pp] = '\0'; } if ((c) > WIDTH) return; /* Oops, we went over the edge */ /* If center square was empty this must be the first move */ if ((board[WIDTH/2+1][HEIGHT/2+1] == 0) && (((WIDTH/2)+1 == r) && (c == (WIDTH/2)+1)) ) { touches_center = (touches_center || TRUE); } if (board[r][c-1] != 0 || board[r][c+1] != 0) touches_horiz = (touches_horiz || TRUE); if (board[r-1][c] != 0 || board[r+1][c] != 0) touches_vert = (touches_vert || TRUE); if (crosschecks[r][c] == NULL) { /* no tiles above or below in this col */ if (strchr(tiles, '?') != NULL) { /* We hold a blank so it could be anything */ sprintf(pattern+pp, "?"); } else { /* restrict search space when possible, ie only those letters for which we hold tiles */ sprintf(pattern+pp, "[%s]", tiles); } } else if (*crosschecks[r][c] == '!') { /* If no valid crosscheck at all, then reject this slot - square is blocked */ pattern[opp] = '\0'; /* undo recursion */ return; } else if ((strcmp(crosschecks[r][c], "?") == 0) && (strchr(tiles, '?') == NULL)) { /* we don't hold a blank, so do a reduction-in-strength of a wild-card "?" to [abcdefg] (i.e. only the tiles we hold) */ sprintf(pattern+pp, "[%s]", tiles); } else if (strcmp(crosschecks[r][c], "?") == 0) { /* we do hold a blank, so allow anything */ sprintf(pattern+pp, "%s", crosschecks[r][c]); } else { /* This letter is constrained by specific cross-checks */ sprintf(pattern+pp, "[%s]", crosschecks[r][c]); } pp = strlen(pattern); pattern[pp] = '\0'; placed += 1; still_to_place -= 1; if (still_to_place != 0) { /* Should this test be moved up before some of the code above? */ slot_internal(orig_r, orig_c, r, c+1, still_to_place, placed, pattern, touches_center, touches_horiz, touches_vert, orientation); pattern[opp] = '\0'; /* undo recursion */ return; } /* after placing all tiles, are there still some letters abutting to the right? If so, add them to the string to be matched */ {int p = c+1; while (board[r][p] != 0) { /*hscore += ...[r][p];*/ touches_horiz = TRUE; pattern[pp++] = board[r][p++]; /* Careful with blanks */ }} pattern[pp] = '\0'; valid = (touches_horiz || (touches_vert && (placed > 1)) || (touches_center && (placed > 1))); if (valid) scrabble_match(dawg, pattern, tiles, (orientation == HORIZONTAL ? orig_c : orig_r)-1+'A', (orientation == HORIZONTAL ? orig_r : orig_c), orientation); /* the x/y param could be done more intelligently */ } int slot(int r, int c, int l, int orientation) { char pattern[(WIDTH*(256+2))+1]; pattern[0] = '\0'; slot_internal(r, c, r, c, l, 0, pattern, FALSE, FALSE, FALSE, orientation); return(0); /* Needs to be true if any were placed */ } int main(int argc, char **argv) { int i; int row = 0, col = 0; int orientation = 0; int length = 0; char *dict = NULL; /*mnem_init(argv[0]);*/ if (argc != 3) { if (argc <= 2) { dict = "SOWPODS"; } else { fprintf(stderr, "syntax: %s board.dat dict?\n", argv[0]); exit(1); } } else dict = argv[2]; /* Default word list is TWL98 */ /* default param when debugging makes running gbd easier */ if (argv[1] == NULL) boardfile = "test5.dat"; else boardfile = argv[1]; if (!dawg_init(dict, &dawg, &nedges)) { fprintf(stderr, "%s: cannot open wordlist '%s'\n", argv[0], dict); exit(2); } /* Clear the arrays */ assert(WIDTH == HEIGHT); for (row = 0; row < (HEIGHT+2); row++) { for (col = 0; col < (WIDTH+2); col++) { board[row][col] = 0; apparent_letter[row][col] = 0; crosschecks[row][col] = NULL; vertical_word[row][col] = NULL; vindex[row][col] = 0; } } for (i = 0; i < 256; i++) { tot[i] = 2; /* Blank ;-) */ score[i] = 0; totprob[i] = 0.0; watkins_rackvalue[i] = 25.0; } #ifdef SWEDISH for (i = 0; i < 256; i++) { tot[i] = 0; /* NEED TO ADD Blank! */ score[i] = 0; totprob[i] = 0.0; watkins_rackvalue[i] = 25.0; } score[latin1_tolower('A')] = 1; tot[latin1_tolower('A')] = 8; score[latin1_tolower('Ä')] = 3; tot[latin1_tolower('Ä')] = 2; score[latin1_tolower('B')] = 4; tot[latin1_tolower('B')] = 2; score[latin1_tolower('C')] = 10;tot[latin1_tolower('C')] = 1; score[latin1_tolower('D')] = 1; tot[latin1_tolower('D')] = 5; score[latin1_tolower('E')] = 1; tot[latin1_tolower('E')] = 7; score[latin1_tolower('F')] = 3; tot[latin1_tolower('F')] = 2; score[latin1_tolower('G')] = 2; tot[latin1_tolower('G')] = 3; score[latin1_tolower('H')] = 2; tot[latin1_tolower('H')] = 2; score[latin1_tolower('I')] = 1; tot[latin1_tolower('I')] = 5; score[latin1_tolower('J')] = 7; tot[latin1_tolower('J')] = 1; score[latin1_tolower('K')] = 2; tot[latin1_tolower('K')] = 3; score[latin1_tolower('L')] = 1; tot[latin1_tolower('L')] = 5; score[latin1_tolower('M')] = 2; tot[latin1_tolower('M')] = 3; score[latin1_tolower('N')] = 1; tot[latin1_tolower('N')] = 6; score[latin1_tolower('O')] = 2; tot[latin1_tolower('O')] = 5; score[latin1_tolower('Ö')] = 4; tot[latin1_tolower('Ö')] = 2; score[latin1_tolower('P')] = 4; tot[latin1_tolower('P')] = 2; score[latin1_tolower('R')] = 1; tot[latin1_tolower('R')] = 8; score[latin1_tolower('S')] = 1; tot[latin1_tolower('S')] = 8; score[latin1_tolower('T')] = 1; tot[latin1_tolower('T')] = 8; score[latin1_tolower('U')] = 4; tot[latin1_tolower('U')] = 3; score[latin1_tolower('V')] = 3; tot[latin1_tolower('V')] = 2; score[latin1_tolower('X')] = 8; tot[latin1_tolower('X')] = 1; score[latin1_tolower('Y')] = 7; tot[latin1_tolower('Y')] = 1; score[latin1_tolower('Z')] = 8; tot[latin1_tolower('Z')] = 1; score[latin1_tolower('Å')] = 4; tot[latin1_tolower('Å')] = 2; score['?'] = 0; tot['?'] = 2; { int j; char *nextp = FULLRACK; for (i = 0; i < 256; i++) { for (j = 0; j < tot[i]; j++) { *nextp++ = i; } } *nextp = '\0'; } #else // change here for other languages for (i = 0; i < 26; i++) { tot['a'+i] = itot[i]; score['a'+i] = iscore[i]; watkins_rackvalue['a'+i] = iwatkins_rackvalue[i]; } #endif /* hand-coded random board. This could be replaced by a more complex format which includes tile distributions, values, language etc */ strcpy(fullrack, FULLRACK); /* If no tiles given in file, do megamove analysis */ bestscore = 0; read_board(boardfile); if (tiles[0] == '\0') { megaanalysis = TRUE; tiles_held = strlen(fullrack); strcpy(tiles, fullrack); } fprintf(stdout, "\nUnseen tiles are: %s\n\n", fullrack); for (orientation = HORIZONTAL; orientation <= VERTICAL; orientation++) { /* We assume throughout that we are examining only horizontal plays, and just flip the board to handle vertical plays. We flip it back at the end, in case we want to update it with a play and write it back to file. (but we don't do that yet) */ for (row = 1; row <= HEIGHT; row++) { /* calculate crosschecks for this row before we look at placements for this row. We could actually do this for the whole board first, but it isn't necessary */ for (col = 1; col <= WIDTH; col++) { char *s; /* Clean up from previous tries */ /* This is about our only use of the heap and I bet if we were to make these fixed size statics it would speed up the code... */ if (crosschecks[row][col] != NULL) { free(crosschecks[row][col]); crosschecks[row][col] = NULL; } if (vertical_word[row][col] != NULL) { free(vertical_word[row][col]); crosschecks[row][col] = NULL; } vertical_word[row][col] = NULL; /* first of all get wildcard pattern, eg "w?rd" : */ crosschecks[row][col] = create_crosscheck_wildcard(row, col); /* Then convert it to a set of valid letters */ if (crosschecks[row][col] == NULL) { /* crosschecks don't make sense here */ crosschecks[row][col]= strdup("?"); /* BUGFIX: forgot strdup! */ } else { s = convert_wildcard_to_permitted_set(dawg, crosschecks[row][col]); free(crosschecks[row][col]); if (s == NULL) { /* No letter can currently be placed in this square legally */ crosschecks[row][col] = strdup("!"); /* "!" is easier to debug than empty string */ } else { crosschecks[row][col] = strdup(s); } } } /* Now do placements: try every square on this row as position for first tile to be placed down. Rest follow automatically */ for (col = 1; col <= WIDTH; col++) { /* if (debug) fprintf(stderr, "Testing row %d col %d\n", row, col); */ for (length = 1; length <= MIN(tiles_held, 7); length++) { /* Can I legally place this many tiles onto the board here? */ if (slot(row, col, length, orientation)) { /* would be nice to pass the wildcard string back to here and then expand it/search for plays, and make the plays separately. The hack above was for convenience only. */ /* record row,col,length and wildcard for move generator (maybe) */ } } } } /* Try every row on the board */ /* flip the board around the x=y diagonal */ for (row = 1; row <= HEIGHT; row++) { for (col = 1; col <= WIDTH; col++) { int i; if (row > col) { /* avoid doing twice (no-op) */ /* swap board and apparent_letter at row,col */ i = board[row][col]; board[row][col] = board[col][row]; board[col][row] = i; i = apparent_letter[row][col]; apparent_letter[row][col] = apparent_letter[col][row]; apparent_letter[col][row] = i; } } } } /* end of horiz/vert placement loop */ /* If want to make best play on board and save it, do it here */ fprintf(stdout, "BEST SCORE WAS %d<BR>\n", bestscore); exit(0); }