I've also written a simple "Jotto" game which doesn't benefit from indexing at all - linear scanning through the few thousand 5 or 6 letter words at each elimination step used to take far less than a second on my old 6 Mhz XT in the pre-history of modern PC computing). In that case linear searches through the lists started at each abstraction is reasonably quick even when you're correlating to find out that "uvz" with "zyzxw" could, indeed, be "the". Your dictionary contains every word indexed by its abstraction, and you can easily find that "every" matches "zyzxw"). (To find every word which zyzxw could be in a cryptogram you "abstract" it into a pattern: abacd. I have written cryptogram solvers which used a similar, though much simpler indexing structure. I haven't personally written a crossword generator. Create a program that generates every possibility (using the data structure described) and a whenever it "gets stuck" have it backtrack until it finds new possibilities.Īs implied by paxdiablo, you'll have to include a large pool of "words" for the generator to have a reasonable chance of creating a completed "solution." Anyone who is experienced with crosswords realizes that they allow the setter to take quite a few liberties (such as frequent use of compass points, archaic terms and poetic contracts) in order to get themselves o'er the hump as it were. Once you have this basic data structure then the rest of the program would, presumably, be a tree generation and traversal (with backtracking of course). Having built the indexed data structure I described, of course, allow for much more efficient searches for possible matches then would be possible by performing linear scans of just the global word list or even linear scans of the length separated lists). (For example a 8 letter word starting with "w" and ending with "k" would be the intersection of all 8 letter words starting with "w" and all those ending with "k" - which, unsurprisingly would include "homework"). the first index is by total word length while the second one is by length, then by letter position, and finally by letter (six letter words with a second letter of "i" for example).Īfter you've built this index you can then express each step in trying to set or solve a puzzle in terms of set operations performed on these. Then you'd create another dictionary of dictionaries of dictionaries. If you're trying to create an index of words such that you could attempt to "solve" (or create) crosswords then I guess you'd start with a dictionary of words indexed by length. However, it is not the fastest way to do it. It's pretty easy to code this in any language. The actual format was use left in your array. To get a list of all valid possibilities.Īnd, as each word was found, it was copied to a clues.txt file that contained both the word and multiple possible clues. If you know you have a 5-letter word starting with "app", it's quite easy to use: grep '^app.$' words.txt Mine ended up being written in shell script (believe it or not) and using the dictionary that came from Linux as a word search tool. It's a lot easier to locate words with letters at known positions than to evaluate those letters at any starting position within a word. Similarly for words where you have known letters at any positions. That way, you would know that "app" was the start of the word and be able to limit your searches to those starting with "app", not every word that has "app" in it. Once you have the pattern, then you start finding words to place in it. Things like being symmetrical around one of the diagonals and disallowing a square of four white cells (to ease the task of selecting suitable words). If you look at most crosswords, they tend to follow certain rules to make it easier. Trying to fit words into a grid while creating the pattern on the fly is very time consuming and prone to errors. The first thing you should do is design your patterns (blacks where you can't put letters and whites where you can). I had a database of words and their clues which could be sorted by times used (so that I wouldn't tend to get duplicate crosswords on subsequent runs). I've actually written a crossword program before (cryptic but the theory behind the construction is identical).
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |