This is all about recursive problems and this is the main problem!.. a boggle which is when you have a 4*4 grid of letters and you need to find letter within it.
The PDF within the zip file attached explains more in more detail, but the main basics of the game is that you setup a grid with random letters (in the assignment you could also take in user input to build up the grid from that, or there was a file of 16 dice with there set characters on them). And then once the grid is built up to then find words within that grid, you can use any letters from within that letter that you are at within a 3*3 grid around it (if possible e.g. no sides) but you cannot re-use any letters that you have already used.
In this assignment it was to use recursive functions to solve the problem of finding words, from the computer point of view, it should find all of the words within the grid, but the human point of view (whom goes first) tries to find all of the words within the grid and the recursive function should make sure that there is a possible combination of that word within the grid.
Both of the functions are very similar, here is the human version, in this version we only need to make sure that the word to find (findThis) is within the grid of characters, below this is a example of the grid. The parameters are what to find (findThis) the board to search (theBoard) the route taken to find this word (theRoute) and the later 3 are internal maintenance of recursive calling, alreadyFound is the word already found (could have used the theRoute, but though it would be nice to another string) and also the point of where we are, placeY placeX.
So to start with the base case is if we have found the string to find, findThis, if not, then if we have just started the search (alreadyFound is empty) then find the first letter within the grid, once found it then re-call the function to find the other letters using the place where we found the first letter (and next and next letters), so once we have found the first letter the already found string is not empty, so search around the letter (not itself) within a 3*3 grid. Most of the bits inside of the code is filling in the route path and also updating the already found string.
bool findUsersWord(string findThis, Grid<char> &theBoard, Vector<cell> &theRoute, string alreadyFound, int placeY, int placeX) { // need to find the findThis base case if (findThis == alreadyFound) return true; // need to find the first letter within the board and then progress around that. if (alreadyFound.empty()) { for (int rows = 0; rows < theBoard.numRows(); rows++) for (int cols = 0; cols < theBoard.numCols(); cols++) // find the each character within the if (theBoard[rows][cols] == findThis[0]) { alreadyFound = findThis[0]; cell newR; newR.row = rows; newR.col = cols; theRoute.add(newR); if (findUsersWord(findThis, theBoard, theRoute, alreadyFound, rows, cols)) return true; else // clear out the found Board theRoute.clear(); } } else { // try and find the next letters within the area around the base letter // spin around the letter 3 * 3 grid for (int y= (placeY > 0 ? placeY-1: placeY); y <=(placeY == (theBoard.numRows()-1) ? placeY : placeY+1);y++) for (int x=(placeX > 0 ? placeX-1: placeX); x<=(placeX == (theBoard.numCols()-1) ? placeX : placeX+1); x++) if ((theBoard[y][x] == findThis[alreadyFound.length()]) && (!(y==placeY && x ==placeX))) // already used letter if (!placeAlreadyUsed(y,x,theRoute)) { alreadyFound += findThis[alreadyFound.length()]; cell newR; newR.row = y; newR.col = x; theRoute.add(newR); if (findUsersWord(findThis, theBoard,theRoute, alreadyFound, y, x)) return true; else { if (alreadyFound.length() > 1) alreadyFound = alreadyFound.substr(0, alreadyFound.length()-1); theRoute.removeAt(theRoute.size()-1); } } return false; } return false; } |
Here is a example of the output of the grid, with the words highlighted “MALT” with each position within the word where it was linked together, e.g M is the first letter thus there is a number 1 within the image on the M.
and here is the computer hammering me !!.. he found allot more words than what I did.
I did do the extensions, so that you can also use the mouse as a input to build up the word to search for by clicking on the characters and also displaying route path of the word was found in the grid.
Also added in some sound to the program, so if the human picks a word that is not in the dictionary/grid then comes back with a sound. I did implement the converting the letter to “Q” to “QU” for the human input to give myself abit more chance!! :).. but could have added to the computer recursive function because just needed to call the function
string addQU(string theStr) { int findI =0; while (true) { findI = theStr.find("Q", findI); if (findI >= 0) theStr = theStr.replace(findI,1,"QU"); if (findI == -1) return theStr; findI++; } } |
Also I did the mouse input, so that it will take a mouse position and find the appropriate letter on the grid, does some maths to find the top left position on the grid and then how far the mouse is from that, then the letters on the grid are 0.5 in size, so divide the distance from there and you get the position.
char getMouseWord(Grid<char> &theBoard, int dimension) { double x = GetMouseX(); double y = GetMouseY(); // get the start point x -= 1.93; y -= 3.1; y *= -1; int row = (int)(y / 0.5); int col = (int)(x / 0.5); if ((row < dimension) && (col < dimension)) return theBoard[row][col]; else return NULL; } |
Here is the computers recursive function, it is very similar to the humans version, but it will search for possible words with the grid and using the startY/startX so that we do not restart the search from point 0,0 on the grid, but where we was last, makes it allot more quicker!!!.
// returns a new word found on the grid, if able to string findComputersWord(Grid<char> &theBoard, Lexicon alreadyFoundWords, Lexicon dictionary, Vector<cell> &theRoute, int startY, int startX, string alreadyFound, int placeY, int placeX) { if (alreadyFound.length() >= MIN_WORD_COUNT) if (dictionary.containsWord(alreadyFound)) if (!alreadyFoundWords.containsWord(alreadyFound)) return alreadyFound; // need to find the first letter within the board and then progress around that. if (alreadyFound.empty()) { for (int rows = startY; rows < theBoard.numRows(); rows++) for (int cols = startX; cols < theBoard.numCols(); cols++) // find the each character within the { alreadyFound = theBoard[rows][cols]; cell newR; newR.row = rows; newR.col = cols; theRoute.add(newR); string newWord = findComputersWord(theBoard,alreadyFoundWords, dictionary,theRoute, startY, startX, alreadyFound, rows, cols); if (newWord.length() > 0) return newWord; else { // clear out the found Board theRoute.clear(); } } } else { // try and find the next letters within the area around the base letter // spin around the letter 3 * 3 grid for (int y= (placeY > 0 ? placeY-1: placeY); y <=(placeY == (theBoard.numRows()-1) ? placeY : placeY+1);y++) for (int x=(placeX > 0 ? placeX-1: placeX); x<=(placeX == (theBoard.numCols()-1) ? placeX : placeX+1); x++) { if (!(y==placeY && x ==placeX)) { // already used letter if (!placeAlreadyUsed(y,x,theRoute)) { alreadyFound += theBoard[y][x]; cell newR; newR.row = y; newR.col = x; theRoute.add(newR); if (dictionary.containsPrefix(alreadyFound)) { string newWord = findComputersWord(theBoard, alreadyFoundWords, dictionary,theRoute,startY, startX, alreadyFound, y, x); if (newWord.length() > 1) return newWord; else { if (theRoute.size() > 0) theRoute.removeAt(theRoute.size()-1); } }else { if (theRoute.size() > 0) theRoute.removeAt(theRoute.size()-1); } // if this new line of attack does not work out, clear the foundboard and also the alreadyfound variables. if (alreadyFound.length() > 0) alreadyFound = alreadyFound.substr(0, alreadyFound.length()-1); } } } } return ""; } |
I have included the source code and the PDF file of the assignment within the attached zip file, it works in Visual Studio 2008.
Choose Set and Map instead of vectors and grid.And use operation like intersect,delete
Both recursion will become a 1o line code. 🙂
Thanks Atul, shall give that a go.
Where do I find the attached zip file with visual studio code ?
Hi Gerry
Sorry I do not longer include the zip’d source code as I have been informed that some students was using it to cheat.
Hope that helps.
Ian