A popular word game involves finding words from a grid of randomly generated letters. Words must be at least three letters long and formed from adjoining letters. Letters may not be reused and it is valid to move across diagonals. As an example, consider the following 4 * 4 grid of letters.

A B C D

E F G H

I J K L

M N O P

The word “FAB” is valid (letters in the upper left corner) and the word “KNIFE” is valid. The word “BABE” is not valid because the “B” may not be reused. The word “MINE” is not valid because the “E” is not adjacent to the “N”.

Write a program that uses a 4 * 4 two-dimensional array to represent the game board. The program should randomly select letters for the board. You may wish to select vowels with a higher probability than consonants. You may also wish to always place a “U” next to a “Q” or to treat “QU” as a single letter. The program should read the words from the text file words.txt (included on the website with this book) and then use a recursive algorithm to determine if the word may be formed from the letters on the game board. The program should output all valid words from the file that are on the game board.