Treebeard's Stumper Answer 12 May 2000

Science Fair Crossword

It seems so simple. Take a list of words, say the first names of all Dunn Middle School students and staff, and arrange them all crossword-style in the smallest possible square grid. But there are too many possibilities for even my fast computer program to check them all! That's my project for this year's DMS Science Fair, just one among the many interesting projects and collections. Here is my best shot (so far) at making a real crossword puzzle with my XWORD program. The answers are all DMS first names, and we all wrote our own tough clues.

This puzzle will only make sense to DMS kids. I know these kids pretty well, and I couldn't guess half their clues! The kids did better, and Whitney and Amanda finished it first. You can also get the DMS word list and try it without clues as a 'fill-in' or 'criss-cross', or whatever you call that type of puzzle. Duplicate names are only used once in the grid. (Thanks, Graybear!)

The real stumper is to build the grid. For example, what's the smallest square grid that will hold all 26 A to Z science words in my ABCs of Science stumper?

(To print these crosswords, you must have "Print background colors" selected in your browser. That option is in Tools/Internet Options/Advanced in IE5.)

1        2  3  4    5    6  7  8          9    10        11        12                13              14                      15      16        17        18    19              20        21    22    23  24  25                    26      27              28          29                              30    31          32                  33          34            35          36  37  38        39            40                            41                        42                    43                44              45

Across	Down
Young beyond his years Muffin man and Bakery boy Throw the ball! Tahoe gaucho sparkles Snails5=ice cream, you can do it! Stratomaster Flat mice, in tune Oldest of the three Cher live Justin Timberlake 4 me Blond belly-dancing singer Napster rapster Sporadic magoo See 21 across Winning scavenger Garden namesake Start with an "A" & ride everyday Green belt Lover of the Lorax Backwards "draw" Basketball singer	Man without hat Fire drinker Red Hot Chili Peppers support Chipmunk in glider port Soccer queen Don't mess with _____ Twin artist Class time! Light my fire 6 down cousin Frogman Slam pow ah zap! Filthy "e" with a "c" P.T.S.C. Pants watch Camel spotter Rhymes with 7, bumps to China Fashionable diva, teacher at heart Flea's apprentice Evil "O" Musical longhair	Reader with glasses Short stuff Little Buddha Man with hat Tall horsejumper Surfb763 Mojo man Married to Midland Bus man Genie in a bottle Horse named "Kate"

Puzzle generated by Treebeard's XWORD v.19 program.
10 May 2000 at 01:47:14

Last week's crossword solution is below. The clues were too hard for me, but the kids did better. Amanda and Whitney got it first. I can fit all DMS staff and students into a 21 x 21 grid except "cianna," who pushes it to 21 x 22. That took 21 hours of computer time! There might be a better solution, but there is no simple algorithm to find it except to keep trying. Mathematicians call such problems intractable or NP-complete. They are the basis of modern cryptography because they are so hard to solve, even for fast computers.

1J E S S 2E     3T 4H O 5M A 6S           7T   8O   P       R       A   A   9A B 10B Y     E   R       11W H I T 12N E Y   X   M   E       S   I   13P   I   K   I   L       O   N   14S U S A N   A   L       C   E               P   A       15T Y L 16E R   K   Y           17V   E           C     R             18J I 19L L I A N           H     I     20K       O   A   N   21C H 22R I 23S         24C 25O R E Y     R   U   C   E   A   H       26A   L   V   27G   D   R   E   R   C   A   28M A R C I   29I L A N A   E           H   N   A   T   V   N   B   N   N   30C H 31A S E   E   R     32M E G     R           H   N   L       Y     A     33B R I A N   34M   R   D                 G     R   E     35K A R I   R   36A   37B   38D     G     I   L   39A   R   S   E   R   R   40A N N I E   A       M   C   T   W   C   U   L     E   41A N D R E A       I       E   C   E           N       N   42C H A N T A L L E   N     43T I N A       D       N       I       E             44M I R A N D A     45C I A N N A

Puzzle solution generated by Treebeard's XWORD.BAS program.
17 May 2000, 1:14:37

Notes:

Graybear took the DMS word list and solved the puzzle without using the clues:

It took me less than an hour to get the solutions... There is not a unique solution, there are four, but I believe I can narrow it down to two by assuming that 34-Down "Mojo man" is Marc, and 28-Down "Short stuff" is Mary. The other pair is 39-Down "Horse named 'Kate'" and 45-Across "Basketball singer" which are Amanda and Cianna.

I'm impressed, Graybear! Mojo is my dog, so 34-down is me.

Here's my best shot at making a word grid from the 26 science words in my ABCs of Science stumper. A grid of 23 by 23 is the best I can do. This was hard since most words are long and share the same "ology" ending.

1D   2C       3I       4Q               5W 6A V E M E C H A 7N I C S     U   8L             S       N   E   E   H       A   I             T       D   M   U   9T A 10X O N O M Y   11J   12F   R   13H   R   I   R   H   E   T   N     14U R O L O G Y   O   S   O   Y   N   U   O     N   R   N   D   L   T   L   O   O   M   L     G   E   O   R   O   R   O   L   B   M   O     I   S   M   O   G   Y   G   O   I   E   G     A   T   Y   L   Y       Y   G   O   C   Y     N   R       O               Y   L   H         P   Y   15Y O G A   16S       17P     O   A   18Z     S     19B     Y     C   20K   A     G   N   O     Y     I   21M     22R A D I O L O 23G Y   I   O   24E C O L O G Y       T   N   E   E     C   L     H     L   C       O   E   O   O     S   O     O     O   O       L   S   N   L         G     L     G   L       O   I   T   25O O L O G Y     O     Y   O       G   O   O   G               G         G       Y   L   L   Y               Y         Y           O   O                                         G   G                     26V O L C A N O L O G Y   Y

