Generating Word Search Puzzles | Hacker News Reader

Generating Word Search Puzzles

weblog.jamisbuck.org

29 pointsjamis13 comments

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...

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.

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.

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/

Finished products: iOS: https://itunes.apple.com/nl/app/word-search-plus-word-puzzle... Android: https://play.google.com/store/apps/details?id=com.codestare....

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.

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.

I added a Word Search to many language learning apps. See middle picture top:

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.

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.

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

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?

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?

The article links to my github repository for a wordsearch utility I wrote (here: 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.

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

Try making crossword puzzles programmatically :)

Reply on news.ycombinator.com