Compressed Crosswords

Dennis Shasha

Omniheurist Course

Computer Science


 

Description

Given a 6 x 6 grid, find a set of words, all different such that you can fill in as much of the 6 x 6 grid with letters as possible and every maximal string is a word in the set. A horizontal maximal string is bordered at the left by the left edge or by a blank and on the right by the right edge or a blank. It is read left to right. A vertical maximal string is bordered at the top by the top edge or by a blank and on the bottom by the bottom edge or a blank. It is read top to bottom.

The ultimate puzzle is to cram all these words into the smallest square possible.