Puzzle generated by Treebeard's XWORD.BAS program.
05-21-2000 12:46:43

Crossword puzzles are more difficult to make than to solve. There are just too many possibilities to check them all systematically in any realistic time-frame, even with fast computers. Even if a potentially best solution is found, there's no way to prove it's the best except to check every other possible arrangement. So the programming goal isn't to find the best arrangement right off, but to quickly find an ok solution, and then improve it as better solutions are found. There's no easy way to know when we're done.

Factoring big numbers into primes is another classic intractable problem. There are mathematical shortcuts, but in the end, you basically have to try dividing your number by every prime number less than its square root. When numbers get very big, the task is too much, even for fast computers. At least that's the hope, since modern encryption programs and secure servers use this intractable math problem to make their secret keys. The Traveling Salesman problem is another classic intractable problem. There may well be a better solution to the DMS word list, and I just haven't found it yet. There's no way to know except to keep searching. Bonus stumper: which Simpsons episode also mentions NP-complete problems?

My XWORD program does better than the commercial Crossword Compiler program at finding tight grids for random word lists, but it's still a pretty dumb program. It starts by scoring each word for how many letters it shares with other words in the list, and then it normalizes the scores for word length. It usually starts with a high-scoring medium-length word, and usually puts it near a corner, and then builds a linked list of crossed-words from that. If it's the best so far, it remembers. Then it tries another, and so on. It doesn't get any smarter as it works longer, but it randomly breaks its own rules now and then. Is that enough to be AI?

My program can't (yet) put words into solid blocks. Real crossword puzzles like you find in the newspaper always feature solid word grids, and they are always symmetrical. That's much harder. Good crossword grids are still mostly contructed by hand, though computer dictionary searches with wildcard characters are helpful. I've never tried to make a real crossword grid by hand. It's a special skill with commercial value. Crossword enthusiasts can recognize the style of individual constructors. The commercial Crossword Compiler program can make real puzzles, and it has many other useful features. My program is not meant to compete.

Making a minimum crossword grid from a list of words is known as a Crozzle, after an Australian newspaper puzzle. This was the spring 1996 problem for the Programmer Of The Month (POTM) contest. The POTM Web site includes C code, discussion of algorithms, and more good stumpers. They don't accept BASIC code in their contests due to their professional Unix bias. They ran each entered program with three different word lists for a max time of 10 minutes each, and recorded words used, connector letters, and total letters. I did it too and got these results:

	WORDS:  the total number of words used from ALL THREE wordlists
	CONNS:  the number of "connector" letters in the THREE solutions
	LETTR:  the total number of letters in the THREE solutions
	Seconds:   time as measured by timex for all THREE

             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
      ------------   ---- ----- ----- ------- ----  -------------------
            jigsaw   212   280   646  794.83  GCC  Franz Korntner
           knuppel   201   227   613 1777.48  G++  P.Frants S.Pieterse
        Wordsworth   198   235   607 1788.40    C  Davor Slamnig
          sswordpu   192   204   587 1799.94    C  Bob Ashenfelter
             Binky   189   201   596  180.13  GCC  Robert Rounthwaite
               Gak   188   218   559 1787.23  G++  Justin Legakis
       DontCrossMe   185   182   586 1698.50  G++  Mike Goldshteyn
ME -->   XWORD.BAS   176   166   600 1800.00  BAS  TREEBEARD
       theos_cross   173   183   540 1457.99  GCC  Theo Sprokholt
        2RoadsCroz   173   177   571 1504.98    C  Gary Gressel
           CrossIt   173   171   590 1642.85    C  Dennis Brooks
       <Lots more>

Eighth place is not bad for good ol' DOS BASIC in this competition! And I ran my program on my home computer, not the fast Unix box the others ran on! The winning programs made tighter grids by putting words right next to each other. My program can't do that yet, but I know how to do it.

Here are some Web links for further research on building crosswords:

• You can download my XWORD program with source code and executable from Treebeard's Basic Vault. This is a rough draft DOS BASIC/QBasic/QuickBasic program that runs fine in a Command window under Win98. It will make a crossword grid from any word list, and save it as an HTML file ready for the Web. I used my program to make the crosswords and solutions on this page. It's primative, but it might be a useful program for teachers.

• Making a minimum crossword grid from a list of words is known as a Crozzle, after an Australian newspaper puzzle. This was the spring 1996 problem for the Programmer Of The Month (POTM) contest. The POTM site includes C code, discussion of algorithms, and more good stumpers. But I started from scratch, using good old BASIC.

• Crossword Compiler is a highly regarded commercial crossword puzzle program for constructors. They offer a free demo, but you have to pay for the real thing. There are many other programs freely available, eg at the Crossword Archive.

• CRUCIVERB-L is a no-spam Web page and Email list for crossword puzzle constructors. Well-known editors and constructors reside here. It's ok to lurk.

• Ray Hamel's Crossword Puzzles page has a huge collection of crossword web links that I don't need to repeat. Lots of puzzles, and sites about puzzles.

• Sik Cambon Jensen's Masters Thesis on Design and Implementation of Crossword Compilation Programs Using Serial Approaches is available on the Web as HTML and PDF files. He treats crossword puzzle construction as a math problem. Looks great!

• You can spend days following the links at Eric Weisstein's World of Mathematics site. Start with "NP-Complete" and see where you end up! Here's another list of different NP-complete math problems.

Back to Stumper

Last modified .