6 ms·

Generating Word Search Puzzles

29 points by jamis 11y ago

rrrrob 11y ago
Neat! This sort of thing also is a really nice project for playing around with logic programming languages. One missing feature is enforcing a unique solution, which is something you'd generally expect from a word search puzzle.
- jamis 11y ago
  Good point. I was relying mostly on the words being sufficiently complex that the odds of them appearing by chance would be small, but enforcing that assumption would be a good exercise.
HardyLeung 11y ago
Nice. One improvement would be to throw in letters in frequencies proportional to the likelihood of appearance in actual text. For example: http://www.math.cornell.edu/~mec/2003-2004/cryptography/subs/frequencies.html http://www.math.cornell.edu/~mec/2003-2004/cryptography/subs... Though this is a simple problem, if you are picky there are actually other considerations... how well do the words intersect (do you prefer more of a sparse tree-like structure, or maximal mesh-like intersection). What is the optimal dimension of a puzzle given the input. How the order of words (random vs. longest word first) affect the quality of the puzzle. etc. I have a half-done word search puzzle app (with a twist) so this piques my interest. But I like this one nice and clean.
- Robadob 11y ago
  I'd prefer the challenge of seeing how many sub-strings from the actual words you could embed in the word-search, without having duplicates of the full strings. Bit of misdirection for a harder challenge.
melling 11y ago
I added a Word Search to many language learning apps. See middle picture top: http://www.h4labs.com http://www.h4labs.com I basically brute forced it and simply skipped words that I couldn't fit. I'd love to hear ideas from other implementations. At some point I'm going to make the grid size dynamic when I rewrite a better version for the iPad.
- jamis 11y ago
  Backtracking works well to try and fit words in tightly, but (especially in cases where the words just BARELY fit) it can take a long time to generate the puzzles. I'm sure that judicious use of heuristics could prune unprofitable branches more quickly and speed things up, but I've not explored those optimizations at all.
bumbledraven 11y ago
Would be neat if it could make https://en.wikipedia.org/wiki/Wonderword https://en.wikipedia.org/wiki/Wonderword puzzles, in which the remaining letters spell out a word.
- jmartinpetersen 11y ago
  From the article: "(Bonus: the letters left after finding all the words spell out one of my favorite features of Ruby…)" Or did I misunderstand something?
- jmartinpetersen 11y ago
  From the article: "(Bonus: the letters left after finding all the words spell out one of my favorite features of Ruby…)" So it's clearly been done. Or did I misunderstand something?
- jamis 11y ago
  The article links to my github repository for a wordsearch utility I wrote (here: https://github.com/jamis/wordsearch https://github.com/jamis/wordsearch) and it includes a description of a technique for embedding a message in the unused letters of a wordsearch puzzle.
lips 11y ago
Docs: "$ wordsearch nitwit blubber oddment tweak" :)
brainburn 11y ago
Interesting, and familiar. I had this idea a while back and made a puzzlegame for Android and iOs that does basically this. The idea is to create puzzles on ANY subject that contain words relating to that subject. - let user type, search wikipedia for articles starting with that text - grab selected article, find out words in it that are links to other articles (they are probably related) - generate a puzzle I also do random placement, but I also add a score to the final puzzle, taking into account spread in vertical/horizontal/diagonal words. Then I just create as many random puzzles as I can in 4 seconds and take 'the best'. More detailed writeup here: http://miscellany.codestare.com/WordsearchPlus/ http://miscellany.codestare.com/WordsearchPlus/ Finished products: iOS: https://itunes.apple.com/nl/app/word-search-plus-word-puzzle/id898234027?l=en https://itunes.apple.com/nl/app/word-search-plus-word-puzzle... Android: https://play.google.com/store/apps/details?id=com.codestare.wordsearch https://play.google.com/store/apps/details?id=com.codestare....
lukas099 11y ago
Try making crossword puzzles programmatically :)

29 points by jamis 11y ago

Neat! This sort of thing also is a really nice project for playing around with logic programming languages. One missing feature is enforcing a unique solution, which is something you'd generally expect from a word search puzzle.

jamis 11y ago
Good point. I was relying mostly on the words being sufficiently complex that the odds of them appearing by chance would be small, but enforcing that assumption would be a good exercise.

HardyLeung 11y ago

Nice. One improvement would be to throw in letters in frequencies proportional to the likelihood of appearance in actual text. For example: http://www.math.cornell.edu/~mec/2003-2004/cryptography/subs/frequencies.html http://www.math.cornell.edu/~mec/2003-2004/cryptography/subs... Though this is a simple problem, if you are picky there are actually other considerations... how well do the words intersect (do you prefer more of a sparse tree-like structure, or maximal mesh-like intersection). What is the optimal dimension of a puzzle given the input. How the order of words (random vs. longest word first) affect the quality of the puzzle. etc. I have a half-done word search puzzle app (with a twist) so this piques my interest. But I like this one nice and clean.

Robadob 11y ago
I'd prefer the challenge of seeing how many sub-strings from the actual words you could embed in the word-search, without having duplicates of the full strings. Bit of misdirection for a harder challenge.

melling 11y ago

I added a Word Search to many language learning apps. See middle picture top: http://www.h4labs.com http://www.h4labs.com I basically brute forced it and simply skipped words that I couldn't fit. I'd love to hear ideas from other implementations. At some point I'm going to make the grid size dynamic when I rewrite a better version for the iPad.

jamis 11y ago
Backtracking works well to try and fit words in tightly, but (especially in cases where the words just BARELY fit) it can take a long time to generate the puzzles. I'm sure that judicious use of heuristics could prune unprofitable branches more quickly and speed things up, but I've not explored those optimizations at all.

bumbledraven 11y ago

Would be neat if it could make https://en.wikipedia.org/wiki/Wonderword https://en.wikipedia.org/wiki/Wonderword puzzles, in which the remaining letters spell out a word.

jmartinpetersen 11y ago
From the article: "(Bonus: the letters left after finding all the words spell out one of my favorite features of Ruby…)" Or did I misunderstand something?
jmartinpetersen 11y ago
From the article: "(Bonus: the letters left after finding all the words spell out one of my favorite features of Ruby…)" So it's clearly been done. Or did I misunderstand something?
jamis 11y ago
The article links to my github repository for a wordsearch utility I wrote (here: https://github.com/jamis/wordsearch https://github.com/jamis/wordsearch) and it includes a description of a technique for embedding a message in the unused letters of a wordsearch puzzle.

lips 11y ago

Docs: "$ wordsearch nitwit blubber oddment tweak" :)

brainburn 11y ago

Interesting, and familiar. I had this idea a while back and made a puzzlegame for Android and iOs that does basically this. The idea is to create puzzles on ANY subject that contain words relating to that subject. - let user type, search wikipedia for articles starting with that text - grab selected article, find out words in it that are links to other articles (they are probably related) - generate a puzzle I also do random placement, but I also add a score to the final puzzle, taking into account spread in vertical/horizontal/diagonal words. Then I just create as many random puzzles as I can in 4 seconds and take 'the best'. More detailed writeup here: http://miscellany.codestare.com/WordsearchPlus/ http://miscellany.codestare.com/WordsearchPlus/ Finished products: iOS: https://itunes.apple.com/nl/app/word-search-plus-word-puzzle/id898234027?l=en https://itunes.apple.com/nl/app/word-search-plus-word-puzzle... Android: https://play.google.com/store/apps/details?id=com.codestare.wordsearch https://play.google.com/store/apps/details?id=com.codestare....

lukas099 11y ago

Try making crossword puzzles programmatically :)