XWORD.BAS May 2000 by Marc Kummel aka Treebeard. Contact mkummel@rain.org, http://www.rain.org/~mkummel/ What is XWORD.BAS? ---------------------- XWORD is an MSDOS BASIC program I wrote as my Dunn Middle School science fair project for spring 2000. I also used it to make a crossword puzzle on my Stumpers webpage at : 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 goal for this program, to make crossword grids from random lists of words. It works! 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 a big number into prime factors 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 the 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 Web browsers and 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. 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 count as 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. Their Web site includes C code, discussion of algorithms, and more good stumpers. They don't accept BASIC code. Check out: Using XWORD.BAS ---------------- XWORD is a simple DOS program. Run it in DOS, or a Command session in Windows. When XWORD starts, it looks for a file named WORDLIST.TXT in its own directory. It will immediately begin making crossword grids from that list. Use any text editor or word processor to make your own word lists, and save them as text with line breaks. Copy your list over WORDLIST.TXT or use the menu option to load it. Spaces are trimmed, so a word entry like "New York" is treated as "newyork". XWORD is a pretty *raw* program, strictly first draft. Several options can only be changed in the source code. There's no error trapping yet, so any file error will stop it. I hope to get back to this. Press as XWORD runs to pause the action and get a menu. All options are called with a single key press: Continue making grids uit Quit program <- -> Arrow keys toggle menu Arrow keys scroll through big word lists when paused Arrow keys scroll through big word lists when paused Help, (but there's no help yet except this file) isplay Display flag toggle to show all grids or only the best rid +/- Change grid size by pressing <+> and <-> keys uto Auto-find the smallest square grid (not implemented) ord Input a new word list, eg science.txt ave Save current best grid sequentially as BESTnnn.TXT oad Load a saved grid, filename must be right tml Save best grid and answer as WEBnnn.HTM and WEBnnnA.HTM

rint Print current best grid with printer on LPT1: ptions Program options (doesn't work yet) nfo Info on current best grid step Single-step mode toggle, useful for debugging inimum Minimum grid, show the worst grid found so far andomize Randomize the random number generator Crossword grids can be aved as text files and oaded back in to continue a search. Saved files are numbered sequentially as BEST001.TXT, BEST002.TXT, etc. You'll want to clear these out every once in a while. It only loads the grid info between and and not the word list, so don't edit those lines and be sure the correct word list is already loaded. Grids can also be saved as HTML web pages with the tml command. Saved pages are numbered sequentially in pairs as WEB001.HTM and WEB001A.HTM, etc. The first file is a numbered blank grid with the words as clues. The second file is the answer grid with the letters in place on the grid. You can then print from your browser or use them on the Web. To add clues to make a real crossword puzzle, you can edit the pages with a text editor, and directly add your clues to the HTML. By default, XWORD uses the attribute to make black squares. This looks good, but might not work with all browsers. Set bgcolorflag%=FALSE in the source code to use a black GIF instead. There are several more switches and settings than can only be changed in the source code. I'll add an ptions command in the future to access these. The Files: ----------- I wrote this program to solve a stumper. You'll have to study the source code for more info. I wrote it using MS Basic PDS v7.10. It will probably need some changes to work with other flavors of QBasic or Quick Basic. Unzip all files into a directory, start a Command Session, and type XWORD to start. Or just click on the file in Explorer if you have it configured right. XWORD.EXE DOS executible to solve Reset stumper XWORDnn.BAS BASIC source code WORDLIST.TXT Default word list (DMS), ok to change DMS.TXT Dunn Middle School staff and students DMSBEST.TXT My best DMS grid saved DMSWEB.HTM My best grid as a web page with clues DMSWEBA.HTM My best grid as a web page with answers SCIENCE.TXT Science A-Z word list STATES.TXT U.S. states word list USPRES.TXT U.S. presidents word list ELEMENTS.TXT Chemical elements word list POTM.TXT Word lists used for the POTM trials BLACK20.GIF Alternative GIF to make black squares on web page README.TXT This file TBVAULT.TXT Treebeard's Basic Vault info Conditions: ------------ This program and source code are yours to use and modify as you will, but they are offered as freeware with no warranty whatsoever. Give me credit, but do not distribute any changes under my name, or attribute such changes to me in any way. You're on your own! If you find this program or code useful, then let me know what you do with it, as a courtesy to a fellow programmer who still hacks for fun and glory. Any suggestions or comments will be much appreciated. Send comments and fixes to: Marc Kummel aka Treebeard mkummel@rain.org http://www.rain.org/~mkummel/ http://www.treebeard.org/ For more interesting Basic software with source code, check out Treebeard's Basic Vault at .