How to find all words on the Boggle board using Dynamic Programming?

Question

I enrolled in the Algorithms, Part II course on Coursera, and one of the assignments is to solve the Boggle game: http://coursera.cs.princeton.edu/algs4/assignments/boggle.html

The honor code requires that I don't publicly post the solution, so here's the pseudocode of the basic algorithm instead.

visit:
  word <- board[i][j]
  start <- dictionary.match(word, start)
  if start is not null
      visited[i][j] <- true
      word <- prefix + word
      if word is longer than min required length 
          words <- words + word

      for (x, y) ∊ adj(i, j)
          if not visited(x, y)
            visit (x, y)

  visited[i][j] <- false

The dictionary is implemented using a Trie.

The above code works, and I passed the assignment, but then I came across this blog post that claims a faster solution using dynamic programming:

It turns out, we can use a nifty dynamic programming technique to quickly check whether a word (from the dictionary in this case) can be constructed from the board or not!

Here is core point of the dynamic programming idea:

For a word of length k to be found (end location) at the [i, j]-th location of the board, the k-1'th letter of that word must be located in one of the adjacent cells of [i, j].

The base case is k = 1.

A letter of length 1 will be found (end location) in the [i, j]-th cell of the board of the only letter in the word matches the letter in the [i, j]-th location of the board.

Once our dynamic programming table is populated with the base case, we can build on top of that for any word of length k, k > 1.

Unfortunately, the author did a poor job of explaining, and I'm not able to follow his solution. I'd like to though, and hoping someone here could explain it to me.

P.S.:

1. Not a duplicate of this question, as that one doesn't use DP; please, keep those duplicate-happy fingers in check.

2. There's sufficient effort demonstrated on my part and not asking anyone to do my homework. I already have a solution of my own. What I'm interested in is learning a better way of solving the problem, if one exists.

Thanks!

Answer 1

The idea for the DP (wrong) solution is simple, assuming that we want to check if the word "apple" is existing in the table.

• Let's create a table dp[k][n][n], with dp[a][x][y]means that whether the prefix of the word with length a could end at cell (x, y).

  [a][p][p]
  [x][x][l]
  [x][x][e]
  

For above table, dp[1][0][0] = true, as the prefix length 1 of apple is a and dp[2][0][1] = true etc.

• So, how to check if dp[a][x][y] is true? check all of the neighbouring cell of (x,y), and if one of its neighbour has dp[a - 1][][] = true, so dp[a][x][y] also true. For our example, for cell (0,2) , dp[3][0][2] = true, as one of its neighbours, cell (0,1) has dp[2][0][1] = true
• By default, all dp[0][x][y] = true
• For any cell (x, y) , if dp[length of word][x][y] = true -> the word exists in the table.

Notice that this solution could not check the case when a character is being used for more than one time.

Like if we need to look for the word apa and with the above table

dp[1][0][0] = true -> dp[2][0][1] = true -> dp[3][0][0] = true