4 ms·

How hard would it be to write a program that can create such puzzles, given a set of few thousand valid English (or some other language) words?

by akudha 5y ago

mzl 5y ago
It’s not terribly hard given a decent enough constraint programming environment I think, although I haven’t tried to implementing the construction problem yet. Given that one is typically limited to at most 10 different letters (since each letter must have a unique corresponding digit), the number of possible word combinations is reasonably limited as well.
- akudha 5y ago
  Are you only thinking of the equation a + b = c? Maybe in this case it is limited, but if we try anything like a + b + c = d, then it might be quite a large list to check, no? According to the website below, there are 5,454 four letter words, 12,478 five letter words and 22,157 six letter words (assuming one stops at six letter words). https://www.bestwordlist.com/6letterwords.htm https://www.bestwordlist.com/6letterwords.htm If we allow well known names (sports stars, movie stars, presidents etc) then this list might become very large.
  - mzl 5y ago
    Sure, there are lots but I think it should be doable. Will probably try sometime. Easiest is to make a model that fixes the lengths of the words, and just run it for different word lengths. As a comparison, see this model solving crosswords using constraint programming. https://github.com/Gecode/gecode/blob/develop/examples/crossword.cpp https://github.com/Gecode/gecode/blob/develop/examples/cross...
dragontamer 5y ago
Its difficult to understand programs that do what you want, but relatively easy to write (!!!!). I recommend reading Knuth's The Art of Computer Programming: Volume 4 Fascicle 5. Knuth covers the creation of word-puzzles such as crossword puzzles (embedding words into a 2-dimension plane that fits). Knuth also covers the "Create a comma-free code" problem to a high amount of detail, which probably is most related to your question of "creating puzzles of a certain type". TAOCP Fascicle 5 is pretty short but is a very difficult read due to the difficulty of the material. But it really does cover what you're asking for.

How hard would it be to write a program that can create such puzzles, given a set of few thousand valid English (or some other language) words?

by akudha 5y ago

How hard would it be to write a program that can create such puzzles, given a set of few thousand valid English (or some other language) words?

mzl 5y ago

It’s not terribly hard given a decent enough constraint programming environment I think, although I haven’t tried to implementing the construction problem yet. Given that one is typically limited to at most 10 different letters (since each letter must have a unique corresponding digit), the number of possible word combinations is reasonably limited as well.

akudha 5y ago
Are you only thinking of the equation a + b = c? Maybe in this case it is limited, but if we try anything like a + b + c = d, then it might be quite a large list to check, no? According to the website below, there are 5,454 four letter words, 12,478 five letter words and 22,157 six letter words (assuming one stops at six letter words). https://www.bestwordlist.com/6letterwords.htm https://www.bestwordlist.com/6letterwords.htm If we allow well known names (sports stars, movie stars, presidents etc) then this list might become very large.
- mzl 5y ago
  Sure, there are lots but I think it should be doable. Will probably try sometime. Easiest is to make a model that fixes the lengths of the words, and just run it for different word lengths. As a comparison, see this model solving crosswords using constraint programming. https://github.com/Gecode/gecode/blob/develop/examples/crossword.cpp https://github.com/Gecode/gecode/blob/develop/examples/cross...

dragontamer 5y ago

Its difficult to understand programs that do what you want, but relatively easy to write (!!!!). I recommend reading Knuth's The Art of Computer Programming: Volume 4 Fascicle 5. Knuth covers the creation of word-puzzles such as crossword puzzles (embedding words into a 2-dimension plane that fits). Knuth also covers the "Create a comma-free code" problem to a high amount of detail, which probably is most related to your question of "creating puzzles of a certain type". TAOCP Fascicle 5 is pretty short but is a very difficult read due to the difficulty of the material. But it really does cover what you're asking for.