At the beginning of 2006 I was introduced to an online word game called quiddler. Although quiddler is more commonly played in a style where the game is multi player, it can also be played in a solitary way. For the Internet contests the solitary style is used and various individuals from all over the world compete to try to solve the daily puzzle the quickest.
The game rules are simple. You are given 16 cards each containing either one or two letters from the alphabet each of these cards also contains a numeric value, which will later be used to determine the score for the game. The sixteen cards are stacked in eight, two card high, piles with the top card face up. You objective in the game is to gain the highest score possible by selecting cards and constructing legal words out of them. For ever word created you get added to your score the point value of the sum of the cards in the word and if the word is longer than a certain number of letter you a bonus is also included in the points received for that word. The number of bonus points increase with the number of letters in the word making it critical to create the longest words possible. Once you use a card it is removed from the pile and the card below can be fliped and is available to use. If both cards are removed from the pile and it is empty a top card from another pile may be moved to the empty pile, allowing you to work with eight cards at all times until you have a total of less than eight cards left on the table. The game ends when either all the cards have been used or there are no more legal words that can be created. The online version of the game can be played as many times as you want; you can even have scores on the score board more than once.
The contest for the score board rankings starts at midnight and is ordered by the first person to get the highest score. Usually the highest possible score has been found an hour or less after the contest opens and the 10 available spots on the score board fill up rapidly. Note that if you get a high score that is currently the top one you will get first position and bump every one down a rank, however if a person gets a high score than your latter on you will also get bumped down and usually right off the score board. Try the game out for yourself to get the hang of it.
I do not consider myself a very intelligent person and when it comes to languages I am even more lost. So I tried in vain many times to get my name on the score board and have it remain there for the day. Since I am a computer science student in university I figured I might as well write a program to solve the puzzle, and see if I could get it fast enough to beat the elite human players. The rest of this document talks about the construction of my quiddler algorithm and source code for it. I do want to note that most of the code in here is pretty quickly put together and is by not means prefected infact alot of the non critical stuff is really slopy.
Quiddler puzzles are not an easy write an fast algorithm to solve for the best solution. It is however fairly trivial to write an algorithm to just come up with a solution. Which brings about some definitions for clarity.
So clearly in order to have get the highest rank on the score board we want a best solution. Quiddler puzzles often have many best solutions, that is, you can get a solution to the puzzle with the maximum score in more than one way. When finding just solutions there are many techniques that have been developed to discover them quickly, however most of these mechanism can not be applied to finding optional solution-unfortunate this is the case with solitary quiddler. Due to this fact we are left with one solution, which is recursive back tracking, the slowest and brutalist method of solving problems which exists. But lets see what we can do with it and see if we can construct an algorithm to beat elite human players with it on a regular basis.
The following algorithm, which uses recursive back tracking took me several attempts to get it where it is and still now it is not fully complete (more on this later). In the following paragraphs I am going to walk thought the major steps of the algorithm.
"Never work harder than you have to"-best way to do this is use what you are given. In this particular quiddler game the creators give us some powerful information to help us more quickly determine a best solution. The first thing they give us is all the cards in the current game set. This of course is useful as we will need to recreate the initial game state in our program, in real life you may not always have this information as the bottom cards would be hidden from your site, but in the online quiddler game, you could play the game once to reveal all the cards making note of the card's position and character value. The next important piece of information which we can use is the list of possible words that can be made from the letters in the puzzle, this is pretty easy to generate, with a simple algorithm, however the creators of the online Quiddler game put the list right in the html source code, which we can easily access.
Typically, there are between 200 - 6000 words in a list but this is not the rule just an observation. The word list will be stored in an array in dynamic memory due to the fact the size of the list is not fixed.
Will talk about data structures used amoung other stuff. To be added later.
In a later step lettered cards from the game are going to be compared against words in the word list until a match is found, the word will be removed and the procedure will re curse trying the words for the next step. It is plain to see that the size of this list will highly influence the number of recursions and the small the list the faster we can process a list.
In respect to scoring and game play anagrams look like the same word when playing the game. Hence all anagrams can be removed from the word list. This step can often remove around one quarter of the list's words substantially reducing the amount of processing needed for a complete solution.
The following code snipit shows the methode by which I determine if two words in the lists are anagrams, if they are anagram one of the words is removed from the list.
/**
* This function will take two cstring and determines if they are anagrams of
* each other; if so it will return true, if not it will return false. The
* function should not effect the string that inputted and case does not
* matter, meaning that A == a, etc.
**/
bool isAnagram(char *string1, char *string2){
/**
* These varibles will be used to keep track of the for loops.
**/
unsigned int i, j;
/**
* This boolean will tell whether a character match was found in the two
* strings and if so, it will break the for loop.
**/
bool match;
/**
* Get the string length of the strings and store it, so that each time
* their string lengths are needed it does not need to be recalculated.
* NOTE: Do to the next if statement which will return false if the strings
* are not the same length only one of the string lengths needs to be
* stored.
**/
unsigned int stringlength = (int)strlen(string1);
/**
* Because we do not want the string that are inputted into this function
* to be change we need to make copies of them first, which are stored in
* str1 and str2.
**/
char *str1, *str2;
/**
* If the strings are not the same length then they can not possibly be
* anagrams of each other and the function must be false.
**/
if (stringlength != strlen(string2)){
return false;
}
else{
/**
* If the strings are exactly the same then they violates the definition
* of an anagram and the function must be false. Please note that
* stringlength1 should be equal to the length of both strings at this
* point.
**/
if (!strncmp(string1, string2, stringlength)){
return false;
}
else{
/**
* This will allocate the memory needed to store the copies of
* strings we need to make.
**/
str1 = (char*)malloc(stringlength+1);
str2 = (char*)malloc(stringlength+1);
/**
* This makes the copies of the strings into the newly allocated
* memory.
**/
memcpy(str1, string1, stringlength+1);
memcpy(str2, string2, stringlength+1);
/**
* One of the strings is looped through so that every character in
* that string can be compared to every other character in the
* other string.
**/
for (i = 0; i < stringlength; i++){
/**
* match is set to false until a character matches another
* character. If a match is made for every character in the
* strings then they are anagrams.
**/
match = false;
/**
* The second string is looped through so that every character
* in the first string is compared to every character of the
* second string.
**/
for (j = 0; j < stringlength && !match; j++){
/**
* This looks for unique character matches.
* NOTE: This statement does a conversion to upper case
* characters each time through the loop. This maybe should
* be changed to doing it only once.
**/
if ((toupper(str1[i]) == toupper(str2[j])) &&
((str1[i] != '*') || (str2[j] != '*'))){
/**
* If a match is found than to insure that duplicate
* letters are not repeated a marker is set in place
* for the letter.
**/
str1[i] = str2[j] = '*';
/**
* If the letter has found a match then there is still
* a chance that the strings might be anagram but the
* other characters must be check to be sure.
**/
match = true;
}
}
/**
* So if the function has not found a match for a letter after
* searching through all the letters in the other string then
* the two string can not be anagrams because there is a mis-
* matched letter.
**/
if (!match){
/**
* The memory that we have allocated must be deallocated so
* we do not get a memory leak.
**/
free(str1);
free(str2);
return false;
}
}
/**
* The memory that we have allocated must be deallocated so we do
* not get a memory leak.
**/
free(str1);
free(str2);
/**
* If the function has made it to this point the strings must be
* anagrams and the function returns true.
**/
return true;
}
}
}
Once the list has been reduced we can move on to ordering it.
Word list order matters to some extent when considering the time needed to find a complete solution but most often reduces the time to acquire a best solution significantly. The time needed to find a solution best solution is more important when racing to get the first spot on the score board, while a complete solution only really ensures you have indeed found the best solution.
At any rate the word list should be ordered by increasing length of word. This will also made a series of grouped sizes. The starting location of each of the length groups will be keeped on record. We can use this information which is acting like a sparse index for our word list array to jump to the exact location in the list of word sizes that we need for the current step of the puzzle. The actually order of largest to smallest is used for two reasons first when we get to near the end of the puzzle we want to try to use words that are less than or equal to the number of letter we have left in our puzzle set. This is very easy to do when the words are ordered largest to smallest and we know the array index location for all the length groups of the words. The second reason for ordering the words largest to smallest factors more into play when finding a best solution which is that, since best solutions are composed normally of higher scoring words and higher scoring words are the longer words, we should naturally try the longer words first.
In this step we can also readjust the word list size in order to take up less memory which was freed up when in the previous step the word list size was reduced. In order to organize the word list I just used the standard C quick sort with a user defined order function.
In order to determin if a solution that is found is a best solution the score needs to be calculated. The following function does this task.
/**
* This function will calculate the current score for a puzzle given a
* precalculated total score (max game score not including bonuses), the
* current state of the game board, a card value array which linkes the
* point value of each card to the respective card, and a bonus points
* array which correlates the bonus points for a given word length.
**/
inline int score(charBoardStr board, char ch){
/**
* Lets set up the integers i and j as counter variables and set the value
* of score to the maximum score for the game not including bonus points.
**/
int i, j, score = totalScore;
/**
* Check all of the cards in the current game set that are left (if any)
* and subtract points for all the remaining cards. The i loops through
* the upper and lower levels of the piles while j loops through the piles
* of cards.
**/
for (i = 0; i < 2; i++){
for (j = 0; j < 8; j++){
/**
* If we find a card still present in the game.
**/
if (board.cards[i][j] != ch){
/**
* Then we subtract twice the value of the card from the score.
* It is twice the value because if a card is not played it you
* don't get points for playing it as well as losing points for
* having it.
**/
score -= 2 * (int)cardValue[board.cards[i][j]-92];
}
}
}
/**
* Now lets loop though all the words that make up our solution.
**/
for (i = 0; i < STACK_SIZE; i++){
/**
* If a word is list in this index in our array then let's look at it.
**/
if (eventStack[i][0] == -1){
/**
* Check out the value of the word length in the that is eventStack
* array, which holds the words for the current solution and the
* length of each words. Next look the length up in the array which
* correlates word length to bonus score and add the bonus points
* to the current score.
**/
score += bonusPoints(eventStack[i][STACK_LENGTH-1]);
}
}
/**
* Return the value of the current score for the given solution.
**/
return score;
}
The recursive function is truely the heart of the algorithm for this function if non other time has been put into to ensure it has
bool recursive(charBoardStr inBoard, int z){
int i, j, n = -1, fScore, maxScore = 0, avaliLetters = 0, totalLetters = 0;
bool doublestack = false;
charBoardStr tempBoard;
char *strloc, tempchar, word[15];
/**
* Loop through the top cards on the board.
**/
for (i = 0; i < 8; i++){
/**
* Look for any piles of cards that is empty.
**/
if ((inBoard.cards[0][i] == '*') && (inBoard.cards[1][i] == '*')){
/**
* If an empty pile exists indicate this by setting n from -1 to
* the location of the pile. This location will be used later
* when moving cards from double stacked piles to empty piles.
**/
n = i;
}
else{
/**
* If the current location is not empty see if there are two cards
* in the pile.
**/
if ((inBoard.cards[0][i] != '*') && (inBoard.cards[1][i] != '*')){
/**
* If there are two cards in the pile then indicate this to the
* rest of the function by setting doublestack to true.
**/
doublestack = true;
/**
* Count the number of letters that are available to use for
* constructing the next word. Some cards have two letters so
* make a distinction between two and one letter cards from the
* array.
**/
avaliLetters += (inBoard.cards[0][i] > 96 ? 1 : 2);
/**
* Count the number of letters that are left in the whole game.
**/
totalLetters += (inBoard.cards[1][i] > 96 ? 1 : 2);
/**
* Accumulate the value of the highest possible score that can
* be produced from the given number of cards and thier values.
**/
maxScore += 4 * ((int)cardValue[inBoard.cards[0][i]-92] +
(int)cardValue[inBoard.cards[1][i]-92]);
}
else{
/**
* If the pile is not empty and it is not full (two cards) then
* the pile must have only one card. Lets see if the card is on
* the top or the bottem.
**/
if (inBoard.cards[0][i] != '*'){
/**
* If the card is on the top then add it to the number
* of letter the card has to the number of avalible
* letters.
**/
avaliLetters += (inBoard.cards[0][i] > 96 ? 1 : 2);
/**
* Also keep accmulating the max possible score.
**/
maxScore += 4 * (int)cardValue[inBoard.cards[0][i]-92];
}
else{
/**
* If there is only one card and it is not on the top
* it must be on the bottom and we shall add it to the
* number of avalible letters depending on how many
* letters are on the card.
**/
avaliLetters += (inBoard.cards[1][i] > 96 ? 1 : 2);
/**
* Keep accmulating the maximum possible score.
**/
maxScore += 4 * (int)cardValue[inBoard.cards[1][i]-92];
}
}
}
}
/**
* Lets conclude this section by finishing off our calculation of the total
* number of letters currently in the game.
**/
totalLetters += avaliLetters;
/**
* If there is a pile that is empty and we have a pile that is full then
* we have an opertunity to move a card from the top of a full pile to
* an empty one.
**/
if ((n != -1) && (doublestack)){
/**
* Once again loop through all the visible cards.
**/
for (j = 0; j < 8; j++){
/**
* Look for empty piles.
**/
if ((inBoard.cards[0][j] != '*') && (inBoard.cards[1][j] != '*')){
/**
* If a suitable empty pile is found then move the card from
* the top of the full pile to the empty pile.
**/
inBoard.cards[0][n] = inBoard.cards[0][j];
inBoard.cards[0][j] = '*';
/**
* Record the type of event in the event stack, which keeps
* track of the state of the system as it recurses.
**/
eventStack[z][0] = 1;
/**
* Record the location the card was moved from in the event
* stack.
**/
eventStack[z][1] = n;
/**
* Record the location the card was moved to in the even stack.
**/
eventStack[z][2] = j;
/**
* Recursively call the function again.
**/
if (recursive(inBoard, z+1)){
/**
* If returns true we have something that works so return
* true as well.
**/
return true;
}
/**
* If the function did not return true then this must be a bad
* move so lets back track one step. First by deleting the
* record in the stack.
**/
eventStack[z][0] = 0;
/**
* Then by putting the board back how it origionally was.
**/
inBoard.cards[0][j] = inBoard.cards[0][n];
inBoard.cards[0][n] = '*';
}
}
}
/**
* Lets now calculate the score for this current game state.
**/
fScore = score(inBoard, '*');
/**
* If the current score is higher than best score we have found a new best
* solution to this puzzle.
**/
if (fScore > bestScore){
/**
* If we have found a new best solution then lets set best score to the
* current score.
**/
bestScore = fScore;
/**
* Now print and/or submit our results.
**/
#ifdef HUMAN
printAnswer(bestScore);
#endif
#ifdef COMPUTER
createOutString(bestScore, "Nixuz", initboard);
submitResult();
#endif
}
/**
* If we discover that we only have less than two avalible letters left
* then the game is over because words have to be two letter long or
* longer. So we back track to the pervious step. In a similar way if
* the best possible score we can ever reach is lower than the score needed
* to beat then it is pointless to go on and we should back track.
**/
if ((avaliLetters < 2) ||
((fScore + maxScore + bonusPoints(totalLetters)) <= bestScore )){
return false;
}
/**
* We need to make a copy of the current board state so we can re establish
* it when back tracking.
**/
tempBoard = inBoard;
/**
* Set our index to the location of the longest words in the word list
* array we have avalible letters for.
**/
i = lengthlocs[avaliLetters];
/**
* Loop though all the remaining words in our wordlist array that are equal
* in length or smaller than the current word.
**/
for (; i < numWords; i++){
/**
* This will print our the precentage of the word list that has already
* been proccessed.
**/
#ifdef HUMAN
if ((z == 0) && ((i % 100) == 0)){
printf("%4f%% of base words complete.\n",
((float)i/(float)numWords)*100);
}
#endif
/**
* If we find a word to process copy it into a new word variable.
* So we don't destroy our wordlist when analyzing the word.
**/
strcpy(word, wordlist[i]);
/**
* Set the word length count to 1. By counting the word length as
* we loop though it we save processing time as opposed to doing
* the calculation separately.
**/
n = 1;
/**
* Loop thought the eight piles looking only at the visible card if
* any exists.
**/
for(j = 0; j < 8; j++){
/**
* If there is a top card then this is the visible one at which
* we look.
**/
if (tempBoard.cards[0][j] != '*'){
/**
* Check if the letters on the card are matched to any in
* the word, where double letters are kept together.
**/
if (strloc = strstr(word,
strRef[(int)tempBoard.cards[0][j]-92])){
/**
* See if the cards are single or double lettered.
**/
if (tempBoard.cards[0][j] > 96){
/**
* If the cards are single lettered then delete the
* letter from the word.
**/
strloc[0] = '*';
/**
* Since only one letter was used add a letter to
* the letter count.
**/
n++;
}
else{
/**
* If the card has two letters then remove both
* letters from the word string.
**/
strloc[0] = strloc[1] = '*';
/**
* Because we are representing cards with only
* one character we place a -2 in for the other
* character to indicate that it should be there.
* This saves us from having to clear a whole
* event in the event stack at every back track,
* instead we just over write the info, so the -2
* is just over writting any info before this. An
* actual place must be saved due to the fact that
* the null character must be placed at the end of
* word using the word length that is being
* calculated.
**/
eventStack[z][strloc - word + 2] = -2;
/**
* Add two to the length of the word.
**/
n += 2;
}
/**
* Remove the card from the game set.
**/
tempBoard.cards[0][j] = '*';
/**
* Indicate the location of the card in the game (aka)
* which pile it was on and record that in the event
* stack.
**/
eventStack[z][strloc - word + 1] = j;
}
}
/**
* If the visible card card is in the bottom position.
**/
else if(tempBoard.cards[1][j] != '*'){
/**
* Check to see if the letters on the card are in the word.
**/
if (strloc = strstr(word, strRef[(int)tempBoard.cards[1][j]-92])){
/**
* See if the card has two or one letters on it.
**/
if (tempBoard.cards[1][j] > 96){
/**
* If there is only one letter delete the letter
* from the current word.
**/
strloc[0] = '*';
/**
* Add one to the word length.
**/
n++;
}
/**
* If the card has two letters.
**/
else{
/**
* Delete both letters from the word.
**/
strloc[0] = strloc[1] = '*';
/**
* Inidicate in the event stack that a double
* letter card represented by a single. See above
* comment.
**/
eventStack[z][strloc - word + 2] = -2;
/**
* Add two to the word length count.
**/
n += 2;
}
/**
* Remove the card from the game.
**/
tempBoard.cards[1][j] = '*';
/**
* Record where the card came from in the
* game stack.
**/
eventStack[z][strloc - word + 1] = j;
}
}
}
/**
* Check to see if the word now only contains empty letters which
* are indicated by the '*' character.
**/
if (fullSet('*', word)){
/**
* If the all the letter in the word have been found in the card
* letters then we have a word that fits, so now we must indicate
* that this next event in the event list is a word so we do this
* by placing a -1 in the first location.
**/
eventStack[z][0] = -1;
/**
* Next we need to put a negitive one at the end of the word
* which acts as a null character, we make use of the word
* length which we have been calculating to do this efficiently.
**/
eventStack[z][n] = -1;
/**
* Lets finish this event stack record off by placing the word
* length at the end so we don't have to recalculate it.
**/
eventStack[z][STACK_LENGTH-1] = n-1;
/**
* If we are going to be a little slack on efficiency but make
* things a bit more user friendly lets copy the word into a
* word event stack.
**/
#ifdef HUMAN
memcpy(words[z], wordlist[i], n);
#endif
/**
* Since we found a word that worked lets recurse to the next level
**/
if (recursive(tempBoard, z+1)){
/**
* If the next level was also worked we return true.
**/
return true;
}
/**
* If things did not work in a higher up level, back track by
* removing any additions to the words stack if any were placed
* there.
**/
#ifdef HUMAN
words[z][0] = '\0';
#endif
/**
* In the same way remove any word events that were placed on the
* stack.
**/
eventStack[z][0] = 0;
}
/**
* Replace the board with the origional board for this step so we can
* try again.
**/
tempBoard = inBoard;
}
/**
* If we have got here we have reached a complete solution so return.
**/
return false;
}
This document is still in progress more to follow later.