Reverse Boggle Challenge
Completed Jan. 22, 2012
Boggle is a game where given a 4×4 grid of random letters, you are asked to identify as many words as you can by chaining letters together. This problem is about writing a reverse Boggle solver.
Introduction to Boggle
In the game of Boggle, the main idea is that you find words by starting with any letter and constructing a chain by moving to any of the letter's eight neighbors. You cannot use a letter more than once in a single chain, but you may reuse letters for other words. For instance, you can find the word SUPER like so:
Other possible words might include TURN, HIP, HIPS and KELP. For every dictionary word identified within the grid, score 1 point per letter. For example, scoring the aforementioned words would net SUPER (5) + TURN (4) + HIP (3) + HIPS (4) + KELP (4) for 20 points.
The goal of this particular challenge is to solve this problem in reverse. That is, given a dictionary of acceptable words, create a 4×4 grid of letters in such a way to maximize the number of points. Only words found in the dictionary may be scored, and each word may only be scored once. If the list of words were HASKELL, PYTHON, LISP and PERL, an acceptable grid would be:
This grid contains all the words, so it scores the maximum number of possible points, which is 21. The list of words will typically be larger than the available space in the grid. In that situation, your task is to create a grid that maximizes the score.
Clarification: Any particular word in the dictionary can only be scored once, even if it takes different paths to create. In the above grid, PERL can be made in two ways, but can only be scored once.
Clarification: The letters used in the grid DO NOT need to follow the same distribution of the physical Boggle game. You may use any single letter in any position. This also means that there is no combined "Qu" tile as in the actual game. Q and U must occupy separate spaces.### Input
Your program should accept a list of words as standard input. This will be the dictionary. The dictionary is in a format such that:
- It is an ascii text file, with unix line endings (\n).
- First line is a single positive integer n.
- the next n lines will be words, one per line. Make sure your program is case-insensitive.
An example dictionary:
4 HASKELL PERL PYTHON LISP### Output
The program you create will output a 4×4 grid in such a format that:
- The output contains four lines.
- Each line is an ascii string of 4 characters representing the rows of the grid in order.
An example output given the above dictionary:
PKSP EIAY RLTH LZNO