Introduction

While between jobs, I decided to take a crack at the palindromic pangram puzzle posed by ITA Software. My initial reason for doing so was to explore space and time tradeoffs in using the C++ Standard Template Library by using it on an algorithmically complex (and interesting) problem.

As I worked on the problem and compared my solution with the solutions of others, I realized that my approach was informed by my years of developing production-quality software. For example, rather than plunging in and developing an algorithm for the core problem directly, I first

analyzed the data file provided, as well as likely alternate data files, before deciding on an overall approach; and
concentrated on reducing the search space before applying various core algorithms.

Accordingly, I decided to create this web site to explain and demonstrate the whole solution.

The original problem statement goes like this:

A palindrome is a sequence of words like "lid off a daffodil" or "shallot ayatollahs" that uses the same letters reading backwards as forwards. The words need not form a meaningful or grammatical sentence.

A palindromic pangram is a multi-word palindrome that includes all 26 letters of the alphabet. Write a program to find a palindromic pangram. Use this dictionary: http://www.itasoftware.com/careers/WORD.LST.

Bonus (optional, very hard!): find the shortest possible palindromic pangram in terms of the total number of words or letters used.

(As of 05 May 2009, ITA is no longer posting the word list or the puzzle, perhaps because so many people have already posted solutions. However, I could still find the original problem statement at http://www.itasoftware.com/careers/puzzles07.html as of 22 June 2009.)

Use the second set of menu buttons on the left to see the details of my approach.