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:

Boggle

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 Problem

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: Reverse Boggle

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:

  1. It is an ascii text file, with unix line endings (\n).
  2. First line is a single positive integer n.
  3. 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:

  1. The output contains four lines.
  2. 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

Resources

This challenge is now closed.


Scoreboard

None yet!

Come Chat!

Join channel ##proggit on freenode.

Bugs

Having issues with the the site? Let us know.