Quote:
Originally Posted by Kristi
Given a word list, find all the words from that list you can make on an x by x Boggle board (the game itsself is a 4x4 board, but we can do better  )
Addeum: We can use the TWL06 as our word list.
http://www.cs.bu.edu/fac/byers/cours...ndouts/TWL.txt
Expert Level: Do the above task with recursion |
you can find all of the words on an x by x boggle board, as long as you can find all of the words on an x by x boggle board.
edit- answer:
Let M be an n x n matrix. (meaning, let M be an n-1 x n-1 array)
Let W be the set of accepted words.
if a set of entries of M, called X, where each entry of M in X is adjacent to the one both preceding and following, is an element of W, then there is a word in the matrix.
Problem: define the set of all possible values for X
(note: the maximum length of X is n*n)
how to do this:
loop through all entries of M sub 'i,j', (we don't need to check if it is apart of the alphabet because this is a boggle board) then check for each entry that:
- M sub 'i+1,j' is an element of W.substring(0,1)
- M sub 'i-1,j' is an element of W.substring(0,1)
- M sub 'i,j+1' is an element of W.substring(0,1)
- M sub 'i,j-1' is an element of W.substring(0,1)
- M sub 'i+1,j+1' is an element of W.substring(0,1)
- M sub 'i-1,j-1' is an element of W.substring(0,1)
- M sub 'i+1,j-1' is an element of W.substring(0,1)
- M sub 'i-1,j+1' is an element of W.substring(0,1)
if any of those are true (and if not then move onto the next entry in the matrix), repeat the process with the new entry and see if it is an element of W.substring(1,2). if that is true, do it again with W.substring(2,3), then (3,4), and so on.
how all of that looks in code talk
PHP Code:
M = 2-dimensional string array of length n-1 by n-1 containing only letters of the alphabet because arrays start at index 0 and not 1;
W = string array containing all of the acceptable words, one word per entry;
for (i=0;i<n-1;i++) { //row # of the matrix
for (j=0;j<n-1;j++) { //column # of the matrix
check(i,j,0);
}
}
check(r, s, p) {
t = p;
for (k=0;k<8 && t==p;k++) { //8 because there are 8 directions to check
if (k==0 && r-1>=0) { //look above the entry, if its not at the top
for (l=0;l<W.length();l++) { //for each word in W
if (M[r][s] in W[l].substring(p,p+1)) {
//p is used to check the pth letter of the lth string in W.
p++; //<--move onto the next letter and...
check(r-1, s, p); //start over
}
}
} else if (k==1 && r+1<=n-1) {//look below, if its not at the bottom
...
} else if (k==2 && s-1>=0) {//look left, if its not at the left edge
...
}
//dot dot dot
}
}
since i'm being asked to show what words can be found:
add the string W[l] to a separate array every time
M[r][s] in W[l].substring(p,p+1) && p == W[l].size(), and then break; so that the search can continue.