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