The Garden of Words

Welcome to the latest episode of "The Amazing Adventures of Alabama Adams, the Adjunct Archeologist (AAAAAA)!"

“This will be easy,” says Alamaba Adams. “All I need to do is to return this priceless relic, The Dictionary of All Words that Have Not Been Invented Yet, to its owner, the Genie of the Garden. And here I am, on a hillock overlooking this garden. And it looks beautiful: a square grid of tiles, with a plant on each tile, each trimmed to look like a letter of the English alphabet. There does not seem to be any pattern to these letters. Also, some tiles are empty.”

Here’s an example of what she sees. The empty tiles are marked with a period (.).

LG.DETCEQO
ISEA.E.TKS
JTTOMAWOBZ
EEN.DARRPC
MESWZMES.E
JD.SEVOKBS
FIHREM.E.B
TTKHMGWZUW
BUNNEQDHJS
QETID.DIRE

Alabama enters from the top left, on the tile with the letter L; it looks like the exit from the garden is at the bottom right, at the tile with the letter E. She heads that way.

Since no self-respecting archeologist would ever navigate a rectangular grid by walking diagonally, Alabama picks a direction and starts walking down. This takes her to the tile marked with the letter I. Proceeding in the same direction, she heads toward the next tile, the one marked with J -

“Aaaaaa!” says Alabama (she’s contractually required to say this once per episode).

The reason she says this is because she ran head-first into an invisible obstacle.

“I’m in a maze,” realizes Alabama. “Why does it always have to be mazes?!”

At this point, there is a loud puff next to her, and the Genie appears, like, uh, a genie from a bottle.

“You cannot go this way!” says the Genie.

“W...why?” stammers Alabama.

“Because no word starts with LIJ. At least, no word in my dictionary.”

“What does this have to do with your garden...?”

“Everything!” says the Genie. “Because this is not a common garden. It is the Garden of Words. You cannot just randomly wander from tile to tile. The tiles you step on must correctly spell words - and not just any words. They must be in my dictionary, which, if you are curious, contains the ten thousand most common English words - although I don’t have any words of three letters or fewer, because short words are boring. Here’s the whole thing, in a text file, because you will need it. Also, there should be a single dot between every pair of the words you spell.”

Alabama looks around.

“I see,” she says. “Instead of walking down again, I can move to the right, to the letter S - so I’ve spelled LIS so far - and then two more tiles down adds T and E, so I’ve spelled LISTE - and then two more tiles to the right gives me N and a dot, so I’ve spelled LISTEN and landed on a dot and not run into any walls, hurrah!”

“You’re getting the hang of it,” nods the Genie.

Now Alabama is speeding up, running through the garden.

“Three more to the right is DAR, and then one down and two more to the right is ES., so I’ve got DARES and a dot. Now one up to the P, one left, three up, and, whooh, five left gives me PROTECTED and a dot. Hmm. What’s next? I think I can spell ESTEEMED, but I’ve already visited these S and T tiles when I was spelling LISTEN - is this allowed?”

“Sure,” says the Genie. “You can revisit the tiles at any time. What you cannot do is hop in place to repeat the tile immediately. If you need OO, you’d better find two adjacent tiles with that letter. Oh, by the way, on your path toward the exit all the words will be different. If you find yourself spelling the same word again, you are probably wandering about in a loop.”

“Got it!” says Alabama. “So, from that dot in the top row, it’s down, left, two down, left, down, right, down, right, and I’ve got ESTEEMED and a dot. Now two right, four down, and then all the way to the right in the bottom row gives me SEEMED.DIRE - so the solution is LISTEN.DARES.PROTECTED.ESTEEMED.SEEMED.DIRE. How did I do?”

Here’s the path she ended up tracing with the unvisited tiles replaced with underscores, as an illustration:

L_.DETCE__
ISE____T__
_T_____O__
EEN.DARRP_
ME____ES._
_D.SE_____
____E_____
____M_____
____E_____
____D.DIRE

“You did terribly!” says the Genie severely. “Yes, you got to the exit, and you only spelled dictionary words, and you spaced them correctly - but there is a much shorter way. You should expect by now that only the shortest solutions are accepted. Here’s a hint, though. Can you get to that dot after ESTEEMED quicker?”

Alabama stares at the garden, and then she smiles.

“Sure,” she says. “After I spell LISTEN I can simply step back to the left after that dot, and then I can spell NEED and then it’s the same way as before, so it’s LISTEN.NEED.SEEMED.DIRE - is this correct?”

L_________
IS________
_T________
_EN.______
_E________
_D.SE_____
____E_____
____M_____
____E_____
____D.DIRE

“This time, correct,” says the Genie.

“What if there are multiple shortest answers?” asks Alabama.

“I’d accept any of them,” says the Genie. “I’m a mythological creature, not a monster.”

“Thanks,” says Alabama. “This is neat. I can probably solve this without any kind of a computing device, though.”

The Genie grins in response.

“Maybe you can, but where's the fun in that?! Also, this ten by ten plot - this is not the real garden. The real one is bigger. Much bigger. It's thirty two by thirty two. Good luck with that.”

There is another puff, and the Genie is gone.

Here are a couple more examples for the small 10x10 case.

Puzzle input:
LYAMIRKLQA
ACCXUEPYYB
.E.EQDFVYU
.PRRU.QXRA
ONE.CFEI.W
MIG.EOMEXR
.IUK.RMSXS
YTLAYVR.RI
LENRO.GMKS
HHJ.LFDODE

Solution:
LACE.REGULAR.LOYALTY.MINE.REQUIRED.FORMS.MODE

Puzzle input:
CON.EGCKGR
DRRETAS.EY
VMTSPKZWGN
SMIGOND.WA
LATED.MARR
WLVXRPYI.P
LOVUKUAUGA
.ONKFTS.BX
.BWMPNQORO
A.SK.NLOVW

Solution:
CORRESPOND.ARRANGE.SAGE.ESTIMATED.PUTS.BROW

Note: two clarifications were asked for and may be helpful: a) The length of the solution in characters (including dots, since they are part of the path) is what should be minimized; b) The last word is in no way different from the other words, and so must be a complete word as well.