WordBoggle

In the word game Boggle, 16 cubes are placed in a container that is shaken. The scattered cubes fall into a 4x4 grid structure. The top faces of each cube compose a playable area where players have to find words constructed from adjacent letters. For instance, the playable area might look like either of these:

ABCD  XYZI
EFGH  ABIJ
IJKL  RSLN
MNOP  POOM

In the example to the right, we could form the word "BARS" by starting at the B and travelling left-down-right. Note that we could not, however, create the word SOON, as it would require a diagonal move from the O to the N.

In our version of the game, the path must travel horizontally or vertically at each step without reusing any cubes. For instance, the word COAT might be found in many different arrangements (other arrangments are also possible):

COAT      COA       CO       CO
            T       TA        AT

In our version of the game, a player scores points for any word from a list of acceptable words. The score for each word is the square of its length. Thus, a word with three letters scores 9, four letters scores 16, etc. If the same word can be formed in more than one way from the grid, each distinct path is counted. Also, words which are a part of a longer word may be counted. Examples:

TEXX       CATX
REEX       XXSX

In the first example, the word TREE may be formed in two different ways: starting with the T, we may go down-right-up, or we may go down-right-right. Thus, we score points for the four-letter word tree twice (total 32 points). In the second example, we score points for CAT and CATS, assuming both were in the list of acceptable words. Thus, we score 9 + 16 = 25 points.

Each cube has six different letters on its sides (no letter will appear more than once on the same cube). The arrangement of the cubes in the grid, and which face is upward (in play) is perfectly random. You are given a String[] cubes, with exactly 16 elements, each element of which is six letters long, indicating the letters that appear on each of the cubes. You are also given a String[] dict, each element of which is one of the allowed words.

You are to return a double indicating your expected score, assuming you play perfectly and find all possible paths for all acceptable words that can be found in the 4x4 grid.