 |
| Wonderword Puzzle |
Teleword is a word search puzzle that appears in The Sunday Oregonian. The daily paper carries Wonderword, an identical puzzle. Both are produced by the same guy: David Q. Oullet, who makes these puzzles by hand.
The aren't particularly difficult, all you have to do is locate the words from the list in the grid. It takes a little time and seems to go slower as you locate more words. It can be downright tedious when you are down to two or three short words and the entire grid seems to have been marked off. It's not my favorite puzzle, but if I am not ready to start my day, it's a good way to procrastinate.
Anyway, I got to wondering how hard it would be to generate such a puzzle, so I put my programmers cap on and set to. It didn't take long before I had solution. Well, I had a program. Let's run it and see if it can generate a square from the list of words in Sunday's puzzle. I let it run overnight. It was still running the next morning and still hadn't found a solution. Hmm, maybe this problem is tougher than I thought.
Let's do a little analysis. The square is 15 letters across and 15 rows tall. There are 38 words with an average length of, let's say, 7. So any one word, on average, can fall roughly 500 different places
( 8 starting rows
times 8 starting column
times 8 directions).
means each word has 500 possible positions, so we have 38 (words) to the 500th power possible combinations, which is like a number with a thousand zeros which may as well be infinity. There isn't enough CPU power on the planet to try that many combinations. But maybe the problem isn't that tough and we'll get an answer in a some kind of reasonable time frame, like overnight.
When it didn't find an answer, I went back and revisited the code. I made some minor changes which I didn't think should effect it, but evidently it did because it returned a solution in about an hour. A solution, not THE solution. The puzzle I used as a model has ten extra letters, which would be spaces in my solution, and my program's solution only had three. Well, if we can generate one solution in an hour, maybe if we run it for a day it will find more solutions, and maybe one of those will have the required ten spaces. So some more minor changes to the code and I fired it up again.
Here's what it has so far (it shows its current state every one million attempted word placements):
R H S M T S Y D O N O V A N G
O O U P O H E A R C L A R K E
C N L L R O E A R E R O
K E H L L I D A R D A H C A R
A Y E E I A N Y N C B M M G
N C R H R N B G B I H I E E I
D O M S O M G A F L M E R R E
R M I Z P L A S L I U A R D S
O B T F O E L N T L E E L S S
L S S H R M N I S O O L S S J
L E E B C E B N O D S E
B I L L Y W D I E S L E S K R
A L L I C H D E R A S N E
P E T U L A O I S C I M
Y T S U D S G G O R T K Y
dimensionof(words): 38 wordcount: 8
placed: 30 counter: 164000000
This program is CPU intensive, which means everything else gets slow. I was thinking it would be handy to have another computer to run this program so I could go web surfing without having to drag this CPU hog around with me everywhere I went, and then I remembered that there are sites out there on the web that will let you write, compile and run programs on their servers, free. Well, shiver me timbers, let's try that. So I pulled up a few, loaded my program (copy & paste, it's only a couple of hundred lines long) and pressed the GO button. Here's the ones I tried.
I'm still dinking with the program. I will post it on github if I am ever satisfied with it.
No comments:
Post a Comment